数据结构(24)-排序

2020-05-28 本文已影响0人 xxxxxxxx_123

概念

假设含有 $n$ 个记录的序列为 ${r_1, r_2,...r_n}$ ，其相应的关键字分别为 ${k_1, k_2,...k_n}$ ，需确定1，2，...n的一种排列 $p_1, p_2,...p_n$ ，使其相应的关键字满足 $k_{p1} <= k_{p2}<=...k_{pn}$ (非递减或非递增)关系，即使得序列称为一个按关键字有序的序列 ${r_{p1},r_{p2},...r_{pn}}$ ，这样的操作就称为排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为内排序和外排序。内排序是在排序的过程中，所有待排序的记录全部被放置在内存中，外排序是由于排序的记录个数太多，无法同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序来说，排序算法的性能主要受3个方面的影响：

时间性能
辅助空间
算法的复杂度

根据排序过程中要借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序、归并排序。

按照算法的复杂度则分为简单算法和改进算法。简单算法包括冒泡排序、简单选择排序和直接插入排序。改进算法包括希尔排序、堆排序、归并排序、快速排序。

冒泡排序

冒泡排序是(Bubble Sort)是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，一直到没有反序的记录为止。首先，我们需要一个交换的方法：

void swap(int *a, int i, int j) {
    int tmp = a[i];
    a[i]    = a[j];
    a[j]    = tmp;
}

冒泡初级版

严格的说，这并不是标准的冒泡排序，因为它并不满足"两两比较相邻记录"的冒泡排序思想。只能算是最最简单的交换排序。

void bubbleSort0(int *a, int len) {
    for (int i = 0; i < len; i++) {
        for (int j = i+1; j < len; j++) {
            if (a[i] > a[j]) {
                swap(a, i, j);
            }
        }
    }
}

正宗冒泡

void bubbleSort1(int *a, int len) {
    for (int i = 0; i < len; i++) {
        for (int j = len - 1; j >= i; j--) {
            if (a[j] > a[j+1]) {
                swap(a, j, j+1);
            }
        }
    }
}

冒泡优化

加入一个变量来标记后续元素是否是有序的，如果是有序的就退出循环，没必要继续比较了。

void bubbleSort2(int *a, int len) {
    bool noOrder = true;
    for (int i = 0; i < len && noOrder; i++) {
        noOrder = false;
        for (int j = len - 1; j >= i; j--) {
            if (a[j] > a[j+1]) {
                swap(a, j, j+1);
                noOrder = true;
            }
        }
    }
}

优化过后的冒泡排序，在最好的情况下，即待排序数组是有序的，时间复杂度为 $O(n)$ ；在最差的情况下，则需要 $1+2+3+...(n-1)$ 次，即为 $O(n^2)$ 。

简单的选择排序

简单的选择排序(Simple Selection Sort)就是通过 $n-i$ 次关键字之间的比较，从 $n-i+1$ 个记录中选择出关键字的最小记录，并第 $i(1 <= i <= n)$ 个记录交换之。

