八大经典排序算法总结

妖狐艹你老母 2022-09-28 13:25 180阅读 0赞

终于到了排序部分了。这部分也是最难总结的，毕竟不同的排序算法思想多少会有差别，有些甚至完全不一样。今天不知道要码多少字。好吧，先为我的手指默哀三分钟~

先来看一下这篇文章的目录吧：  
桶排序、插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、堆排序。一共八个排序算法的思想。好了，闲话少叙，先来看看第一个排序算法，桶排序：

**1、桶排序：**  
桶排序的算法思想和笔者之前总结过的一篇查找算法的散列查找算法思想是差不多的，利用标记数组来对各个出现过的元素进行标记，然后直接按照一定的顺序输出，为此，我们需要创建一个标记数组来标记各个元素出现的次数，先来看一个最简单的桶排序：对非负整形数排序：

// 利用桶排序的算法思想对非负整形数排序 
    #include <iostream>
    using namespace std;
    const int N = 100010;
    int book[N];
    
    int main() {
        int n, x, max = 0;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> x;
            book[x]++; // 将出现的元素次数标记加 1 
            if(max < x) { // 求出所有元素中出现的最大元素 
                max = x;
            }
        }
    
        cout << "排序后：" << endl;
        for(int i = 0; i <= max; i++) { // 从小到大输出排序的元素 
            if(book[i]) {
                // 通过元素出现的次数输出这个元素,出现多少次就输出多少个 
                for(int j = 0; j < book[i]; j++) {  
                    cout << i << " ";
                }
            }
        }
    
        return 0;
    }

来看看结果：

![这里写图片描述][SouthEast]

Ok，这里是从小到大排序，如果从大到小呢？其实很简单，我们只需要改一行代码就行了

`for(int i = max; i >= 0; i--) { // 从大到小输出排序的元素 `

来看看结果：

![这里写图片描述][SouthEast 1]

不知道小伙伴发现没有，这里的排序算法是有很大弊端的，首先，由于是直接利用标记数组的思想，那么意味着我们只能够对非负整形数字进行排序，而且不能对浮点数排序，第二个就是我们排序的数字不能过大（因为数组下标的限制）。  
针对第一个问题，我们可以采用类似于散列函数的方法，即通过某种转换方式将浮点数或者负数转换为正整数作为数组下标，然后按照从小到大或者从大到小输出，当然，这只是思想，我们要怎么去实现呢？为了方便，我们可以设置两个数组，一个用于储存正数，一个用于储存负数。之后以字符串的形式输入数据，通过转换函数将这些数据转换为数组下标，从小到大输出或者从大到小输出的时候再通过反转函数将对应的下标转换为数据输出。这个是第一个问题，那么如何解决第二个问题呢？对于储存数据不能过大的问题，我们可以通过用链表来储存数据。我们给每一段范围的数据设置一个数组下标，然后将所有在这个范围内的数据用链表储存并且按照给定排序规则排序。这种方法比较复杂，在文章结尾笔者会给出这种方法的动画实现。笔者这里并不打算用代码实现这两种改进的桶排序算法，毕竟这不是桶排序的专栏。

**2、插入排序：**  
扑克牌都玩过吧，插入排序就像我们摸扑克牌一样，摸到一张扑克牌，我们就可以将它插入到对应位置，使得已经摸到的牌有序，插入排序正是这种思想：**首先，把数组元素中的第一个元素看成是有序的，从第二个元素开始，我们每次取出一个元素，并且将这个元素插入到相应位置，使得插入后的元素仍有序，直到所有元素都插入完成。**  
我们以 22, 13, 38, 42, 79, 8, 92, 128, 11, 382 这 10 个数字为例，来看一下动画演示：

![SouthEast 2][]

下面上代码：

