常用排序算法總結(jié)（C++實(shí)現(xiàn)）

常用排序算法總結(jié)

概述

在計(jì)算機(jī)科學(xué)中，排序算法是一種重要的操作。合理的排序算法能夠大幅度提高計(jì)算機(jī)處理數(shù)據(jù)的性能。排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。我們這里說說八大排序就是內(nèi)部排序。


1.插入排序

1.1直接插入排序

算法思想

直接插入排序是一種簡(jiǎn)單的排序算法，由 n-1 趟排序組成。第 p 趟排序后保證第 0 個(gè)位置到第 p 個(gè)位置上的元素為有序狀態(tài)。第 p+1 趟排序?qū)⒌?p+2 個(gè)元素插入到前面 p+1個(gè)元素的有序表中。下圖顯示了直接插入排序算法的每一趟的排序情況。

初始數(shù)據(jù)序列 32??18 ??65??48??27??9
第1趟排序之后 18??32??65??48??27??9
第2趟排序之后 18??32??65??48??27??9
第3趟排序之后 18??32??48??65??27??9
第4趟排序之后 18??27??32??48??65??9
第5趟排序之后 9??18??27??32??48??65
代碼實(shí)現(xiàn)
void DirectInsertSort(int *array,int n){
    int p ,i;
    for(p = 1;p<n;p++){
        int temp = array[p];
        i = p-1;
        while(i>=0&&array[i]>temp){
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = temp;
    }
}
復(fù)雜度分析

直接插入排序算法主要應(yīng)用比較和移動(dòng)兩種操作，從空間上來看，它只需要一個(gè)元素的輔助空間，用于位置的交換，有些教材也將這類排序算法稱為原地(In Place)排序算法。
從時(shí)間上分析，首先外層循環(huán)要進(jìn)行 n-1 次，但每一趟插入排序的比較和移動(dòng)的次數(shù)并不相同。第 p 趟插入時(shí)最好的情況時(shí)數(shù)據(jù)已經(jīng)排好序，每趟插入進(jìn)行一次比較，兩次移動(dòng)；最壞的情況時(shí)比較 p 次，移動(dòng) p+2 次，(逆序）（p = 1，2，...,n-1)。記 M 為執(zhí)行一次排序算法移動(dòng)的次數(shù)，C 為比較次數(shù)，則：

??C min = n-1;
??M min = 2(n-1);

??C max = 1+2+...+(n-1),

??M max = 3+4+...+(n+1) = (n^2+3n-4)/2;

假設(shè)數(shù)據(jù)元素在各個(gè)位置的概率相等，即 1/n ，則平均的比較次數(shù)和移動(dòng)次數(shù)為：

C ave = (n^2+n-2)/4,??M ave = (n^2+5n-6)/4;

因此，直接插入排序算法的時(shí)間復(fù)雜度是 O(n^2)。對(duì)于隨機(jī)順序的數(shù)據(jù)來說，移動(dòng)和比較的次數(shù)接近最壞情況。

由于直接插入算法的元素移動(dòng)是順序的，該算法是穩(wěn)定的。

1.2折半插入排序

算法思想

直接插入排序算法是利用有序表的插入操作來實(shí)現(xiàn)對(duì)數(shù)據(jù)集合的排序。在進(jìn)行第 p+1 趟插入排序時(shí)，需要在前面的有序序列 data[0],data[1],...data[p] 中找到 data[p+1] 第對(duì)應(yīng)位置 i ，同時(shí)將 data[i],data[i+1],...data[p] 都向后移動(dòng)一個(gè)位置。由于有序表是排好序的，故可以用折半查找（二分法）操作來確定 data[p+1] 的位置，這就是折半插入算法的思想。

代碼實(shí)現(xiàn)
void HalfInsertSort(int *array,int n){
    int left,right,middle,p;
    for(p = 1;p<n;p++){
        int temp = array[p];
        left = 0;right = p-1;
        while (left<=right) {
            middle = (left+right)/2;
            if(array[middle]>temp)
                right = middle-1;
            else
                left = middle+1;
        }
        for(int i = p-1;i>=left;i--){
            array[i+1] = array[i];
            array[left] = temp;
        }
    }
}
復(fù)雜度分析

折半插入排序算法與直接插入算法相比，需要的輔助空間與直接插入排序算法基本一致，時(shí)間上，折半插入的比較次數(shù)比直接插入的最壞情況號(hào)，最好情況下，時(shí)間復(fù)雜度為 O(n log2 n);折半插入算法的元素移動(dòng)與直接插入相同，復(fù)雜度為 O(n^2)。

折半插入和直接插入算法的元素移動(dòng)一樣是順序的，因此該排序算法也是穩(wěn)定的。

1.3 希爾(shell)排序

算法思想

希爾排序的基本思想是，先將待排序的數(shù)據(jù)序列劃分成若干子序列，分別進(jìn)行直接插入排序：待整個(gè)序列中的數(shù)據(jù)基本有序后，再對(duì)全部的數(shù)據(jù)進(jìn)行一次直接插入排序。
對(duì)于子序列可以采用任意簡(jiǎn)單的排序算法。

例如，對(duì)于序列 {65,34,25,87,12,38,56,46,14,77,92,23},可以劃分成如下 6 個(gè)子序列。


shell排序

如果初始序列是 array[0],?array[1],?array[2], ... ?array[n-1],?子序列間隔為 d ，則子序列可以描述為 ?array[i],?array[i+d],?array[i+2*d], ...?array[i+k*d],（其中 0<=i<d,i+k*d<n)。希爾排序中通過不斷地縮小增量，來將原始序列分成若干個(gè)子序列。例如，增量初始的時(shí)候可以選為待排序的元素個(gè)數(shù)的一半，即 n/2 的向下取整，在后來的迭代過程中不斷縮小增量，下一次的增量為上一次的一半，即第二趟的選擇增量為 n/4 的向下取整，以此類推，知道增量變?yōu)?1 為止。這時(shí)序列已經(jīng)基本有序，對(duì)整個(gè)序列進(jìn)行一次插入排序即可完成數(shù)據(jù)排序。

