老青菜

选择排序

2019-05-07

选择排序是一种简单直观的排序算法,属于比较类排序,内部是通过比较元素大小,决定每个位置应该存储哪个元素。
常见的算法如下:

  1. 简单选择排序(SelectionSort
  2. 堆排序(HeapSort


简单选择排序

简单选择排序(SelectionSort)原理比较简单,如下:

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。
  3. 以此类推,直到所有元素均排序完毕。

代码实现

// objc 版本
- (void)selectionSort:(int[] )arr withLength:(int )length {
    //循环 length 次
    for (int i=0; i<length-1; i++) {
        //查找每个位置的合适的元素
        int findIndex = i;//默认第i个,即待排序列表 第一个元素 是最小(大)的元素
        //循环待排序列表,找到 最小(大)的元素
        for (int j=i+1; j<length-1; j++) {
            if (arr[j]<arr[findIndex]) {
                //找到更小的元素
                findIndex = j;
            }
        }
        //交换最小的元素,交换位置
        if (findIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[findIndex];
            arr[findIndex] = tmp;
        }
    }
}


算法分析

最好时间复杂度:O(n²)
最坏时间复杂度:O(n²)
平均时间复杂度:O(n²)
空间复杂度:O(1)
稳定性:稳定。




堆排序

堆排序(HeapSort)是一种树形选择排序方法,利用大顶堆、小顶堆(完全二叉树Complete Binary Tree)结构的顺序存储结构特性,每次从树中选择出最大节点。
基本流程如下:

  1. 将无需序列构建成一个堆(heap,即完全二叉树),顶据升序降序需求选择大顶堆或小顶堆。
  2. 将堆顶元素与末尾元素交换,将最大元素”沉”到数组末端,重新调整结构,使其满足大顶堆、小顶堆特性。
  3. 然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

那什么是完全二叉树?

完全二叉树

完全二叉树:(Complete Binary Tree),若设二叉树的深度为h,除第h层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。

例如序列 array[0,...,n-1] ,生成的完全二叉树有下面几个特性。
1.针对任意节点i,节点之间索引规则:

 父节点:(i-1)/2 ,i != 0
 左孩子:2*i+1
 右孩子:2*i+2

2.节点顺序规则:

小顶堆:array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]
大顶堆:array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]

这里我们看一下完全二叉树的大顶堆版本。

大小顶堆

大顶堆即任意节点都要比两个子节点要大,升序的堆排序中会用到。
小顶堆即任意节点都要比两个子节点要大,降序的堆排序中会用到。
例如一个序列:

int arr[] = {9,4,5,6,8,1};

对应二叉树和完全二叉树结构如下:


代码实现

/// 从 index 节点开始,调整二叉树,成为大(小)顶堆。调整之后,可能会使子节点不满足大(小)顶堆,会继续调整子节点。
void heapSortAdjustHandle(int* array, int length, int index) {
    int parentIndex = index;
    while (true) {
        int parentValue = array[parentIndex];
        int maxValue = parentValue;
        int maxIndex = -1;
        // 1.和左子节点比较大小
        int leftChildIndex = 2*parentIndex + 1;
        if (leftChildIndex > length-1) break;
        int leftValue = array[leftChildIndex];
        if (leftValue > maxValue) {
            maxIndex = leftChildIndex;
            maxValue = leftValue;
        }
        // 2.和右子节点比较大小
        int rightChildIndex = 2*parentIndex + 2;
        if (rightChildIndex <= length-1) {
            int rightValue = array[rightChildIndex];
            if (rightValue > maxValue) {
                maxIndex = rightChildIndex;
                maxValue = rightValue;
            }
        }
        if (maxIndex <= -1) break;
        // 3.交换最大值
        array[parentIndex] = maxValue;
        array[maxIndex] = parentValue;
        // 4.继续调整子节点
        parentIndex = maxIndex;
    }
}
/// 堆排序
void heapSort(int* array, int length) {
    // 1.从第一个非子节点开始,调整节点顺序,构造大(小)顶堆
    for (int i=(length-1-1)/2.0; i>=0; i--) {
        heapSortAdjustHandle(array, length, i);
    }
    // 2.循环列表,依次取出顶部元素(最大、最小元素),并继续调整剩下的元素,满足大(小)顶堆
    for (int i=length-1; i>=0; i--) {
        // 2.1交换首尾元素,剔除顶部元素,即选择最大或最小的元素,放在尾部
        int lastValue = array[i];
        array[i] = array[0];
        array[0] = lastValue;
        // 2.2首部元素改变,在剩下的元素(除length-1之后的元素)内,继续调整首节点,满足大(小)顶堆。
        int rightBoundary = i-1;
        heapSortAdjustHandle(array, rightBoundary, 0);
    }
}


算法分析

最好时间复杂度:O(nlogn)
最坏时间复杂度:O(nlogn)
平均事件复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章