排序 | LeeHui

#排序的稳定性

存在多个具有相同排序码的记录，排序后这些记录的相对次序不变则称排序是稳定的。

🌰 待排序列： 37 12 98 37 69 若经过排序后，序列为 12 37 37 69 98，则该排序是稳定的；若序列为 12 37 37 69 98，则排序是不稳定的。

步骤：假设待排序列为 data。data[0] 已经是有序的了；将 data[1] 插入到有序序列 {data[0]} 中；第 p+1 次排序时，将 data[p+1] 插入到有序序列 {data[0],data[1],...,data[p]} 中，先用临时变量 temp 存储 data[p+1] 的值，然后将 data[p] 和 temp 进行比较，如果后者比较小，则将 data[p] 移动到 data[p+1] 的位置，继续将 data[p-1] 与 temp 比较，如果后者小，则将 data[p-1] 移动到 data[p] 的位置，重复以上比较过程，直到找到 temp 的插入位置。“从后向前，边比边移。”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template<class T>
void InsertionSort(T data[], int n) {  //不减序排列
    for (int i = 1; i < n; i++) {
        T temp = data[i];
        int j;
        for (j = i - 1; j >= 0 && data[j] > temp; j--) {
            data[j + 1] = data[j];
        }
        data[j + 1] = temp;
    }
}

稳定
空间代价 $O(1)$
时间代价 $O(n^2)$

直接插入排序的两个性质：

在最好情况（序列本身已是有序的）下时间代价为 $O(n)$
对于短序列，直接插入排序比较有效

#折半插入排序

思想：在插入第 i 个记录时，前面的记录已经是有序的了，可以用二分法查找第 i 个记录的正确位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


template<class T>
void BinaryInsertionSort(T data[], int n) {
    int left, right, mid;
    for (int i = 1; i < n; i++) {
        T temp = data[i];
        left = 0, right = i - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (data[mid] > temp)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for (int j = i - 1; j >= left; j--)
            data[j + 1] = data[j];
        data[left] = temp;
    }
}

折半插入排序的时间复杂度仍为 $O(n^2)$
折半插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。

#希尔排序

直接插入排序只允许相邻的元素交换,希尔排序将原序列根据不同的步长("间隙")划分成许多小的序列,然后每一个小序列内进行直接插入排序,这样就允许了原序列的远程元素间的交换。逐步缩小步长,让其最终为 1,最终序列有序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template<class T>
void ShellSort(T data[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 直接插入排序
        for (int i = gap; i < n; i++) {
            T temp = data[i];
            int j;
            for (j = i; j >= gap && data[j - gap] > temp; j -= gap) {
                data[j] = data[j - gap];
            }
            data[j] = temp;
        }
    }
}

希尔排序空间复杂度为 $O(1)$

希尔排序时间复杂度与增量序列有关:

当增量序列为$K=2^x$时,时间复杂度为 $O(n^2)$

排序

#排序的稳定性

#排序算法的衡量标准

#插入排序

#直接插入排序

#折半插入排序

#希尔排序