希爾排序算法流程
1

2

3
4

5

6
代碼實(shí)現(xiàn)
void ShellSort(int *array,int n){
    int d = n/2;
    while(d>=1){
        for(int k = 0;k<d;k++){
            for(int i = k+d;i<n;i++){
                int temp = array[i];
                int j = i-d;
                while(j>=k&&array[j]>temp){
                    array[j+d] = array[j];
                    j -=d;
                }
                array[j+d] = temp;
            }
        }
        d = d/2;
    }
}
復(fù)雜度分析

希爾排序算法依賴于增量序列的選擇，時(shí)間復(fù)雜度在 O(nlog2n) 和 O(n^2) 之間，大致為 O(n^1.3) 和直接插入排序算法相比，減少了算法復(fù)雜度。
希爾排序算法是不穩(wěn)定的。

2.交換排序

2.1冒泡排序

2.1.1簡(jiǎn)單冒泡排序
算法思想

以升序排序（不減排序）算法為例
冒泡排序算法一共要進(jìn)行 n-1 趟排序，每一趟排序都要將待排序序列中最大的元素?cái)D到最后。
第一趟：將第一個(gè)元素與第二個(gè)元素比較，若為逆序，則交換；然后比較第二個(gè)元素和第三個(gè)元素，若為逆序，則交換；以此類推，直到第 n-1 個(gè)元素和第 n 個(gè)元素比較，若為逆序，則交換，這樣，經(jīng)過第一趟排序，最大的元素被移動(dòng)到了序列的最后。
第二趟排序，由于最大的元素已經(jīng)在最右端了，因此只需要對(duì)記錄{a[0],a[1],...a[n-1]}進(jìn)行上述排序過程就可以了。
以此類推，進(jìn)行 n-1 趟掃描。

