数据结构中的常见排序

落日映苍穹つ 2022-01-06 02:04 233阅读 0赞

**一、基数排序**

基数排序的思想比较好理解，即是从各位数开始比较起，一直比较到最高位位置，每次比较都是在前一次比较的基础上进行的。

代码如下：

/*
        基数排序，即为按照每位数来将其分类，然后在前一次分类的顺序基础上，再次进行分类，直到所有分类标准都执行完毕
        时间复杂度为n 
    */
    #include <iostream>
    using namespace std;
    int GetNumByPos(int num,int dight){
        int value=-1;
        while(dight>0){
            value=num%10;
            num=num/10;
            dight--;
        }
        return value;
    }
    void RadixSort(int * s,int len,int dight){
        int * buttet=new int[len];
        int count[dight];
        for(int i=1;i<=dight;i++){
            for(int j=0;j<dight;j++){
                count[j]=0;
            }
            for(int j=0;j<len;j++){
                if(GetNumByPos(s[j],i)>=0){
                    count[GetNumByPos(s[j],i)]++;
                }
            }
            for(int j=1;j<dight;j++){
                count[j]=count[j]+count[j-1];
            }
            for(int j=len-1;j>=0;j--){
                buttet[count[GetNumByPos(s[j],i)]-1]=s[j];
                count[GetNumByPos(s[j],i)]--;
            }
            for(int j=0;j<len;j++){
                s[j]=buttet[j];
            }
        } 
    }
    int main(){
        int list[10]={
        278,109,63,930,589,184,505,269,8 ,83};
        RadixSort(list,10,10);
        for(int i=0;i<10;i++){
            cout<<list[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**二、二路归并排序**

二路归并排序的思想是开始就将数列划分为两个部分，然后依次递归的对这两部分执行二分操作，直到所有的部分都只包含一个元素位置，此时，再分别对这些部分执行归并操作。直到整个数列都被归并完毕。

代码如下：

/*
        二路归并排序，采用了递归的做法，它首先将整个队列划分为两个部分，再一次对这两个部分进行二分操作，
        直到每个部分只包含一个元素为止，然后再依次对这些只包含一个元素的部分开始进行归并，然后递归操作会依次向上
        进行回溯，最后返回已排好序的队列，排序完成。
        时间复杂度n*log2n  
    */
    #include <iostream>
    using namespace std;
    void Merge(int array[], int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
    
        int *L;
        L = (int*)malloc(sizeof(int)*n1);
        int *R;
        R = (int*)malloc(sizeof(int)*n2);
    
        int i = 0;
        int j = 0;
    
        for(i; i < n1; i++)
            L[i] = array[i + p];
        for(j; j < n2; j++)
            R[j] = array[j + q  +1];
    
        i = j = 0;
    
        int k = p;
    
        while(i!=n1 && j!= n2)
        {
            if(L[i] <= R[j])
                array[k++] = L[i++];
            else
                array[k++] = R[j++];
        }
    
        while(i < n1)
            array[k++] = L[i++];
        while(j < n2)
            array[k++] = R[j++];
    
        free(L);
        free(R);
    }
    
    void merge(int * b,int s,int mid,int t){
         
        int a[t-s+1];
        int k=0;for(int i=s;i<=t;i++){
            a[k++]=b[i];
        }int i,j;
        int id=s;
        for(i=s,j=mid+1;i<=mid&&j<=t;){
         if(a[i-s]<a[j-s]){
                b[id++]=a[i-s];
                i++;    
            }else{
                b[id++]=a[j-s];
                j++;
            }
        }while(i<=mid){
            b[id++]=a[i-s];
            i++;
        }
        while(j<=t){
            b[id++]=a[j-s];
            j++;
        }
    }
    void TwoGuiBing(int * a,int s,int e){
        int * bb;
        if(s<e){
            int mid=(s+e)/2;
            TwoGuiBing(a,s,mid);
            TwoGuiBing(a,mid+1,e);
            cout<<"before sort: ";
            for(int i=s;i<=e;i++){
                cout<<a[i]<<" ";
            }
            cout<<endl;
            merge(a,s,mid,e);
            cout<<"after sort: ";
            for(int i=s;i<=e;i++){
                cout<<a[i]<<" ";
            }
            cout<<endl;
        }
    }
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 
        TwoGuiBing(s,0,9);
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**三、快读排序**

快速排序的思想是每次都选择一个标志，将整个数列划分为两个部分，然后在依次递归的对这两个部分通用选取标志进行划分。直到每个部分大小变为1为止。

代码如下：

/*
        快速排序就是首先将s[0]选定为我们的划分标志，然后，将队列划分为两个部分。然后再分别对这两个部分进行划分。
        直到每个部分只包含一个元素为止。
        时间复杂度n*log2n  不稳定排序，数列有序则退化为冒泡排序。 
    */ 
    #include <iostream>
    using namespace std;
    void swap(int & a,int & b){
        int temp=a;
        a=b;
        b=temp;
    }
    int func(int * s,int b,int e){
        int flag=s[b];
        while(b<e){
            while(b<e&&s[e]>=flag) e--;//一定要>=否则如果最后两个数与flag相同，那么整个while就会陷入死循环中。 
            swap(s[b],s[e]);
            while(b<e&&s[b]<=flag) b++;
            swap(s[b],s[e]);
        }
        return b;
    }
    void quickSort(int * s,int b,int e){
        if(b<e){
            int pos=func(s,b,e);
            quickSort(s,b,pos-1);
            quickSort(s,pos+1,e);
        }
    }
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 
        quickSort(s,0,9);
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**四、堆排序**

堆排序，通过每次构造一个大顶堆或者小顶堆，来查找出当前数列的最大值或最小值，然后交换堆顶与最后一个叶子节点，同时，将排序的范围减一，直到排序的范围减小到1，记住，初始时需要先将数列构造为大顶堆或小顶堆。

代码如下：

/*
        时间复杂度n*log2n，我们直到堆排序，需要首先构造一个大顶堆或者小顶堆，然后开始选出最大值或最小值，在这一过程中，将其移动
        到堆顶，然后交换堆顶和堆尾，缩小堆的大小，再次排序，直到堆的大小为1为止。 
    */
    #include <iostream>
    using namespace std;
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 
        for(int i=10;i>0;i--){
         //之所以将i设置为从10开始，就是考虑了初始数列构造大顶堆或小顶堆的问题。 if(i<10){
         //初始时，无需交换堆顶和最后一个叶子结点。 int temp=s[i];
                s[i]=s[0];
                s[0]=temp;    
            }
            for(int j=(i)/2;j>=0;j--){
                int faV=s[j];
                int fa=j;
                int child=2*j+1;
                while(child<i){
                    if(child+1<i&&s[child]<s[child+1]){
                        child++;
                    }
                    if(s[child]>s[fa]){
         //一直顺着查找下去。
                        s[fa]=s[child];
                        fa=child;
                        child=2*fa+1;
                    }else{
                        break;
                    }
                    s[fa]=faV;
                }
            }
        }
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**五、希尔排序**

希尔排序通过设置间隔，来将数列进行分组，然后对于每组的数据使用直接插入排序。之后，在将间隔减小为其的一半，直到间隔减小到0为止。

代码如下：

/*
        通过设置间隔来实现，首先将间隔设置为队列大小的一半，对相同间隔内的元素执行直接插入排序。
        时间复杂度n到n*n 
    */
    #include <iostream>
    using namespace std;
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};
        int jianGe=10/2;
        while(jianGe>=1){
            for(int i=jianGe;i<10;i++){
                int j=i-jianGe;
                int val=s[i];//在后面的变换中，s[i]对应的值已经发生了变化。 
                while(s[j]>val&&j>=0){
                    s[j+jianGe]=s[j];
                    j=j-jianGe;
                }
                s[j+jianGe]=val;
            }
            jianGe=jianGe/2; 
        }
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**六、直接插入排序**

直接插入排序的思想就是假设初始的有序序列大小为1，然后依次扩大这个有序序列。

代码如下：

/*
        首先有序队列只包含第一个元素，随后逐渐扩充其大小，每次将新值与有序队列末尾的值进行比较，
        找到其位置。
        时间复杂度为n*n; 
    */
    #include <iostream>
    using namespace std;
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};
        for(int i=1;i<10;i++){
            if(s[i]>s[i-1]){
                continue;
            }else{
                int j=i-1;
                int val=s[i];
                while(s[j]>val){
                    s[j+1]=s[j];
                    j--;
                }
                s[j+1]=val;
            }
        }
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**七、冒泡排序**

