【总结】经典排序算法(C++）

古城微笑少年丶 2022-05-13 15:14 159阅读 0赞

最近在学习算法，趁这个机会总结一些算法。慢慢更新，欢迎交流探讨。

参考书籍：《算法导论》

排序：

输入：n个数

输出：有序（从大到小、从小到大）序列

**一、插入排序**

做排序的都需要做遍历，而插入排序，顾名思义，就是插队。

不必多说，给个案例体会一下:

*输入*：5 4 3 2 1

*处理*：

*     4 5 3 2 1
 *     3 4 5 2 1
 *     2 3 4 5 1
 *     1 2 3 4 5

*输出*：1 2 3 4 5

*输入*：6 8 2 4 5

*处理*：

*  6 8 2 4 5
 *  2 6 8 4 5
 *  2 4 6 8 5
 *  2 4 5 6 8

代码如下（测试）：

（排序部分第11-16行）；

input：输入数组元素数n;输入数组元素a\[i\];输入n=0代码结束；

#include<iostream>
    #include<string.h>
    using namespace std;
    int main()
    {
        int n,key,i,j,a[100];
        while (cin>>n,n!=0)
        {
            for(int i=0;i<n;i++)
            cin>>a[i];
            for(int j=1;j<n;j++)
            {
                key=a[j];
               for(i=j-1;i>=0&&a[i]>key;i--)
                   a[i+1]=a[i];
                a[i+1]=key;
            }
            for(int k=0;k<n;k++)
            {
                cout<<a[k]<<" ";
            }
            cout<<endl;
        }
    }

**二、选择排序：**

*规则*：首先找到数组的最小数，与a\[0\]交换；循环下去，找到第n小的数，与数组的第n个数交换；

*案例*：

*输入*： 5 4 9 8 3

*处理*：

*  3 4 9 8 5
 *  3 4 9 8 5
 *  3 4 5 8 9
 *  3 4 5 8 9

*输出*：3 4 5 8 9

代码如下：

#include<iostream>
    using namespace std;
    int main()
    {
        int n,a[100],key,x;
        while(cin>>n,n!=0)
        {
            for(int i=0;i<n;i++)
                cin>>a[i];
            for(int i=0;i<n;i++)
        {
           key=a[i];
           x=i;
           for(int j=i+1;j<n;j++)
           {
               if(a[j]<key)
               {
                   key=a[j];
                   x=j;
               }
           }
           int tem=a[i];
           a[i]=a[x];
           a[x]=tem;
        }
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        }
    }

**三、归并排序（MERGE SORT）**

规则:将原数组分解成n个子序列，再对子序列递归地进行排序。其中，单个元素被视为是已经排列好的。

说明：这个算法在下根据课本先做了两个函数，第一个是做对数组的分割，其次是对数组的排序；而在主函数中，用了srand产生100以内的随机数。

案例：

输入：5 2 4 7 1 3 2 6

处理：分割：5     2    4    7    1    3    2    6

合并：2 5    4 7    1 3     2 6

再合并：2 4 5 7    1 2 3 6

再合并：1 2 3 4 5 6 7

代码如下：

#include <iostream>
    #include <time.h>
    #include <stdlib.h>
    using namespace std;
    
    void Merge(int *_Array, int p, int q, int r) {// p:第0个;r:第n-1个数,q:第(r + p) / 2个数
        int len1 = q - p + 1;
        int len2 = r - q;
        int *L = new int[len1 + 1];//用动态数组储存左边的数
        int *R = new int[len2 + 1];//用动态数组储存右边的数
    
        for (int i = 0; i < len1; i++) {// 把Array数组左边的数放入L数组
            L[i] = _Array[p + i];
        }
    
        for (int j = 0; j < len2; j++) {// 把Array数组右边的数放入R数组
            R[j] = _Array[q + 1 + j];
        }
        L[len1]=R[len2]=INT_MAX;    //定义无穷大
        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] < R[j]) {//小的放左边，大的放右边
                _Array[k] = L[i];
                i++;
            }
            else {
                _Array[k] = R[j];
                j++;
            }
        }
    }
    
    void MergeSort(int _Array[], int p, int r) {
        if (p < r) {//p:第0个;r:第n-1个数。数组至少要有两个数据
            int q;
            q = (r + p) / 2;//拆分两组
            MergeSort(_Array , p , q);//拆分第0个到第 (r + p) / 2个 ，即拆分左半部分
            MergeSort(_Array , q+1 , r);//拆分第(r + p) / 2个到第r个 ，即拆分右半部分
            Merge(_Array , p , q , r);//调用合并函数，从第0个到第n-1个排好
        }
    }
    
    int main() {
        int n;
        cout<<"请输入数组的元素数：";
        cin >> n;
        cout << endl;
        int *Array = new int[n];
        cout << "随机数组为：";
        srand((unsigned)time(0));
    
        for (int i = 0; i < n; i++) {
            Array[i] =  (rand()%(100-0+1))+0;
            //cin>>;
            cout<<Array[i]<<"  ";
        }
        cout<<endl;
    
        MergeSort(Array,0,n-1);
    
        cout << "排序后的数组为：";
        for(int j  = 0;j<n;j++){
            cout<<Array[j]<<"  ";
        }
        return 0 ;
    }