代碼實(shí)現(xiàn)
void bubbleSort(char *a,int n){
    char tmp;
    int i,j;
    for(i = 0;i<n-1;i++){
        for(j=0;j<n-i-1;j++){   
            if(a[j]>a[j+1]){
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}
復(fù)雜度分析

這種冒泡排序算法直觀、簡(jiǎn)便。但時(shí)間復(fù)雜度長(zhǎng)。
對(duì)任何序列，都需要進(jìn)行 n-1 趟掃描，第 i 趟需要進(jìn)行 n-i 次元素比較。造成了時(shí)間上的浪費(fèi)。因此，大部分情況，我們都會(huì)選擇改進(jìn)的冒泡排序。

2.1.2改進(jìn)的冒泡排序
算法思想

通過對(duì)每一趟排序進(jìn)行監(jiān)控，若中間某一趟排序過程中數(shù)沒有進(jìn)行交換，則說明序列已經(jīng)排好，此時(shí)跳出循環(huán)即可

代碼實(shí)現(xiàn)
void bubbleSort(char *a,int n){
    char tmp;
    int i,j;
    for(i = 0;i<n-1;i++){
        int flag=0;
        for(j=0;j<n-i-1;j++){   
            if(a[j]>a[j+1]){
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                flag=1;
            }
        }
        if(flag==0)break;
    }
}
復(fù)雜度分析

顯然，改進(jìn)的冒泡排序算法的效率和待排序的初始順序密切相關(guān)。若待排序的元素是正序，則是最好情況，此時(shí)只需要進(jìn)行一趟排序，比較次數(shù)為 n-1 次，移動(dòng)元素次數(shù)為 0 次；若初始待排序列為逆序，則是最壞情況，此時(shí)需要執(zhí)行 n-1 趟排序，第 i 趟做了 n-i 次比較，執(zhí)行 3(n-i) 次元素交換

所以最壞情況時(shí)間復(fù)雜度為 O(n^2).平均時(shí)間復(fù)雜度也是 O(n^2) 。

由于冒泡排序算法只是進(jìn)行元素間的順序移動(dòng)，所以是穩(wěn)定的算法。

2.2快速排序

  1. 分割：取序列的一個(gè)元素作為軸元素，利用這個(gè)軸元素，把序列分成三段，使所有小于等于軸元素的元素放在軸的左邊，大于軸的元素放在軸的右邊。此時(shí)，軸元素已經(jīng)被放到的正確的位置。
  2. 分治：對(duì)左段和右段中的元素遞歸調(diào)用（1）中的過程，分別對(duì)左端=段和右段中的元素進(jìn)行排序。
  3. 此時(shí)，排序完成

一般情況下，我們采用左邊第一個(gè)元素作為軸元素的方法。

分割策略1
算法思想

首先用一個(gè)臨時(shí)變量對(duì)首元素進(jìn)行備份，取兩個(gè)指針 left 和 right ，他們的初始值分別是待排序列的兩端的下標(biāo)，其中 left 指向最左邊，right 指向最右邊。在整個(gè)排序過程中保證 left 不大于 right ，用下面的方法不斷移動(dòng)兩個(gè)指針:

  1. 從 right 的位置向左搜索，找到第一個(gè)小于或等于軸的元素，移動(dòng)到 left 的位置。
  2. 再?gòu)?left 所指的位置向右搜索，找到第一個(gè)大于軸的元素，移動(dòng)到 right 所指的位置。
  3. 重復(fù)上面的過程，直到 left = right ，最后把軸元素放在 left 所指的位置。

經(jīng)過上面的過程，所有大于軸的元素放在了軸的右邊，小于軸的元素放在了軸的左邊。

代碼實(shí)現(xiàn)
int Partition(int *array,int left,int right){
    int pivot = array[left];
    while(left<right){
        while (left<right&&array[right]>pivot) {
            right--;
        }
        array[left] = array[right];
        while (left<right&&array[left]<=pivot) {
            left++;
        }
        array[right] = array[left];
    }
    array[left] = pivot;
    return left;
}
分割策略2
算法思想

分別從待排序序列兩端相向掃描，從左邊找到第一個(gè)大于軸的元素，從右邊找到第一個(gè)小于軸的元素，然后交換二者。

然后把軸元素和 right 所指的元素交換。

代碼實(shí)現(xiàn)
int Partition(int *array,int start,int end){
    int pivot = array[start];
    int left = start,right = end;
    while (left<=right) {
        while (left<=right&&array[left]<=pivot) {
            left++;
        }
        while (right>=left&&array[right]>pivot) {
            right--;
        }
        if(left<right){
            swap(array[right], array[left]);
            left++;right--;
        }
    }
    swap(array[start], array[right]);
    return right;
}
分治
代碼實(shí)現(xiàn)
void QuickSort(int *array,int left,int right){
    if(left<right){
        int p = Partition(array, left, right);
        QuickSort(array, left, p-1);
        QuickSort(array, p+1, right);
    }
}
復(fù)雜度分析

最好空間復(fù)雜度為 O(log n)， 最壞的空間復(fù)雜度為 O(n)。

3.選擇排序

3.1簡(jiǎn)單選擇排序

算法思想

簡(jiǎn)單選擇排序算法是利用線性查找的方法從一個(gè)序列中找到最小的元素，即地 i 趟的排序操作為：通過 n-i 次關(guān)鍵字的比較，從 n-i+1 個(gè)元素中選出最小的元素，并和第 i-1 個(gè)元素交換。簡(jiǎn)單選擇排序算法也稱為直接選擇排序算法。

代碼實(shí)現(xiàn)
void SelectionSort(char*num,int n){
    char tmp;
    for(int i = 0;i<n-1;i++){
        int min = i;
        for(int j = i;j<n;j++){
            if(num[min]>num[j]){
                min = j;
            }
        }
        if(min!=i){
            tmp = num[i];
            num[i] = num[min];
            num[min] = tmp;
        }   
    }
}
復(fù)雜度分析

簡(jiǎn)單選擇排序算法需要進(jìn)行 n-1 趟操作，而且第 i 趟選擇要進(jìn)行 n-i 次比較，最多執(zhí)行 1 次數(shù)據(jù)交換，最少進(jìn)行 0 次，因此簡(jiǎn)單選擇排序算法的時(shí)間效率是 O(n^2) 。簡(jiǎn)單選擇排序算法比較次數(shù)較多，而移動(dòng)次數(shù)較少。空間開銷中，由于只需要使用一個(gè)臨時(shí)變量來記錄最小位置，因此空間負(fù)責(zé)度為 O(1) 。簡(jiǎn)單選擇排序算法是不穩(wěn)定的排序算法。

3.2堆排序

算法思想

以降序排序?yàn)槔?/p>

  1. 將初始序列初始化為一個(gè)最大堆，初始化當(dāng)前待排序列元素的個(gè)數(shù) n 。
  2. 將堆頂元素和當(dāng)前最后一個(gè)元素交換，n = n-1;
  3. 調(diào)整堆結(jié)構(gòu)
  4. 如果當(dāng)前待排序列元素個(gè)數(shù) n>1 則重復(fù)步驟 2），3）。
代碼實(shí)現(xiàn)
void SiftDown(int *array,int i,int n){
        int left = 2*i+1,right = 2*i+2,min = i;
        if(left<n&&array[min]<array[left]){
            min = left;
        }
        if(right<n&&array[min]<array[right]){
            min = right;
        }
        if(min!=i){
            int t = array[min];
            array[min] = array[i];
            array[i] = t;
            SiftDown(array, min, n);
        }
}
void BuildHeap(int *array,int n){
    int p = n/2-1;
    for(int i = p;i>=0;i--){
        SiftDown(array, i, n);
    }
}
void HeapSort(int *array,int n){
    BuildHeap(array,n);
    for(int i = n-1;i>0;i--){
        int t = array[0];
        array[0] = array[i];
        array[i] = t;
        SiftDown(array, 0, i);
    }
}
復(fù)雜度分析

對(duì)于調(diào)整最大堆的操作 SiftDown 來說，最多執(zhí)行 O(log2n) 次數(shù)據(jù)元素的交換，初始化堆的時(shí)間復(fù)雜度為 O(n) 。堆排序中一共調(diào)用了 n-1 次 SiftDown 操作。以及一次初始化操作，所以堆排序的時(shí)間復(fù)雜度為 O(log2n) 。排序過程中只需要，臨時(shí)變量來進(jìn)行交換操作，故空間開銷為 O(1) 。堆排序算法是不穩(wěn)定的算法。當(dāng)數(shù)據(jù)量較大的時(shí)候堆排序的效率體現(xiàn)得很明顯，在小數(shù)據(jù)集上，堆排序算法的優(yōu)勢(shì)并不明顯。

4.基數(shù)排序

算法思想
代碼實(shí)現(xiàn)
//MergeSort
//array是待歸并數(shù)組，
//其中對(duì) array[start,mid] 和 array[mid+1,end]
//之間的數(shù)據(jù)進(jìn)行合并
void Merge(int *array,int start,int mid,int end){
    int len1 = mid-start+1;
    int len2 = end-mid;
    int i,j,k;
    int *left = new int[len1];//臨時(shí)用數(shù)組來存放 array[start,mid]的數(shù)據(jù)
    int *right = new int[len2];//臨時(shí)用數(shù)組來存放 array[mid+1,end]
    for(i = 0;i<len1;i++){
        left[i] = array[i+start];
    }

    for(i = 0;i<len2;i++){
        right[i] = array[i+mid+1];
    }

    i = 0;j = 0;//執(zhí)行歸并
    for(k = start;k<=end;k++){
        if(i==len1 || j==len2){
            break;
        }
        if(left[i]<=right[j]){
            array[k] = left[i++];
        }
        else{
            array[k] = right[j++];
        }
    }
    
    while (i<len1) {
        array[k++] = left[i++];
    }
    while (j<len2) {
        array[k++] = right[j++];
    }
    delete [] left;
    delete [] right;
}
void MergeSort(int *array,int start,int end){
    if(start<end){
        int mid = (start+end)/2;
        MergeSort(array, start, mid);
        MergeSort(array, mid+1, end);
        Merge(array, start, mid, end);
    }
}
復(fù)雜度分析

5.歸并排序

###### 算法思想
###### 代碼實(shí)現(xiàn)
//基數(shù)排序
int  getMaxBit(int *array,int n){//得到元素序列中最大數(shù)的位數(shù)
    int max = 1;
    int k = 10;
    for(int i = 0;i<n;i++){
        while(array[i]>=k){
            k*=10;
            max++;
        }
    }
    return max;
}
void RadixSort(int *array,int size)
{
    int n;
    int max = getMaxBit(array, size);
    int maxNum = 1;
    for(int i = 1;i<max;i++){
        maxNum *=10;
    }
    for(int i=1;i<=maxNum;i=i*10)
    {
        int tmp[15][10]={0};//分配操作:建立一個(gè)15行，10列的數(shù)組，每一列分別代表0~9位數(shù)，15行代表能存放的總個(gè)數(shù)
        for(int j=0;j<size;j++)
        {
            n=(array[j]/i)%10;
            tmp[j][n]=array[j];
        }
        int k=0;//收集操作：將二維數(shù)組中的數(shù)據(jù)自左至右、自上至下收集到數(shù)組中
        for(int p=0;p<10;p++)
            for(int q=0;q<size;q++)
            {
                if(tmp[q][p]!=0)
                    array[k++]=tmp[q][p];
            }
    }
}
復(fù)雜度分析
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 概述：排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    每天刷兩次牙閱讀 3,829評(píng)論 0贊 15
  • 概述 排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    蟻前閱讀 5,308評(píng)論 0贊 52
  • 排序的基本概念 在計(jì)算機(jī)程序開發(fā)過程中，經(jīng)常需要一組數(shù)據(jù)元素(或記錄)按某個(gè)關(guān)鍵字進(jìn)行排序，排序完成的序列可用于快...
    Jack921閱讀 1,576評(píng)論 1贊 4
  • 高鐵修成后，聽大家說，鄭州和西安兩地之間變的很短?？梢栽谕砩系轿靼渤詡€(gè)羊肉泡饃，然后再回來睡覺，什么都不耽誤。 周...
    雪凝心閱讀 1,073評(píng)論 26贊 10
  • 使用 Properties 在上面的文章中，我已經(jīng)介紹了在 Java 中如何使用 MySQL， 下面就來看看怎么使...
    ghwaphon閱讀 1,098評(píng)論 0贊 3

友情鏈接更多精彩內(nèi)容