冒泡排序的每次遍历都会比较临近元素的大小，不满足要求就交换其顺序，每次遍历都会找到一个当前查找范围的最大值或最小值。直到查找范围缩小到1。

代码如下：

#include <iostream>
    using namespace std;
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 
        for(int i=0;i<10;i++){
            for(int j=0;j<9-i;j++){
                if(s[j]>s[j+1]){
                    int temp=s[j];
                    s[j]=s[j+1];
                    s[j+1]=temp;
                }
            }
        }
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**八、简单选择排序**

简单选择排序会在每次遍历中找到它的最小值或最大值，然后缩小查找的范围，直到查找范围缩小到1.

代码如下：

/*
        每次找出最小值放置，时间复杂度n*n 
    */ 
    #include <iostream>
    using namespace std;
    int main(){
        int s[10]={
        4,1,5,2,4,3,98,6,65,1};
        for(int i=0;i<10;i++){
            int min=i;
            for(int j=i+1;j<10;j++){
                if(s[j]<s[min]){
                    min=j;
                }
            }
            if(min!=i){
                int temp=s[i];
                s[i]=s[min];
                s[min]=temp;
            }
        }
        for(int i=0;i<10;i++){
            cout<<s[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

**总结：**

(1)平方阶(O(n2))排序  
　　各类简单排序:直接插入、直接选择和冒泡排序；  
 (2)线性对数阶(O(nlog2n))排序  
　　快速排序、堆排序和归并排序；  
 (3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序  
(4)线性阶(O(n))排序  
　　基数排序，此外还有桶、箱排序。

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2），每次划分都会将数列划分为一个空数组和一个大小减一的数组，故比较次数为n-1,n-2,n-2,.......1,故为o(n2)。

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

**稳定性：**

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。   
     稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

转载于:https://www.cnblogs.com/JsonZhangAA/p/10561382.html