/*
     * 插入排序：先将数组第一个数字看成有序的，然后逐步将后面的数字插入到前面有序的数字中 
     */
    
    #include <iostream>
    using namespace std;
    const int N = 100010;
    int a[N];
    
    void insertSort(int a[], int n) {
        int v;
        // 对后面的 n-1 个数字进行插入 
        for(int i = 1; i < n; i++) {
            v = a[i];
            int j = i - 1;
            while(j >= 0 && a[j] > v) { // 寻找对应插入位置
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = v;
        }
    }
    
    // 输出数组元素 
    void print(int a[], int n) { 
        for(int i = 0; i < n; i++) {
            if(i) {
                cout << " ";
            }
            cout << a[i];
        }
    }
    
    int main() {
        int n;
        cin >> n; 
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
    
        insertSort(a, n);
        cout << "从小到大插入排序后：" << endl;
        print(a, n);
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 3]

同样的，如果要从大到小排序我们也只需要改一行代码：

while(j >= 0 && a[j] < v) {
        // 寻找对应插入位置

结果：

![这里写图片描述][SouthEast 4]

**3、希尔排序：**  
其实希尔排序算是插入排序的一种变形和改进，只是插入排序是按顺序一个个（元素间隔为 1）比较寻找对应插入位置，而希尔排序是间隔某个数字（这里假设为 g ）来进行比较，随着 g 的变小，希尔排序渐渐完成，当 g 等于 1 的时候，它就是插入排序。下面来看一个动画：

![这里写图片描述][SouthEast 5]

下面是代码：

/*
     * 希尔排序，每次进行间隔为 g（g 为常数） 个元素的插入排序，随着 g 慢慢变小，
     * 排序渐渐完成，当 g 等于 1 的时候它就是插入排序 
     */
    #include <iostream>
    using namespace std;
    const int N = 10000;
    int a[N];
    int g[N];
    
    // 进行元素间隔为 g 的插入排序 
    void insertSort(int a[], int n, int g) { 
        int j, v;
        for(int i = g; i < n; i += g) {
            j = i-g;
            v = a[i];
            while(j >= 0 && a[j] > v) { // 寻找插入位置
                a[j+g] = a[j];
                j -= g;
            }
            a[j+g] = v;
        }
    }
    
    void print(int a[], int n) {
        for(int i = 0; i < n; i++) {
            if(i) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << endl;   
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        /*
         * 获取 G 数组，大量实验发现当间隔递推方法为 G(n+1) = G(n)*3+1 时，
         * 希尔排序时间复杂度最小约为 O(N^1.25) 
         */
        g[0] = 1;
        for(int i = 1; i < n; i++) {  
            g[i] = g[i-1]*3+1;
        }
    
        // 循环进行元素间隔为 g[i] 的插入排序 
        for(int i = n-1; i >= 0; i--) {
            insertSort(a, n, g[i]);
        } 
    
        cout << "排序之后：" << endl;
        print(a, n);
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 6]

同样的，要进行从大到小排序，我们也只需要更改代码中插入排序中寻找插入位置的代码就行了：

while(j >= 0 && a[j] < v) {
        // 寻找插入位置

结果：

![这里写图片描述][SouthEast 7]

**4、冒泡排序：**  
冒泡排序可谓是我们最常用的排序算法了，不过如果不对它进行优化，它的时间复杂度是 O(n\*n)，相对于一些高效的排序算法来说还是比较高的，但是其容易实现，这也是为什么这个算法仍是常用的排序算法之一。  
冒泡排序每次通过比较相邻元素的大小来调整它们的位置，第一趟排序将最大（最小）的元素置于数组开始位置，第二趟排序将第二大（第二小）的元素置于数组的第二个位置。。。直到所有的元素都有序，来看动画演示：

![这里写图片描述][SouthEast 8]

代码：

/*
     * 双重循环，内层循环如果相邻数字不符合顺序，则交换，
     * 外层循环执行一层，数组中就会多一个数字排好序，
     * 外层循环最多执行 n - 1 次，如果某一内层循环内没有交换任意数字，
     * 那么证明数组已经是有序的，则直接退出外层循环 
     */
    #include <iostream>
    using namespace std;
    const int N = 100100;
    int a[N]; 
    
    void bubbleSort(int a[], int n) {
         /*
          * 数组元素交换标志，如果 flag不为 0，证明数组元素交换过，
          * 则可以继续执行循环，否则说明数组已经有序，直接退出 
          */
        int flag = 1; 
        for(int i = 0; flag; i++) {
            flag = 0;
            for(int j = n-1; j > i; j--) {
                if(a[j] < a[j-1]) {
                    swap(a[j], a[j-1]);
                    flag = 1;
                }
            }
        }
    }
    
    void print(int a[], int n) {
        for(int i = 0; i < n; i++) {
            if(i) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << endl;
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
    
        bubbleSort(a, n);
        cout << "从小到大进行冒泡排序：" << endl;
        print(a, n); 
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 9]

如果要从大到小我们只需要改变交换两个数组元素的条件就行了：

if(a[j] > a[j-1])

结果：

![这里写图片描述][SouthEast 10]

**5、选择排序：**  
选择排序在某些地方和冒泡排序相似：第一次选出最大（最小）的元素置于数组开头，第二次选出第二大（第二小）的元素置于数组第二个位置。。。直到所有的元素都有序。不同的是选择排序不是通过相邻元素比较来交换数组元素，好了，来看动画：

![这里写图片描述][SouthEast 11]

代码：

/*
     * 双重循环，外层循环每一次找出一个标准（尺子）， 
     * 内层循环找出从这个标准开始的最小（最大）的数组元素，
     * 并把它放在正确的下表位置，外层循环最多 n - 1 轮 
     */
    #include <iostream>
    using namespace std;
    const int N = 100010;
    
    void selectSort(int a[], int n) {
        int minj;
        for(int i = 0; i < n-1; i++) {
            minj = i;
            // 找出从当前数组下标开始数组中最小的元素 
            for(int j = i+1; j < n; j++) {
                if(a[minj] > a[j]) {
                    minj = j;
                }
            }
            // 如果最小的元素和开始的元素不是同一个元素，那么交换这两个数组元素
            if(minj != i) {  
                swap(a[minj], a[i]);
            }
        }
    }
    
    void print(int a[], int n) {
        for(int i = 0; i < n; i++) {
            if(i) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << endl;
    }
    
    
    int main() {
        int n;
        cin >> n;
        int a[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
    
        selectSort(a, n);
        cout << "从小到大选择排序后：" << endl; 
        print(a, n);
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 12]

如果要从大到小排序，我们也只需要改一行代码：

if(a[minj] < a[j])

结果：

![这里写图片描述][SouthEast 13]

**6、快速排序：**  
快速排序可谓是最快的排序之一了，它的时间复杂度是O(n\*log n)。利用递归的方法进行排序，每次选取一个基数，然后从数组最右边开始扫描，记录第一个大于这个基数的数组元素下标，再从数组左边开始扫描，记录小于这个基数的数组元素的数组元素下标，然后交换这两个数组元素，之后继续扫描和交换，直到当前区间已经扫描完成，之后执行分治递归。下面来看动画演示：

![这里写图片描述][SouthEast 14]

这个动画只演示了一次快速排序的过程，因为快速排序是一个分治递归的过程，下面上代码：

/*
    * 快速排序：利用二分递归的方法，每一次排序设定一个基数，
    * 将比基数大的数字移动到基数的右边，小的移动到基数的左边，基数最后放在中间
    * 然后分治递归缩小范围。直至所有的数据排序完成 
    */
    
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    const int N = 100010;
    int a[N]; 
    
    void quickSort(int a[], int left, int right)    // 快速排序
    {
        if(left >= right)
        {
            return ;
        }
        int i, j, temp, t;
        i = left;
        j = right;
        temp = a[left]; // 设定排序的基数为左边第一个数
    
        while(i < j) // 每次循环结束之后 i 左边的数都小于等于 a[i]，右边的都大于等于 a[i] 
        {
            // 设定的基数为左边第一个数，所以要先从右边开始检索，不然会有 bug
            while(a[j] >= temp && i < j)
            {
                j--;
            }
            a[i] = a[j]; // 把右边比 temp 小的数换去左边 
    
            while(a[i] <= temp && i < j)
            {
                i++;
            }
            a[j] = a[i]; // 把左边比 temp 大的数换去右边 
        }
        /* *
         * 循环结束之后，i 和 j 相等，i 左边的数都小于 a[i]，
         * i 右边的数都大于 a[i] ，将基数放在中间 ，之后执行分治递归 
         */ 
        a[i] = temp; // 把基数放在中间，比基数小的数在左边，比基数大的数在右边 
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }
    
    int main()
    {
        int n;
        cin >> n;
        srand((unsigned int) time(NULL)); // 布随机数种子 
        for(int i = 0; i < n; i++)
        {
            a[i] = rand() % n; // 产生随机数 
            cout << a[i] << " ";
        }
        cout << endl;
    
        quickSort(a, 0, n - 1);
        cout << "排序后：" << endl;
        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

这里我直接采用随机生成数字，懒得一个个输入了，效率太低。

结果：

![这里写图片描述][SouthEast 15]

那么如果要从大到小呢，只需要改两个地方的代码就行了：

while(a[j] <= temp && i < j)
    {
        j--;
    }
    while(a[i] >= temp && i < j)
    {
        i++;
    }

结果：

![这里写图片描述][SouthEast 16]

**7、归并排序：**  
其实归并排序和快速排序有点像，因为归并排序也是通过分治递归来实现的，但是归并排序是先通过分治递归将所有的数组元素都分成一个个独立的元素个体，之后通过合并函数按照从小到大（从大到小）来进行和并，直到所有的元素都合并了。来看动画演示：

![SouthEast 17][]

这个动画也只演示了一次归并过程：即最后的那一次归并，通过这次归并之后，整个数组已经变为有序了，对于其余区间更小的归并也是一样的。下面上代码：

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    const int N = 100010;
    int a[N]; // 储存待排序数的数组
    int b[N]; // 合并两组数用的中间数组
    
    // 合并左右两边的数组元素，数组元素的交换在这里进行 
    void merge(int left, int mid, int right) {
        int i = left;
        int j = mid+1;
        int index = 0;
        // 进行左右两边的元素合并 
        for(; i <= mid && j <= right; ) {
            if(a[i] <= a[j]) { // 从小到大排序 
                b[index++] = a[i++];
            } else {
                b[index++] = a[j++];
            }
        } 
        // 当有一边中的元素全部用完之后，将剩下的那一边元素直接复制 
        while(i <= mid) {
            b[index++] = a[i++];
        }
        while(j <= right) {
            b[index++] = a[j++];
        }
        // 将合并好了的数组元素复制到原来的数组中 
        for(int k = 0; k < index; k++) {
            a[left++] = b[k];
        }
    }
    
    // 递归进行反复合并，实现排序，数组下标范围：[left, right] 
    void mergeSort(int left, int right) {
        // 当剩下的未合并的元素至少为两个的时候，合并这两个元素
        if(left < right) { 
            int mid = (right + left) / 2;
            mergeSort(left, mid);
            mergeSort(mid+1, right);
            merge(left, mid, right);
        }
    }
    
    void print(int a[], int n) {
        for(int i = 0; i < n; i++) {
            if(i) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << endl;
    }
    
    int main() {
        int n;
        cin >> n;
        srand((unsigned int) time(NULL)); // 布随机数种子 
        for(int i = 0; i < n; i++)
        {
            a[i] = rand() % n; // 产生随机数 
            cout << a[i] << " ";
        }
        cout << endl;
    
        mergeSort(0, n-1);
        cout << "归并排序之后：" << endl; 
        print(a, n);
    
        return 0;
    }

结果：

![这里写图片描述][SouthEast 18]

如果要从大到小排序，改一个字符就行了：

if(a[i] >= a[j]) { // 从大到小排序 
        b[index++] = a[i++];
    } else {
        b[index++] = a[j++];
    }

**8、堆排序：**  
堆排序是在堆这种数据结构上延伸出的一种排序方法，如果对堆数据结构还不熟的小伙伴，可以参考这篇文章：[http://blog.csdn.net/hacker\_zhidian/article/details/60801415][http_blog.csdn.net_hacker_zhidian_article_details_60801415]  
如果是从小到大进行堆排序，那么我们需要建立最小堆，然后不断取出堆顶元素并对堆进行维护，直到堆为空。  
如果是从大到小进行堆排序，那么我们需要建立最大堆，然后不断取出堆顶元素并对堆进行维护，直到堆为空。下面上代码：

#include <iostream>
    #include <cstdlib>
    #include <ctime> 
    using namespace std;
    const int N = 10010;
    int a[N], b[N];
    
    // 将堆中以第 i 个节点为根节点的子完全二叉树调整顺序使得其为一个最大堆
    void maxHeap(int a[], int i, int n) {  
        int l, r, large = i;
        l = 2 * i;
        r = l + 1;
        if(l <= n && a[l] > a[large]) {
            large = l;
        }
        if(r <= n && a[r] > a[large]) {
            large = r;
        }
        if(i != large) {
            swap(a[i], a[large]);
            maxHeap(a, large, n);
        }
    }
    
    // 将堆中以第 i 个节点为根节点的子完全二叉树调整顺序使得其为一个最小堆
    void minHeap(int a[], int i, int n) {
        int l, r, small = i;
        l = 2 * i;
        r = l + 1;
        if(l <= n && a[small] > a[l])  {
            small = l;
        }
        if(r <= n && a[small] > a[r]) {
            small = r;
        }
        if(small != i) {
            swap(a[small], a[i]);
            minHeap(a, small, n);
        }
    } 
    
    // 堆排序，从大到小 
    void heapSortBigToSmall(int a[], int n) {
        int nodeSum = n;
        for(int i = 1; i <= nodeSum; i++) {
            if(i != 1) {
                cout << " ";
            }
            cout << a[1];
            // 将堆顶已经输出的元素丢弃，并且将最后一个元素提到堆顶 
            a[1] = a[n--]; 
            // 重新对整个完全二叉树进行顺序调整，使得其仍为最大堆 
            maxHeap(a, 1, n); 
        }
        cout << endl;
    }
    
    // 堆排序，从小到大 
    void heapSortSmallToBig(int a[], int n) {
        int nodeSum = n;
        for(int i = 1; i <= nodeSum; i++) {
            if(i != 1) {
                cout << " ";
            }
            cout << a[1];
            // 将堆顶已经输出的元素丢弃，并且将最后一个元素提到堆顶
            a[1] = a[n--];
            // 重新对整个完全二叉树进行顺序调整，使得其仍为最小堆 
            minHeap(a, 1, n);
        }
        cout << endl;
    } 
    
    int main() {
        int n;
        cin >> n;
    
        srand((unsigned int) time(NULL)); // 布随机数种子 
        for(int i = 1; i <= n; i++)
        {
            a[i] = rand() % n; // 产生随机数
            b[i] = a[i];
            cout << a[i] << " ";
        }
        cout << endl;
    
        cout << "堆排序，从小到大：";
        for(int i = n/2; i >= 1; i--) {
            minHeap(a, i, n);
        }
        heapSortSmallToBig(a, n);
    
        cout << "堆排序，从大到小：";
        for(int i = n/2; i >= 1; i--) {
            maxHeap(b, i, n);
        }
        heapSortBigToSmall(b, n);
    
    
        return 0;
    }

结果：  
![这里写图片描述][SouthEast 19]

Ok，耗费了近一天的时间，终于总结完了，这里要说一下关于这些排序算法的时间复杂度：  
桶排序：O(n)，看起来很低，但是本文中的代码适用场合很少，必须改进才能适用于更多的场合。  
插入排序：O(n\*n)，看具体的数字元素，有时候效率很高，有时候很低。  
希尔排序 ：事件复杂度与 G 数组和具体的数字元素有关。  
冒泡排序：看具体情况，一般是O(n\*n)。  
选择排序：O(n\*n)  
快速排序：O(n\*log n)。  
归并排序：O(n\*log n)。  
堆排序：O(n\*log n)

这里说一下，归并排序对于求逆序数很有效（冒泡排序也可以，但是时间复杂度高）

[这里给出这八个排序算法的Flash动画演示下载链接][Flash]

好了。终于写完了，如果博客中有什么不正确的地方，请多多指点，如果觉得我写的不错，那么请点个赞支持我吧。

谢谢观看。。。

[SouthEast]: /images/20220708/393faad179ea440683f075ae2273c39a.png
[SouthEast 1]: /images/20220708/612041fa90104ab6a9d25e72b305124b.png
[SouthEast 2]: /images/20220708/925e8bd202ea455ea5519e6f26baab49.png
[SouthEast 3]: /images/20220708/ded4fac8b4964421b78bfae712f2f58c.png
[SouthEast 4]: /images/20220708/61b1605b629e46919990bfb10fd2d9e3.png
[SouthEast 5]: /images/20220708/9e5f13b1575f434782766bf5b6737330.png
[SouthEast 6]: /images/20220708/cc7ef7d14bd941a8864b7611211ccbee.png
[SouthEast 7]: /images/20220708/79821c7910f44a6c9bd6f248d4ee4f3e.png
[SouthEast 8]: /images/20220708/2d4876035c034487a2ed90e1b56fdec1.png
[SouthEast 9]: /images/20220708/25e897e1d35848839cf19246b0cffda5.png
[SouthEast 10]: /images/20220708/109afd6822fe4c40a8343ba279a07a0c.png
[SouthEast 11]: /images/20220708/846ff8ba097842e39e7d9762c0e7b986.png
[SouthEast 12]: /images/20220708/085d5260d1e74e5887a79162978c4585.png
[SouthEast 13]: /images/20220708/44728cc151814128b0ec3db6a17220dd.png
[SouthEast 14]: /images/20220708/4d7f67a633cd423082c2f553f16451ec.png
[SouthEast 15]: /images/20220708/494555ac6e4d417cab8d13fa5c8117c0.png
[SouthEast 16]: /images/20220708/d0805b65f82d4980a71de92319108c02.png
[SouthEast 17]: /images/20220708/4c94f433e95945c0866161a83e999795.png
[SouthEast 18]: /images/20220708/2b20a5fd5b394f06a10a894b27ba60cb.png
[http_blog.csdn.net_hacker_zhidian_article_details_60801415]: http://blog.csdn.net/hacker_zhidian/article/details/60801415
[SouthEast 19]: /images/20220708/afaf8e3bd90c434d867113c43ae8a59c.png
[Flash]: http://download.csdn.net/detail/hacker_zhidian/9778634