// 选择排序
void selectSort(int *a, int len) {
    int min;
    for (int i = 0; i < len; i++) {
        min = i;
        for (int j = i+1; j < len; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        if (min != i) {
            swap(a, i, min);
        }
    }
}

简单的选择排序的时间复杂度也为 $O(n^2)$ 。但是由于其交换移动数据次数会少一些，性能上还是优于冒泡排序的。

直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增1的有序表。说的通俗一点，当我们从小到大排序时，就是将第一个元素作为基准，遍历后面的元素如果遇到比自己小的元素就往前移动直到基准元素为止，这样每次遍历前面的元素都是有序的，比较的元素的元素找到位置插入即可。

比如我们要将{2, 3, 5, 4, 1}从小到大排序，首先把2作为基准，遍历后面的元素，第一次遇到3比2大，不作处理；第二次遇到5不做处理；第三次遇到4，先和5作比较，4比5小，将5挪到4的位置，变成{2, 3, 5, 5, 1}，然后再把4赋值给第3个位置的5，此时数组变为{2, 3, 4, 5, 1}；第四次遇到1，1比5小，然后把5放到1的位置，{2, 3, 4, 5, 5}，然后4比5小，变成{2, 3, 4, 4, 5}，然后3比4小，变成{2, 3, 3, 4, 5}，然后2比3小，变成{2, 2, 3, 4, 5}，最后再把第一个2换成1，就变成了{1, 2, 3, 4, 5}。

void insertSort(int *a, int len) {
    int i, j, tmp;
    for (i = 1; i < len; i++) {
        if (a[i] < a[i-1]) {
            tmp = a[i];
            for (j = i-1; a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
    }
}

根据代码可以看出，最好的情况，直接插入排序的时间复杂度为 $O(n)$ ，最坏的情况则是 $2+3+...+n$ 次，可以得出其时间复杂度为 $O(n^2)$ 。相对于冒泡和简单选择排序，直接插入排序排序的性能还是要好一点。

希尔排序

由D.L.Shell提出的一种排序算法，在他之前，所有的排序算法的时间复杂度都是 $O(n^2)$ ，而希尔排序则是突破这个时间复杂度的第一批算法之一。

希尔排序需要引入一个新的概念，基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。像{2, 1, 3, 6, 4, 7, 5, 8, 9}可以称为基本有序，像{1, 5, 9, 3, 7, 8, 2, 4, 6}这样9在第三位、2在倒数第三位就不算是基本有序。

为了使我们的待排序序列变成基本有序，因此我们需要采取如下措施：将相距某个增量的记录组成一个子序列，这样才能保证子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

下面我们通过示例{9, 1, 5, 8, 3, 7, 4, 6, 2}来看看希尔排序的实现：

void shellSort(int *a, int len) {
    int i, j, tmp;
    int increment = len;
    do {
        increment = increment / 3 + 1;
        for (i = increment; i < len; i++) {
            if (a[i] < a[i - increment]) {
                tmp = a[i];
                for (j = i - increment; j >= 0 && tmp < a[j]; j -= increment) {
                    a[j+increment] = a[j];
                }
                a[j+increment] = tmp;
            }
        }
    } while (increment > 1);
}
/***
 {9, 1, 5, 8, 3, 7, 4, 6, 2}
 increment = 4
 315897462
 314897562
 314697582
 314627589 214637589
 increment = 2
 213647589
 increment = 1
 123647589
 123467589
 123465789 123456789
 */

通过代码可以看出，希尔排序的关键在于增量，增量的选取直接影响排序效率。那么如何选取一个合适的增量呢？这是一个难题，不过前人们总结出了一些关于增量和时间复杂度的规律：

增量序列	时间复杂度
$n / 2^i$	$O(n^2)$
$2^i - 1$	$O(n^{3/2})$
$2^i3^i$	$O(nlog_2n)$

另外，需要注意的是，增量序列的最后一个增量值必须等于1才行。

堆排序

堆排序(Heap Sort)是对简单选择排序进行的一种改进。此处的"堆"指的是一种数据结构，它是具有下列性质的完全二叉树：每个结点的值都大于或者等于其左右孩子的结点的值称为大顶堆；每个结点的值都小于等于其左右孩子结点的值称为小顶堆。通过定义可知，根结点一定是堆中所有结点的最大者或者是最小者。

如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：
当 $1 <= i <= n/2$ 时， $2i、2i+1$ 是结点 $i$ 的左右孩子
$\begin{cases} k_i >= k_2i \\ k_i >= k_{2i+1} \end{cases}$
或
$\begin{cases} k_i <= k_2i \\ k_i <= k_{2i+1} \end{cases}$

堆排序就是利用堆进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆(小顶堆)。此时，整个序列的最大值(最小值)就是堆顶的根结点。将它移走，其实就是将其与堆数组的末尾元素交换，此时末尾就是最大值(最小值)，然后将剩余的 $n-1$ 个序列重新构成一个堆，这样就会得到 $n$ 个元素中的第二大的值(第二小值)。如此反复执行，即可得到一个有序序列了。

现在我们还需要解决两个问题：

如何由一个无序序列构建成一个堆？
如果在输出堆顶元素后，如何调整剩余元素称为一个新的堆？

// 调整堆 将a转化为一个大顶堆 a中除s之外均满足堆的定义
void heapAdjust(int *a, int s, int m) {
    int tmp = a[s];
    
    for (int i = 2*s; i <= m; i *= 2) {
        if (i < m && a[i] < a[i+1]) {
            i++;
        }
        if (tmp >= a[i]) {
            break;
        }
        a[s] = a[i];
        s = i;
    }
    
    a[s] = tmp;
}

void heapSort(int *a, int len) {
    int i;
    
    // 构建大顶堆
    for (i = len/2; i >= 0; i--) {
        heapAdjust(a, i, len - 1);
    }
    
    
    for (i = len - 1; i > 0; i--) {
        // 将堆顶元素和子序列的最后一个元素交换
        swap(a, 0, i);
        // 将剩余的元素a[0...i-2]重新构建大顶堆
        heapAdjust(a, 0, i-2);
    }
}

堆排序的时间复杂度为 $O(nlogn)$ ，但是堆排序是一种不稳定的排序方式。

归并排序

归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是，假设初始序列含有 $n$ 个记录，则可以看成 $n$ 个有序的子序列，每个子序列的长度为1，然后两两归并，得到 $n/2$ 个长度为2或者1的有序子序列；然后再两两归并，。。。，如此重复，直至得到一个长度为 $n$ 的有序序列为止。这种排序的方式，我们称为2路归并排序。

下面我们根据示例{2, 1, 3, 6, 4, 7, 5, 8, 9}来看看归并排序是如何实现的。首先我们将其进行递归拆分，{2, 1, 3, 6, 4}和{7, 5, 8, 9}，然后再拆分为{2, 1, 3}、{6, 4}、{7, 5}、{8, 9}，最终拆分为{2}、{1}、{3}、{6}、{4}、{7}、{5}、{8}、{9}。然后再进行归并操作，{1, 2, 3}、{4，6}、{5, 7}, {8, 9}，继续归并{1, 2, 3, 4, 6}、{5, 7, 8, 9}，最终归并为{1, 2, 3, 4, 5, 6, 7, 8, 9}。

// 将有序的sorts[s...m] 和 sorts[m+1...n] 归并为有序的results[s...t]
void merge(int sorts[], int results[], int s, int m, int t) {
    int j, k, l;
    // 将sorts中的记录从小到大归并到results
    for (j = m+1, k = s; s <= m && j <= t; k++) {
        if (sorts[s] < sorts[j]) {
            results[k] = sorts[s++];
        } else {
            results[k] = sorts[j++];
        }
    }
    
    // 将剩余sorts[s+l]复制到results[k+l]
    if (s <= m) {
        for (l = 0; l <= m-s; l++) {
            results[k+l] = sorts[s+l];
        }
    }
    
    // 将剩余的sorts[j+l]复制到results[k+l]
    if (j <= t) {
        for (l = 0; l <= t-j; l++) {
            results[k+l] = sorts[j+l];
        }
    }
}

/// 将无序的unsorts[s...t] 归并为有序的results[s...t]
/// @param unsorts 给定的待排序序列
/// @param results 拍完序的结果
/// @param s 起始位置的下标
/// @param t 结束位置的下标
void recursiveMergeSort(int unsorts[], int results[], int s, int t) {
    int m;
    int res[T_MAX_SIZE];
    
    if (s == t) {
        results[s] = unsorts[s];
    } else {
        // 将unsorts分为unsorts[s...m] 和 unsorts[m+1...t]
        m = (s + t) / 2;
        // 将unsorts[s...m]归并为有序的res[s...m]
        recursiveMergeSort(unsorts, res, s, m);
        // 将unsorts[m+1...t]归并为有序的res[m+1...t]
        recursiveMergeSort(unsorts, res, m + 1, t);
        
        // 将res[s...m]和res[m+1...t]归并到results[s...t]
        merge(res, results, s, m, t);
    }
}

归并排序的时间复杂度为 $O(nlogn)$ 。是一种比较占用内存，但却效率高且稳定的排序算法。

快速排序

快速排序是由图灵奖获得者Tony Hoare设计，被称为20世纪十大算法之一。快速排序属于交换排序，即它也是通过不断比较和移动交换来实现排序的，只不过它增大了记录的比较和移动距离，将关键字大的记录从前面移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了比较次数和移动交换的次数。

快速排序的基本思想是：通过一次排序将待排序记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序的关键就是需要先找到一个基准(枢轴)元素，然后将其放到一个位置上，这个位置左边的值都比它小，右边的值都比它大。

int partition(int *a, int startIndex, int endIndex) {
    // 每次先把起始位置的元素设置为基准元素
    int pivotkey = a[startIndex];
    while (startIndex < endIndex) {
        // 从后往前（从右往左）遍历如果后面的比基准元素的小 就交换位置
        // 相当于把比基准元素小的元素往前面 移动
        while (startIndex < endIndex && a[endIndex] >= pivotkey) {
            endIndex--;
        }
        swap(a, startIndex, endIndex);
        
        // 从前往后（从左往右）遍历如果后面的比基准元素的大 就交换位置
        // 相当于把比基准元素大的元素往后面 移动
        while (startIndex < endIndex && a[startIndex] <= pivotkey) {
            startIndex++;
        }
        swap(a, startIndex, endIndex);
    }
    
    return startIndex;
}

void recursiveQuickSort(int *a, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(a, startIndex, endIndex);
    
    // 找到一个基准，然后将待排序序列分为两部分 
    recursiveQuickSort(a, startIndex, pivotIndex - 1);
    recursiveQuickSort(a, pivotIndex + 1, endIndex);
}

void quickSort(int *a, int len) {
    recursiveQuickSort(a, 0, len - 1);
}

在最优的情况下，快速排序算法的时间复杂度为 $O(nlogn)$ ，而在最坏的情况下，其时间复杂度为 $O(n^2)$ ，平均情况下为 $O(nlogn)$ 。由于递归调用造成栈空间爱你的使用，其平均情况下，空间复杂度为 $O(nlogn)$ 。另外，由于关键字的比较和交换是跳跃进行的，因此快速排序是一种不稳定的排序方法。

快速排序的优化

1. 优化选取基准元素(枢轴)

如果我们选取的基准元素正好位于整个序列的中间位置，那么我们可以将整个序列分为大子集和小子集。相反，则需要经过多次遍历来进行处理。优化的方法如下：

随机获取基准元素
三数取中法。取三个元素先进行排序，将中间数作为枢轴，这三个数一般是取最左边、最右边、中间的三个数
九数取中。先从数组中分三次取样，每次取三个数，然后每个样品取一个中数，最后再从三个中数中取中数

2. 优化不必要的交换

int partition(int *a, int startIndex, int endIndex) {
    int pivotkey = a[startIndex];
    int tmp = pivotkey;
    while (startIndex < endIndex) {
        while (startIndex < endIndex && a[endIndex] >= pivotkey) {
            endIndex--;
        }
        a[startIndex] = a[endIndex];
        
        while (startIndex < endIndex && a[startIndex] <= pivotkey) {
            startIndex++;
        }
        a[endIndex] = a[startIndex];
    }
    
    a[startIndex] = tmp;
    return startIndex;
}

优化递归操作

使用迭代的方式替换递归

void iterationQuickSort(int *a, int startIndex, int endIndex) {
    while (startIndex < endIndex) {
        int pivotIndex = partition(a, startIndex, endIndex);
        iterationQuickSort(a, startIndex, pivotIndex - 1);
        startIndex = pivotIndex + 1;
    }
}

总结

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(nlogn)$ ~ $O(n^2)$	$O(nlogn)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定
快速排序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)$ ~ $O(n)$	不稳定