排序总结(C++)

女爷i 2022-02-26 13:54 148阅读 0赞

# 冒泡排序 #

## 基础知识 ##

*  冒泡排序：比较相邻的元素。如果第一个比第二个大，就交换他们两个。每次最外面的循环，得到一个最小值。
 *  时间复杂度：$O(n^2)$

> [https://blog.csdn.net/guoweim...][https_blog.csdn.net_guoweim...]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    void BubbleSort(int a[], int n){
        for(int i=0; i<n-1; i++){//控制外循环次数
            for(int j=0; j<n-1-i; j++){
                if(a[j+1] < a[j]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        /*
            for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(a[j] < a[i]){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        */
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        BubbleSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

## ![clipboard.png][] ##

# 快速排序 #

## 基础知识 ##

*  快速排序采用的是**分治**的思想。
 *  基本思路：
    
     *  在数据集之中，选择一个元素作为“基准”。
     *  所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”的右边。
     *  对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
 *  注意：
    
     *  要先从右边哨兵开始寻找（这样做的是保证哨兵i和哨兵j共同指向的元素比“基准”小）
     *  交换的前提是：哨兵i指向的元素比“基准”大，哨兵j指向的元素比“基准”小，且哨兵i比哨兵j小。
 *  算法复杂度：$O(nlog\_2n)$

![clipboard.png][clipboard.png 1]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    void quickSort(int a[], int left, int right){
        if(left>right)  return;
        int temp = a[left];
        int i = left;
        int j = right;
        while(i != j){
        //注意顺序，保证右边哨兵最先开始
            while(i<j && a[j]>=temp){
                j--;
            }
            while(i<j && a[i]<=temp){
                i++;
            }
            if(i<j){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    
        a[left]  = a[i];
        a[i] = temp;
    
        quickSort(a,left, i-1);
        quickSort(a, i+1, right);
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        quickSort(a, 0, size-1);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

# 插入排序 #

## 基本知识 ##

*  插入排序:将一个记录插入到已排序好的有序表中，从而得到一个新的有序序列
 *  时间复杂度：$O(n^2)$

![clipboard.png][clipboard.png 2]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    int temp[10];
    
    void InsertSort(int a[] , int n){
        for(int i=0; i<n; i++){
            for(int j=i; j>0; j--){
                if(a[j]<a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        InsertSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

![clipboard.png][clipboard.png 3]

--------------------

# Shell排序 #

## 基础知识 ##

*  Shell排序是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序。
 *  对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
 *  时间复杂度：$O(n^\{1.3\})$

![clipboard.png][clipboard.png 4]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    
    void ShellSort(int a[], int n){
        int i,j,gap;
        for(gap = n/2; gap>0; gap /=2){
        //以下是快速插入排序
            for(i=gap; i<n; i++){
                for(j=i; j>0; j -=gap){
                    if(a[j-gap]>a[j]){
                        int temp = a[j-gap];
                        a[j-gap] = a[j];
                        a[j] = temp;
    
                    }
                }
            }
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        ShellSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

![clipboard.png][clipboard.png 5]

--------------------

# 选择排序 #

## 基础知识 ##

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
 *  时间复杂度：$O(n^2)$

![clipboard.png][clipboard.png 6]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    void SelectSort(int a[], int n){
        for(int i=0; i<n-1; i++){//每次循环，寻找到i位置最小的值
            int index = i;
            //index用来记录最小元素的下标
            for(int j=i+1; j<n; j++){
                if(a[j] < a[index]){
                    index = j;
                }
            }
    
            if(index != i){
                int temp = a[index];
                a[index] = a[i];
                a[i] = temp;
            }
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        SelectSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

--------------------

# 堆排序 #

## 基础知识 ##

*  堆排序是一种树形选择排序，在排序过程中可以把元素看成是一颗完全二叉树，每个节点都大（小）于它的两个子节点。
 *  当每个节点都大于等于它的两个子节点时，就称为大顶堆，也叫堆有序； 当每个节点都小于等于它的两个子节点时，就称为小顶堆。
 *  完全二叉树的规律：
    
     *  索引为i的左孩子的索引是 (2\*i+1);
     *  索引为i的左孩子的索引是 (2\*i+2);
     *  索引为i的父结点的索引是 (i-1)/2;
 *  算法思想：
    
     *  将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
     *  将根节点与尾节点交换并输出此时的尾节点
     *  将剩余的n -1个节点重新进行堆有序化
     *  重复步骤2，步骤3直至构造成一个有序序列
 *  时间复杂度：$O(nlog\_2n)$

![clipboard.png][clipboard.png 7]  
![clipboard.png][clipboard.png 8]  
![clipboard.png][clipboard.png 9]  
![clipboard.png][clipboard.png 10]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    void swap(int a[], int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    void heapAdjust(int a[], int i, int len){//保证根节点最大
        int left, right, child;
    
        while(2*i+1 <= len){判断当前节点有无左节点，保证当前节点不是叶子节点
            left = 2*i+1;        
            right = left+1;
            child = left;
            if(left<len && a[left]<a[right]){
                child++;//左右子节点的最大值
            }
            if(a[i]<a[child]){//当前节点比孩子节点要小，需要调整位置
                swap(a, i, child);
            }
            else
                break;
    
            i = child;
        }
    }
    
    void heapSort(int a[], int n){
        for(int i=(n-1)/2; i>=0; i--){//从最后一个非叶子节点开始构建大顶堆，以上图例子(8-1)/2=3,也就是说a[3]以后都是叶子节点。
            heapAdjust(a, i, n);
        }
    
        n = n-1;//因为下标从0开始，所以尾节点下标是n-1
        while(n>0){
            swap(a, 0, n);//交换根节点与尾节点
            n--;//把尾节点排除在外
            heapAdjust(a, 0, n);
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        heapSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

--------------------

# 归并排序（合并排序） #

## 基础知识 ##

*  归并排序采用的是分治的思想；
 *  归并操作即将两个已经排序的序列合并成一个序列的操作；
 *  基本实现：
    
     *  分解：将当前区间一分为二，并递归的对左右子区间进行分解，直到子区间长度为1；
     *  合并：将两个有序的子区间合并成一个有序的区间。  
        ![clipboard.png][clipboard.png 11]
 *  时间复杂度：$nlogn$（理解：分解可以理解为n个节点的完全二叉树层数为$log\_2n$,即$O(logn)$;合并可以理解为每层都需要扫描比较一遍所有数据，所以为$O(n)$）

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    int temp[10];
    
    void Merge(int a[], int start, int mid, int end, int temp[]){
        int pb = 0;
        int p1 = start;
        int p2 = mid+1;
    
        while(p1<=mid && p2<=end){
            if(a[p1] < a[p2]){
                temp[pb++] = a[p1++];
            }
            else{
                temp[pb++] = a[p2++];
            }
        }
    
        while(p1<=mid){
            temp[pb++] = a[p1++];
        }
        while(p2<=end){
            temp[pb++] = a[p2++];
        }
    
        for(int i=0; i<end-start+1; i++){
            a[start+i] = temp[i];
        }
    }
    
    void MergeSort(int a[], int start, int end, int temp[]){
        if(start<end){
            int mid = start + (end - start)/2;
    
            MergeSort(a, start, mid, temp);
            MergeSort(a, mid+1, end, temp);
    
            Merge(a, start, mid, end, temp);
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        MergeSort(a, 0, size-1, temp);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

![clipboard.png][clipboard.png 12]

# 桶排序 #

## 基础知识 ##

*  时间复杂度：$O(n+K)$
 *  工作的原理是将数组分到有限数量的桶里。每个桶再个别排序。
 *  桶排序使用线性时间，并不是比较排序。

![clipboard.png][clipboard.png 13]

## 代码实现 ##

//一种最简单的桶排序
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int a[10] = {3,2,7,5,1,9,6,4,0,8};
    
    void bucketSort(int a[], int size, int max){
    //size是待排序数组的大小；max是待排序数组中的最大值
        int buckets[max];
        memset(buckets, 0, max* sizeof(int));
    
        for(int i=0; i<size; i++){
            buckets[a[i]]++;
        }
        int i,j;
        for(i=0,j=0; i<max; i++){
            while(buckets[i]>0){
                buckets[i]--;
                a[j] = i;
                j++;
    
            }
        }
    }
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        bucketSort(a, size, 10);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

--------------------

# 计数排序 #

## 基础知识 ##

*  计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为$O(n+k)$，其中k是整数的范围。快于任何比较排序算法。
 *  它是基数排序的一个关键部分。

![clipboard.png][clipboard.png 14]

## 代码实现 ##

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int a[6] = {0,7,2,6,0,8};
    
    int getMax(int a[], int size){
        int max = a[0];
        for(int i=1; i<size; i++){
            if(max<a[i]){
                max = a[i];
            }
        }
        return max;
    }
    void countSort(int a[], int size){
        int max = getMax(a, size)+1;
        int output[size];
        memset(output, 0, size* sizeof(int));
        int buckets[max];
        memset(buckets, 0, max* sizeof(int));
    
        for(int i=0; i<size; i++){
            buckets[a[i]]++;
        }
        for(int i=0; i<max; i++){
            buckets[i+1] += buckets[i];
        }
        cout<<buckets[max]<<endl;
        for(int i=0; i<size; i++){
            output[buckets[a[i]]-1] = a[i];
            buckets[a[i]]--;
        }
        for (int i = 0; i < size; ++i) {
            a[i] = output[i];
        }
    }
    
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        countSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

# 基数排序 #

## 基础知识 ##

*  主要思想：将所有待比较数值(注意,必须是正整数)统一为同样的数位长度，数位较短的数前面补零。 然后，从最低位开始, 依次进行一次稳定排序。（从低位开始的原因是：如果要从高位排序，那么次高位的排序会影响高位已经排好的大小关系。在数学中， 数位越高，数位值对数的大小的影响就越大。）

![clipboard.png][clipboard.png 15]

*  举个例子：

![clipboard.png][clipboard.png 16]  
![clipboard.png][clipboard.png 17]

## 代码实现 ##

#include <iostream>
    using namespace std;
    
    int a[10] = {13,2,90,165,211,768,89,889,0,28};
    
    int getMax(int a[], int size){
        int max = a[0];
        for(int i=1; i<size; i++){
            if(max<a[i]){
                max = a[i];
            }
        }
        return max;
    
    }
    
    void countSort(int a[], int size, int exp){
        int output[size];//注意这是动态数组，在堆上分配，需要delete。
        for(int i=0; i<size; i++){
            output[i] = 0;
        }
        /*
         * int output[size];
         *
         * delete output;
         * */
    
        int buckets[10]={0};
    
        for(int i=0; i<size; i++){
            buckets[(a[i]/exp)%10]++;
        }
    
        for(int i=0; i<10; i++){
            buckets[i+1] +=buckets[i];
        }
    
        for(int i=size; i>=0; i--){/*这里需要注意，从大开始递减。
        原因是：buckets[(a[i]/exp)%10](临时数组的下标)的值是递减的；
        第一轮循环以后，个位值大的在数组下标大。因此相同十位的数，数组下标大的先进临时数组。*/
            output[buckets[(a[i]/exp)%10]-1] = a[i];//因为索引是从0开始的，所以要减1
            buckets[(a[i]/exp)%10]--;
        }
    
        for(int i=0; i<size; i++){
            a[i] = output[i];
        }
    
        //delete output;
    }
    
    void radixSort(int a[], int size){
        int exp;
        int max = getMax(a, size);
        for(exp=1; max/exp>0; exp *= 10){
            countSort(a,size,exp);
        }
    }
    
    int main() {
        int size = sizeof(a)/sizeof(a[0]);
        cout<<"........before sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
    
        radixSort(a, size);
        cout<<"........after sort........"<<endl;
        for(int i=0; i<size; i++){
            cout<<a[i]<<",";
        }
        cout<<endl;
        return 0;
    }

--------------------

# 总结 #

## 内排序与外排序 ##

*  内排序：指在排序期间数据对象全部存放在内存的排序。以上讲的都是内部排序。
 *  外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

## 基于比较的排序 ##

*  基于比较的排序：插入排序，选择排序，交换排序，归并排序。基于比较的排序算法是不能突破$O(nlog\_2n)$的。n个数有$n!$个可能的排列情况，也就是说基于比较的排序算法的判定树有$n!$个叶子结点，比较次数至少为$log(n!)=O(nlogn)$(斯特林公式)。
 *  基于线性的排序（非比较排序）：计数排序，桶排序，基数排序。不受$O(nlog\_2n)$$的影响。其时间复杂度依赖于数据的范围。非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制等。

![clipboard.png][clipboard.png 18]

> 参考： [https://www.cnblogs.com/zyb42...][https_www.cnblogs.com_zyb42...]

[https_blog.csdn.net_guoweim...]: https://blog.csdn.net/guoweimelon/article/details/50902597
[clipboard.png]: /images/20220226/85f3eaa8d5af4b14a90d6097eb22eeca.png
[clipboard.png 1]: /images/20220226/fdec088196084788bba16f7d3cb5b05d.png
[clipboard.png 2]: /images/20220226/be0f94795beb4793ab3c9f1bc21dbee3.png
[clipboard.png 3]: /images/20220226/5574ebbb79d941ebbe8089d8a3feff32.png
[clipboard.png 4]: /images/20220226/4eeabd3868b54ba19b8b00bba2907acb.png
[clipboard.png 5]: /images/20220226/c15812d977a34073816835ce70be37f3.png
[clipboard.png 6]: /images/20220226/f717e7c094bc491780b614d75148c3cf.png
[clipboard.png 7]: /images/20220226/3cd72b38979745669ba0a5daae984769.png
[clipboard.png 8]: /images/20220226/9e97561506b5441c996836e119015cb9.png
[clipboard.png 9]: /images/20220226/6f2c8d0f01b443d0a2c8010d32c22232.png
[clipboard.png 10]: /images/20220226/d42f81d97598409787ee27c5b597c2ad.png
[clipboard.png 11]: /images/20220226/87ce1b5754904681a6638e07d051bde6.png
[clipboard.png 12]: /images/20220226/8f45301adc5346f3894928f1a04996db.png
[clipboard.png 13]: /images/20220226/27e83f5d0633462e80cf29788e7db07d.png
[clipboard.png 14]: /images/20220226/27377b855e334f2bb89c9b5fc3751d7e.png
[clipboard.png 15]: /images/20220226/5fe6f64520aa4dc8a4805c28d3cb887b.png
[clipboard.png 16]: /images/20220226/a9d1dee975fa412f96ddc9c30de73765.png
[clipboard.png 17]: /images/20220226/748e327527c3431f8c0994b392d39f91.png
[clipboard.png 18]: /images/20220226/64d8f0df32fd40c0938b800ce087fc6b.png
[https_www.cnblogs.com_zyb42...]: https://www.cnblogs.com/zyb428/p/5673738.html