**四、快速排序法**

*  介绍：

快速排序的最坏情况（输入数从小到大或从大到小）的运行时间为cita（n^2），但快速排序是用于排序的最佳实用选择，因为其平均性能相当好，一般的运行时间为cita(nlgn)，且cita(nlgn)中的常数因子很小。此外，快速排序还可以就地排序，在虚存环境中也能很好运行。

同归并排序类似地，快速排序也是基于分治法的，

*  divide 分解：将数组A\[p....r\]划分为两个子数组A\[p..q-1\]和A\[q...r\]排序，使得A\[p...q-1\]<=A(q)<=A\[q+1...r\]
 *  conquer解决：通过递归调用Quicksort,对子数组A\[p...q-1\]和A\[q...r\]排序。
 *  combine.合并：此步可忽略，因为A\[p...r\]已经排序。
 *  原理：

![20181115205603573.png][]

*  案例：（来自算法导论）仅partition部分：

![20181115205912645.png][]

![20181115210233500.png][]

![20181115210357868.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 5][]

代码如下：

#include<iostream>
    #include<time.h>
    #include<stdlib.h>
    using namespace std;
    int Partition(int *a,int p,int q)        //函数：使得<x的数在X的左边，>x的数在x的右边
    {
        int x=a[p];
        int i=p;
        for(int j=p+1;j<=q;j++)
        {
            if(a[j]<=x)
            {
                i++;
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        int temp=a[i];
        a[i]=a[p];
        a[p]=temp;
        return i;
        }
    void QuickSort(int *a,int p,int q)
    {
        if(p<q)            //递归停止的信号p>=q
        {
            int r=Partition(a,p,q);
            QuickSort(a,p,r-1);
            QuickSort(a,r+1,q);
        }
    }
    int main()
    {
        int n;
        cout<<"请输入";
        cin >> n;
        cout << endl;
        int *Array = new int[n];
        cout << "产生的随机数组为：";
        srand((unsigned)time(0));
        for (int i = 0; i < n; i++) {
            Array[i] =  (rand()%(100-0+1))+0;
            cout<<Array[i]<<"  ";
        }
        cout<<endl;
    
        QuickSort(Array,0,n-1);
    
        cout << "排序后的数组为：";
        for(int j  = 0;j<n;j++){
            cout<<Array[j]<<"  ";
        }
        return 0;
    }

快速排序的最佳情况运行时间为cita(nlgn);

快速排序的最坏情况运行时间为cita(n^2)   //即是划分得不平衡，如划分为n-1与1；

,而插入排序的最坏情况运行时间为cita(n),这时候快速排序真是徒负虚名。这归咎于我们选取的x的位置被固定住了，所以下面的随机快速排序就是一种优化。

**五、随机快速排序**

作为一种优化，其实也是用一个随机种子生产随机数，随机抽取某一个数做为x,再调用partition函数，仅仅加了一个函数，再做一点点修改，代码如下：

#include<iostream>
    #include<time.h>            //添加文件
    #include<stdlib.h>
    using namespace std;
    int Partition(int *a,int p,int q)
    {
        int x=a[p];
        int i=p;
        for(int j=p+1;j<=q;j++)
        {
            if(a[j]<=x)
            {
                i++;
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        int temp=a[i];
        a[i]=a[p];
        a[p]=temp;
        return i;
        }
    int Random_Partition(int* a,int p,int q)    //产生随机数做下标，使得中间数是随机的数
    {
        int i=rand()%(q-p)+0;
        int temp=a[i];
        a[i]=a[q];
        a[q]=temp;
        return Partition(a,p,q);
    }
    void QuickSort(int *a,int p,int q)
    {
        if(p<q)
        {
            int r=Random_Partition(a,p,q);
            QuickSort(a,p,r-1);
            QuickSort(a,r+1,q);
        }
    }
    int main()
    {
        int n;
        cout<<"请输入";
        cin >> n;
        cout << endl;
        int *Array = new int[n];
        cout << "产生的随机数组为：";
        srand((unsigned)time(0));
        for (int i = 0; i < n; i++) {
            Array[i] =  (rand()%(100-0+1))+0;
            cout<<Array[i]<<"  ";
        }
        cout<<endl;
    
        /*cout<<"请输入数组："<<endl;
        for(int i=0;i<n;i++)
            cin>>Array[i];*/
        QuickSort(Array,0,n-1);
        cout << "返回的下标为："<<Partition(Array,0,n-1)<<endl;
        cout << "排序后的数组为：";
        for(int j  = 0;j<n;j++){
            cout<<Array[j]<<"  ";
        }
        delete []Array ;
        return 0;
    }

**六、计数排序法**

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    void Counting_Sort(int *a,int *b,int n,int *c,int m)
    {
        for(int i=0;i<m;i++)
            c[i]=0;
        for(int j=0;j<n;j++)
            c[a[j]]++;
        for(int i=1;i<m;i++)
            c[i]+=c[i-1];
        for(int j=n-1;j>=0;j--)
        {
            b[c[a[j]]-1]=a[j];
            c[a[j]]--;
        }
    }
    int main()
    {
        int n,m;
        cout<<"input an number as the size of the matrix:"<<endl;
        cin>>n;
        cout<<"input the largest number you hope:"<<endl;
        cin>>m;
        int *a = new int[n];
        int *b = new int[n];
        int *c = new int[m];
        cout<<"here is the matrix:"<<endl;
        srand((unsigned)time(0));
        for(int i=0;i<n;i++)
        {
            a[i]=rand()%(m+1)+0;
            cout<<a[i]<<" ";
        }
        cout<<endl;
        /*写成函数。。
        for(int i=0;i<m;i++)//注意这些循环的界限
            c[i]=0;
        for(int j=0;j<n;j++)
            c[a[j]]++;
        for(int i=1;i<m;i++)
            c[i]+=c[i-1];
        for(int j=n-1;j>=0;j--)
        {
            b[c[a[j]]-1]=a[j];
            c[a[j]]--;
        }*/
        Counting_Sort(a,b,n,c,m);
        cout<<"and the result is:"<<endl;
        for(int i=0;i<n;i++)
            cout<<b[i]<<" ";
        cout<<endl;
        delete []a;                 //new之后最好delete掉
        delete []b;
        delete []c;
    }

**七、基数排序法**

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    int GetMax(int a[],int n)
    {
        int max=a[0];
        for (int i=0;i<n;i++)
            max= a[i]>max?a[i]:max;
        return max;
    }
    void CountingSort(int a[],int n,int exp)
    {
        int b[n]={0};
        int c[10]={0};
        for(int i=0;i<n;i++)
            c[(a[i]/exp)%10]++;
        for(int i=1;i<10;i++)
            c[i]+=c[i-1];
        for(int j=n-1;j>=0;j--)
        {
            b[c[(a[j]/exp)%10]-1]=a[j];
            c[(a[j]/exp)%10]--;
        }
        for(int i=0;i<n;i++)
            a[i]=b[i];
    }
    void RadixSort(int a[],int n)
    {
        int exp;
        int max=GetMax(a,n);
        for(exp=1;max/exp>0;exp*=10)
            CountingSort(a,n,exp);
    }
    int main()
    {
        int n,m;
        cout<<"please input a numb as the length of matrix:"<<endl;
        cin>>n;
        cout<<"please input the largest numb you hope:"<<endl;
        cin>>m;
        int *a = new int [n];
        srand((unsigned)time(0));
        for(int i=0;i<n;i++)
        {
            a[i]=rand()%m;
            cout<<a[i]<<" ";
        }cout<<endl;
        RadixSort(a,n);
        for(int i=0;i<n;i++)
        {
            cout<<a[i]<<" ";
        }cout<<endl;
        delete []a;
        return 0;
    }

[20181115205603573.png]: /images/20220504/71b13a6db23a478c88296827f002bd6d.png
[20181115205912645.png]: /images/20220504/16058976572c4da08c9dc3b0df80b6f0.png
[20181115210233500.png]: /images/20220504/b7be27ad1da845679253a16cd2c1dfbe.png
[20181115210357868.png]: /images/20220504/41e59a0884ac425bb45ddd32296775b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70]: /images/20220504/efa2dbf887824ed59a6462b348b8ef92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 1]: /images/20220504/0b8e4c6371784a16ad451421ed90981a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 2]: /images/20220504/a6d75b6c6fc341a4bdc55fca4f192b94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 3]: /images/20220504/1e485c23cd494cf189e4e326ae3769f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 4]: /images/20220504/0a556f7fe9f54f1ea0f6c6c00535b8c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjI3MjM1_size_16_color_FFFFFF_t_70 5]: /images/20220504/403f3f6a975440b3aecaf6b161cc98d5.png