数据结构：排序算法详解（插入与选择排序）

一、排序

1.1 概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

1.2 常见的排序算法

本文将重点讲解插入排序和选择排序。

二、插入排序

基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际应用中玩扑克牌时，就用了插入排序的思想。

2.1 直接插入排序

当插入第 i (i>=1) 个元素时，前面的 array[0], array[1], …, array[i-1] 已经排好序。此时用 array[i] 的排序码与 array[i-1], array[i-2], … 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

void InsertSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0) {
            if (a[end] > tmp) {
                a[end + 1] = a[end];
                end--;
            } else {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

2.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是 gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序。然后 gap=gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序，当 gap=1 时，就相当于直接插入排序。

它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

一组一组来使用直接插入，组的间隙慢慢变小，最后一层就是直接插入排序。这种方式相比于直接插入排序，外层的 ++ 循环变成了 gap 的递减，从 O(N) 到 O(logN)。

代码实现如下：

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (a[end] > tmp) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

希尔排序的时间复杂度

外层循环的时间复杂度为 O(log n)。内层循环次数随 gap 变化。希尔排序在最初和最后的排序的次数都为 n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至 n。

因此，希尔排序的时间复杂度为：O(n log n) ~ O(n^2)，最好的情况为 O(n^1.3)，最坏的情况为 O(n^2)。

三、选择排序

选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

3.1 直接选择排序

1. 在元素集合 array[i]–array[n-1] 中选择关键码最大 (小) 的数据元素。
2. 若它不是这组元素中的最后一个 (第一个) 元素，则将它与这组元素中的最后一个（第一个）元素交换。
3. 在剩余的 array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。

通俗来讲，先遍历一遍，找一个最小的数据，放第一个，然后遍历第二个到最后一个数据，找最小放在第二个。这样一直遍历，放置，数据就排好了。

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin; i < end; i++) {
            if (a[i] < a[mini]) {
                mini = i;
            }
            if (a[i] > a[maxi]) {
                maxi = i;
            }
        }
        if (maxi == begin) {
            maxi = mini;
        }
        swap(a[mini], a[begin]);
        swap(a[maxi], a[end]);
        begin++;
        end--;
    }
}

直接选择排序的特性总结：

1. 思考非常好理解，但是效率不是很好。实际中很少使用。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

3.2 堆排序

堆排序主要基于二叉堆结构，需要深刻理解向下调整算法和向上调整算法。

void AdjustDown(int* a, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child] > a[child + 1]) {
            child++;
        }
        if (a[child] < a[parent]) {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int* a, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, i, n);
    }
    int end = n - 1;
    while (end > 0) {
        swap(a[0], a[end]);
        AdjustDown(a, 0, end);
        end--;
    }
}

以上代码供复习使用。