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

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

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

排序算法的分析圖解：

用隨機數（介于1-100）產生10個待排序數據元素的關鍵字值）。

① 采用直接插入排序和希爾排序方法對上述待排數據進行排序并輸出序后的有序序列；

② 采用冒泡排序、快速排序方法對上述待排數據進行排序并輸出序后的有序序列；

③ 采用簡單選擇排序、堆排序方法對上述待排數據進行排序并輸出序后的有序序列；

④ 采用歸并排序方法對上述待排數據進行排序并輸出排序后的有序序列；

代碼分析

頭文件：

#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<<"比較次數:"<"移動次數:"<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);}

隨機生成函數

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

輸出函數

結論

（1）若n較小（例如n<50），可采用直接插入排序、冒泡排序或簡單選擇排序。如果記錄中的數據較多，移動較費時的，應采取簡單選擇排序法。

（2）若記錄的初始狀態已經按關鍵碼基本有序，則選用直接插入排序或冒泡排序法為宜。

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

（4）基數排序可在O (d×n) 時間內完成對n個記錄的排序，d是指單邏輯關鍵碼的個數，一般遠少于n。但基數排序只適用于字符串和整數這類有明顯結構特征的關鍵碼。

（5）前面討論的排序算法，除基數排序外，都是在順序存儲上實現的。當記錄本身的信息量很大時，為避免大量時間用在移動數據上，可以用鏈表作為存儲結構。插入排序和歸并排序都易在鏈表上實現，但有的排序方法，如快速排序和堆排序在鏈表上卻很難實現。

寫在最后：對于準備學習C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內功）不妨從現在開始！

整理分享（多年學習的源碼、項目實戰視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！