文档章节

数据结构中的常见排序

o
 osc_n6euf5h6
发布于 2019/03/19 21:08
字数 2587
阅读 0
收藏 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)。

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

 

稳定性:

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

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

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

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

在virtualenv中使用Python 3 - Using Python 3 in virtualenv

问题: Using virtualenv , I run my projects with the default version of Python (2.7). 使用virtualenv ,我使用默认版本的Python(2.7)运行项目。 On one project, I need to use Pyth......

富含淀粉
19分钟前
0
0
Python的__init__和self是做什么的? - What __init__ and self do on Python?

问题: I'm learning the Python programming language and I've came across something I don't fully understand. 我正在学习Python编程语言,遇到了一些我不太了解的东西。 In a method ......

javail
49分钟前
15
0
OSChina 周五乱弹 —— 你大妈还是你大妈

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @watergood:是时候分享一波我的这张纯音乐歌单了,过去的五年多时间里,我陆陆续续地把听到的好听的纯音乐添加了进去,目前一共65首,相信总...

小小编辑
今天
25
0
在Objective-C中生成随机数 - Generating random numbers in Objective-C

问题: I'm a Java head mainly, and I want a way to generate a pseudo-random number between 0 and 74. In Java I would use the method: 我主要是Java头,我想要一种生成0到74之间的伪随......

技术盛宴
今天
13
0
ftp-ftps-sftp的关系

Ftp FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件的双向传输。同时,它也是一个应用程序(Application)。基于不同的操作...

独钓渔
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部