為了讓大家掌握多種排序方法的基本思想，本篇文章帶著大家對(duì)數(shù)據(jù)結(jié)構(gòu)的常用七大算法進(jìn)行分析：包括直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序等，并能夠用高級(jí)語言實(shí)現(xiàn)。

希望通過對(duì)這些算法效率的比較，加深對(duì)算法的理解。

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

排序算法的分析圖解：

用隨機(jī)數(shù)（介于1-100）產(chǎn)生10個(gè)待排序數(shù)據(jù)元素的關(guān)鍵字值）。

① 采用直接插入排序和希爾排序方法對(duì)上述待排數(shù)據(jù)進(jìn)行排序并輸出序后的有序序列；

② 采用冒泡排序、快速排序方法對(duì)上述待排數(shù)據(jù)進(jìn)行排序并輸出序后的有序序列；

③ 采用簡(jiǎn)單選擇排序、堆排序方法對(duì)上述待排數(shù)據(jù)進(jìn)行排序并輸出序后的有序序列；

④ 采用歸并排序方法對(duì)上述待排數(shù)據(jù)進(jìn)行排序并輸出排序后的有序序列；

代碼分析

頭文件：

#include#include#include
#define MAXSIZE 100
using namespace std;
typedef int KeyType;typedef int InfoType;
typedef struct{    KeyType key;    InfoType otherinfo;}RedType;
typedef struct{    RedType r[MAXSIZE+1];    int length;}SqList;

①插入排序

void InsertSort(SqList &L){    int i,j,a=0,b=0;    for(i=1;i<=L.length;++i)    {        if(L.r[i].key-1].key)        {            L.r[0]=L.r[i];            L.r[i]=L.r[i-1];            a++;        }        for(j=i-2;L.r[0].key            L.r[j+1]=L.r[j];b++;        L.r[j+1]=L.r[0];    }    cout<<"比較次數(shù):"<"移動(dòng)次數(shù):"<endl;}

②折半插入排序

void BInsertSort(SqList &L){    int low,high,m;    for(int i=2;i<=L.length;++i)    {        L.r[0]=L.r[i];        low=1;high=i-1;        while(low<=high)        {            m=(low+high)/2;            if(L.r[0].key-1;            else low=m+1;        }        for(int j=i-1;j>=high+1;--j)            L.r[j+1]=L.r[j];        L.r[high+1]=L.r[0];    }}

③選擇排序

void SelectSort(SqList &L){    int j,k;    for(int i=1;i<=L.length;++i)    {        k=i;        for(j=i+1;j<=L.length;j++)            if(L.r[j].key        if(k!=i)        {            L.r[0].key=L.r[i].key;            L.r[i].key=L.r[k].key;            L.r[k].key=L.r[0].key;        }    }}

④起泡排序

void BubbleSort(SqList &L){    int i,j;    for(i=1;i<=L.length;++i)    {        for(j=1;j1;++j)        {            if(L.r[j+1].key            {                L.r[0].key=L.r[j].key;                L.r[j].key=L.r[j+1].key;                L.r[j+1].key=L.r[0].key;            }        }    }}

⑤快速排序

int Partition(SqList &L,int low,int high){    L.r[0]=L.r[low];    KeyType pivotkey=L.r[low].key;    while(low    {        while(low=pivotkey)--high;        L.r[low]=L.r[high];        while(low        L.r[high]=L.r[low];    }    L.r[low]=L.r[0];    return low;}
void QSort(SqList &L,int low,int high){    if(low    {        int pivotloc=Partition(L,low,high);        QSort(L,low,pivotloc-1);        QSort(L,pivotloc+1,high);    }}

⑥希爾排序

void ShellInsert(SqList &L,int dk){        int i,j;        for(i=dk+1;i<=L.length;++i)        {            if(L.r[i].key0]=L.r[i];            for(j=i-dk;j>0&&L.r[0].key                L.r[j+dk]=L.r[j];            L.r[j+dk]=L.r[0];            }        }}
void ShellSort(SqList &L,int dlta[],int t){    for(int k=0;k        ShellInsert(L,dlta[k]);}

⑦堆排序

typedef SqList HeapType;void HeapAdjust(HeapType &H,int s,int m){    RedType rc=H.r[s];int j;    for(j=2*s;j<=m;j*=2)    {        if(j1].key)++j;        if(!(rc.keybreak;        H.r[s]=H.r[j];s=j;    }    H.r[s]=rc;}void HeapSort(HeapType &H){    int i;    RedType temp;    for(i=H.length/2;i>0;--i)        HeapAdjust(H,i,H.length);    for(i=H.length;i>1;--i)    {        temp=H.r[1];        H.r[1]=H.r[i];        H.r[i]=temp;        HeapAdjust(H,1,i-1);    }

⑧歸并排序

void Merge(RedType SR[],RedType &TR[],int i,int m,int n){    int j,k;    for(j=m+1,k=i;i<=m&&j<=n;++k)    {        if(SR[i].key<=SR[j].key)            TR[k]=SR[i++];        else            TR[k]=SR[j++];    }    int t;    if(i<=m)    {        for(t=i;t<=m;t++)            TR[k+t-i]=SR[t];    }    if(j<=n)    {        for(t=j;t<=m;t++)            TR[k+t-j]=SR[t];    }}
void MSort(RedType SR[],RedType *TR1,int s,int t){    int m;    RedType TR2[MAXSIZE+1];    if(s==t)TR1[s]=SR[s];    else{        m=(s+t)/2;        MSort(SR,TR2,s,m);        MSort(SR,TR2,m+1,t);        Merge(TR2,TR1,s,m,t);    }}void MergeSort(SqList &L){    MSort(L.r,L.r,1,L.length);}

隨機(jī)生成函數(shù)

void RandSqList(SqList &L){    int n,max,min;    printf("輸入順序表的大小
");    cin>>n;    printf("輸入最小值和最大值
");    cin>>min>>max;    L.length=n;    printf("隨機(jī)產(chǎn)生%d個(gè)數(shù)
",n);    for(int i=1;i<=L.length;++i)    {        L.r[i].key=rand()%(max-min+1);        L.r[i].key+=min;    }    printf("順序表創(chuàng)建成功!
");}

輸出函數(shù)

結(jié)論

（1）若n較小（例如n<50），可采用直接插入排序、冒泡排序或簡(jiǎn)單選擇排序。如果記錄中的數(shù)據(jù)較多，移動(dòng)較費(fèi)時(shí)的，應(yīng)采取簡(jiǎn)單選擇排序法。

（2）若記錄的初始狀態(tài)已經(jīng)按關(guān)鍵碼基本有序，則選用直接插入排序或冒泡排序法為宜。

（3）若n較大，則應(yīng)采用改進(jìn)排序方法，如快速排序、堆排序或歸并排序法。這些排序算法的時(shí)間復(fù)雜度均為O(nlog2n)，但就平均性能而言，快速排序被認(rèn)為是目前基于比較記錄關(guān)鍵碼的內(nèi)部排序中最好的排序方法，但遺憾的是，快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n2)，堆排序與歸并排序的最壞情況時(shí)間復(fù)雜度仍為O(nlog2n)。堆排序和快速排序法都是不穩(wěn)定的排序。若要求穩(wěn)定排序，則可選用歸并排序。

（4）基數(shù)排序可在O (d×n) 時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序，d是指單邏輯關(guān)鍵碼的個(gè)數(shù)，一般遠(yuǎn)少于n。但基數(shù)排序只適用于字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵碼。

（5）前面討論的排序算法，除基數(shù)排序外，都是在順序存儲(chǔ)上實(shí)現(xiàn)的。當(dāng)記錄本身的信息量很大時(shí)，為避免大量時(shí)間用在移動(dòng)數(shù)據(jù)上，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。插入排序和歸并排序都易在鏈表上實(shí)現(xiàn)，但有的排序方法，如快速排序和堆排序在鏈表上卻很難實(shí)現(xiàn)。

寫在最后：對(duì)于準(zhǔn)備學(xué)習(xí)C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！