排序算法時間複雜度、空間複雜度、穩定性比較

轉自：https://blog.csdn.net/yushiyi6453/article/details/76407640

排序算法分類

　　排序大的分類可以分為兩種：内排序和外排序。

　　放在記憶體的稱為内排序，需要使用外存的稱為外排序。

排序算法的時間複雜度和空間複雜度

排序算法	平均時間複雜度	最壞時間複雜度	最好時間複雜度	空間複雜度	穩定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	穩定
直接選擇排序	O(n²)	O(n²)	O(n)	O(1)	不穩定
直接插入排序	O(n²)	O(n²)	O(n)	O(1)	穩定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(nlogn)	不穩定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不穩定
希爾排序	O(nlogn)	O(ns)	O(n)	O(1)	不穩定
歸并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	穩定
計數排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	穩定
基數排序	O(N*M)	O(N*M)	O(N*M)	O(M)	穩定

注：

1 歸并排序可以通過手搖算法将空間複雜度降到O(1)，但是時間複雜度會提高。

2 基數排序時間複雜度為O(N*M)，其中N為資料個數，M為資料位數。

輔助記憶

• 時間複雜度記憶- 

1. 冒泡、選擇、直接 排序需要兩個for循環，每次隻關注一個元素，平均時間複雜度為O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
2. 快速、歸并、希爾、堆基于二分思想，log以2為底，平均時間複雜度為O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

• 穩定性記憶-“快希選堆”（快犧牲穩定性） 

1. 排序算法的穩定性：排序前後相同元素的相對位置不變，則稱排序算法是穩定的；否則排序算法是不穩定的。

原理了解

1 冒泡排序

1.1 過程

冒泡排序從小到大排序：一開始交換的區間為0~N-1，将第1個數和第2個數進行比較，前面大于後面，交換兩個數，否則不交換。再比較第2個數和第三個數，前面大于後面，交換兩個數否則不交換。依次進行，最大的數會放在數組最後的位置。然後将範圍變為0~N-2，數組第二大的數會放在數組倒數第二的位置。依次進行整個交換過程，最後範圍隻剩一個數時數組即為有序。

1.2 動圖

1.3 核心代碼（函數）

//array[]為待排序數組，n為數組長度
void BubbleSort(int array[], int n)
{
    int i, j, k;
    for(i=0; i<n-1; i++)
        for(j=0; j<n-1-i; j++)
        {
            if(array[j]>array[j+1])
            {
                k=array[j];
                array[j]=array[j+1];
                array[j+1]=k;
            }
        }
}
           

2 直接選擇排序

2.1 過程

選擇排序從小到大排序：一開始從0~n-1區間上選擇一個最小值，将其放在位置0上，然後在1~n-1範圍上選取最小值放在位置1上。重複過程直到剩下最後一個元素，數組即為有序。

2.2 動圖

2.3 核心代碼（函數）

//array[]為待排序數組，n為數組長度
void selectSort(int array[], int n)
{
    int i, j ,min ,k;
    for( i=0; i<n-1; i++)
    {
        min=i; //每趟排序最小值先等于第一個數，周遊剩下的數
        for( j=i+1; j<n; j++) //從i下一個數開始檢查
        {
            if(array[min]>array[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            k=array[min];
            array[min]=array[i];
            array[i]=k;
        }
    }
}
           

3 直接插入排序

3.1 過程

插入排序從小到大排序：首先位置1上的數和位置0上的數進行比較，如果位置1上的數大于位置0上的數，将位置0上的數向後移一位，将1插入到0位置，否則不處理。位置k上的數和之前的數依次進行比較，如果位置K上的數更大，将之前的數向後移位，最後将位置k上的數插入不滿足條件點，反之不處理。

3.2 動圖

3.3 核心代碼（函數）

//array[]為待排序數組，n為數組長度
void insertSort(int array[], int n)
{
    int i,j,temp;
    for( i=1;i<n;i++)
    {
        if(array[i]<array[i-1])
        {
            temp=array[i];
            for( j=i;array[j-1]>temp;j--)
            {
                array[j]=array[j-1];
            }
            array[j]=temp;
        }
    }
}
           

4 快速排序

 4.1 過程

 快速排序從小到大排序：在數組中随機選一個數（預設數組首個元素），數組中小于等于此數的放在左邊部分，大于此數的放在右邊部分，這個操作確定了這個數是處于正确位置的，再對左邊部分數組和右邊部分數組遞歸調用快速排序，重複這個過程。

 4.2 動圖

 4.3 核心代碼（函數）

void quicksort(int a[], int left, int right) {
    int i, j, t, privotkey;
    if (left > right)   //（遞歸過程先寫結束條件）
        return;

    privotkey = a[left]; //temp中存的就是基準數（樞軸）
    i = left;
    j = right;
    while (i < j) {
        //順序很重要，要先從右邊開始找（最後交換基準時換過去的數要保證比基準小，因為基準選取數組第一個數）
        while (a[j] >= privotkey && i < j) {
            j--;
        }
        a[i] = a[j];
        //再找左邊的
        while (a[i] <= privotkey && i < j) {
            i++;
        }
        a[j] = a[i];
    }
    //最終将基準數歸位
    a[i] = privotkey;

    quicksort(a, left, i - 1);//繼續處理左邊的，這裡是一個遞歸的過程
    quicksort(a, i + 1, right);//繼續處理右邊的 ，這裡是一個遞歸的過程
}
           

5 堆排序

 5.1 過程

 堆排序從小到大排序：首先将數組元素建成大小為n的大頂堆，堆頂（數組第一個元素）是所有元素中的最大值，将堆頂元素和數組最後一個元素進行交換，再将除了最後一個數的n-1個元素   建立成大頂堆，再将最大元素和數組倒數第二個元素進行交換，重複直至堆大小減為1。

• 注：完全二叉樹 

  假設二叉樹深度為n，除了第n層外，n-1層節點都有兩個孩子，第n層節點連續從左到右。如下圖 

  

• 注：大頂堆 

  大頂堆是具有以下性質的完全二叉樹：每個節點的值都大于或等于其左右孩子節點的值。 

  即，根節點是堆中最大的值，按照層序周遊給節點從1開始編号，則節點之間滿足如下關系： 

  

   (1<=i<=n/2)

 5.2 動圖

 5.3 核心代碼（函數）

void heapSort(int array[], int n)
{
    int i;
    for (i=n/2;i>0;i--)
    {
        HeapAdjust(array,i,n);//從下向上，從右向左調整
    }
    for( i=n;i>1;i--)
    {
        swap(array, 1, i);
        HeapAdjust(array, 1, i-1);//從上到下，從左向右調整
    }
}
void HeapAdjust(int array[], int s, int n )
{
    int i,temp;
    temp = array[s];
    for(i=2*s;i<=n;i*=2)
    {
        if(i<n&&array[i]<array[i+1])
        {
            i++;
        }
        if(temp>=array[i])
        {
            break;
        }
        array[s]=array[i];
        s=i;
    }
    array[s]=temp;
}
void swap(int array[], int i, int j)
{
    int temp;

    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}
           

6 希爾排序

 6.1 過程

 希爾排序是插入排序改良的算法，希爾排序步長從大到小調整，第一次循環後面元素逐個和前面元素按間隔步長進行比較并交換，直至步長為1，步長選擇是關鍵。

 6.2 動圖

 6.3 核心程式（函數）

//下面是插入排序
void InsertSort( int array[], int n)
{
    int i,j,temp;
    for( i=0;i<n;i++ )
    {
        if(array[i]<array[i-1])
        {
            temp=array[i];
            for( j=i-1;array[j]>temp;j--)
            {
                array[j+1]=array[j];
            }
            array[j+1]=temp;
        }
    }
}
//在插入排序基礎上修改得到希爾排序
void SheelSort( int array[], int n)
{
    int i,j,temp;
    int gap=n; //~~~~~~~~~~~~~~~~~~~~~
    do{
        gap=gap/3+1;  //~~~~~~~~~~~~~~~~~~
        for( i=gap;i<n;i++ )
        {
            if(array[i]<array[i-gap])
            {
                temp=array[i];
                for( j=i-gap;array[j]>temp;j-=gap)
                {
                    array[j+gap]=array[j];
                }
                array[j+gap]=temp;
            }
        }
    }while(gap>1);  //~~~~~~~~~~~~~~~~~~~~~~

}
           

7 歸并排序

 7.1 過程

 歸并排序從小到大排序：首先讓數組中的每一個數單獨成為長度為1的區間，然後兩兩一組有序合并，得到長度為2的有序區間，依次進行，直到合成整個區間。

 7.2 動圖

 7.3 核心代碼（函數）

遞歸實作

實作歸并，并把資料都放在list1裡面 
void merging(int *list1, int list1_size, int *list2,  int list2_size)
{
    int i=0, j=0, k=0, m=0;
    int temp[MAXSIZE];

    while(i < list1_size && j < list2_size)
    {
        if(list1[i]<list2[j])
        {
            temp[k++] = list1[i++];
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }
    while(i<list1_size)
    {
        temp[k++] = list1[i++];
    }
    while(j<list2_size)
    {
        temp[k++] = list2[j++];
    }

    for(m=0; m < (list1_size+list2_size); m++)
    {
        list1[m]=temp[m];
    }
}
//如果有剩下的，那麼說明就是它是比前面的數組都大的，直接加入就可以了 
void mergeSort(int array[], int n)
{
    if(n>1)
    {
        int *list1 = array;
        int list1_size = n/2;
        int *list2 = array + n/2;
        int list2_size = n-list1_size;

        mergeSort(list1, list1_size);
        mergeSort(list2, list2_size);

        merging(list1, list1_size, list2, list2_size);
    }
}
//歸并排序複雜度分析：一趟歸并需要将待排序列中的所有記錄  
//掃描一遍，是以耗費時間為O(n),而由完全二叉樹的深度可知，  
//整個歸并排序需要進行[log2n],是以，總的時間複雜度為  
//O(nlogn),而且這是歸并排序算法中平均的時間性能  
//空間複雜度：由于歸并過程中需要與原始記錄序列同樣數量級的  
//存儲空間去存放歸并結果及遞歸深度為log2N的棧空間，是以空間  
//複雜度為O(n+logN)  
//也就是說，歸并排序是一種比較占記憶體，但卻效率高且穩定的算法 
           

疊代實作

void MergeSort(int k[],int n)  
{  
    int i,next,left_min,left_max,right_min,right_max;  
    //動态申請一個與原來數組一樣大小的空間用來存儲
    int *temp = (int *)malloc(n * sizeof(int));  
    //逐級上升，第一次比較2個，第二次比較4個，第三次比較8個。。。  
    for(i=1; i<n; i*=2)  
    {  
        //每次都從0開始，數組的頭元素開始  
        for(left_min=0; left_min<n-i; left_min = right_max)  
        {  
            right_min = left_max = left_min + i;  
            right_max = left_max + i;  
            //右邊的下标最大值隻能為n  
            if(right_max>n)  
            {  
                right_max = n;  
            }  
            //next是用來标志temp數組下标的，由于每次資料都有傳回到K，  
            //故每次開始得重新置零  
            next = 0;  
            //如果左邊的資料還沒達到分割線且右邊的數組沒到達分割線，開始循環  
            while(left_min<left_max&&right_min<right_max)  
            {  
                if(k[left_min] < k[right_min])  
                {  
                    temp[next++] = k[left_min++];  
                }  
                else  
                {  
                    temp[next++] = k[right_min++];  
                }  
            }  
            //上面循環結束的條件有兩個，如果是左邊的遊标尚未到達，那麼需要把  
            //數組接回去，可能會有疑問，那如果右邊的沒到達呢，其實模拟一下就可以  
            //知道，如果右邊沒到達，那麼說明右邊的資料比較大，這時也就不用移動位置了  

            while(left_min < left_max)  
            {  
                //如果left_min小于left_max，說明現在左邊的資料比較大  
                //直接把它們接到數組的min之前就行  
                k[--right_min] = k[--left_max];   
            }  
            while(next>0)  
            {  
                //把排好序的那部分數組傳回該k  
                k[--right_min] = temp[--next];        
            }  
        }  
    }  
}  
//非遞歸的方法，避免了遞歸時深度為log2N的棧空間，
//空間隻是用到歸并臨時申請的跟原來數組一樣大小的空間，并且在時間性能上也有一定的提升，
//是以，使用歸并排序是，盡量考慮用非遞歸的方法。
           

8 桶排序（基數排序和基數排序的思想）

 8.1 過程

 桶排序是計數排序的變種，把計數排序中相鄰的m個”小桶”放到一個”大桶”中，在分完桶後，對每個桶進行排序（一般用快排），然後合并成最後的結果。

 8.2 圖解

 8.3 核心程式

#include <stdio.h>
int main()
{
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
        a[i]=0;  //初始化為0

    for(i=1;i<=5;i++)  //循環讀入5個數
    {
        scanf("%d",&t);  //把每一個數讀到變量t中
        a[t]++;  //進行計數(核心行)
    }

    for(i=0;i<=10;i++)  //依次判斷a[0]~a[10]
        for(j=1;j<=a[i];j++)  //出現了幾次就列印幾次
            printf("%d ",i);

    getchar();getchar(); 
    //這裡的getchar();用來暫停程式，以便檢視程式輸出的内容
    //也可以用system("pause");等來代替
    return 0;
}
           

9 計數排序

 9.1 過程

 算法的步驟如下： 

 - 找出待排序的數組中最大和最小的元素 

 - 統計數組中每個值為i的元素出現的次數，存入數組C的第i項 

 - 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加） 

 - 反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1

 9.2 圖解

 9.3 核心程式（函數）

程式1：
#define NUM_RANGE (100)    //預定義資料範圍上限，即K的值

void counting_sort(int *ini_arr, int *sorted_arr, int n)  //所需空間為 2*n+k
{  
       int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);  
       int i, j, k;  

       //初始化統計數組元素為值為零 
       for(k=0; k<NUM_RANGE; k++){  
               count_arr[k] = 0;  
       }  
       //統計數組中，每個元素出現的次數    
       for(i=0; i<n; i++){  
               count_arr[ini_arr[i]]++;  
       }  

       //統計數組計數，每項存前N項和，這實質為排序過程
       for(k=1; k<NUM_RANGE; k++){  
               count_arr[k] += count_arr[k-1];  
       }  

       //将計數排序結果轉化為數組元素的真實排序結果
       for(j=n-1 ; j>=0; j--){  
           int elem = ini_arr[j];          //取待排序元素
           int index = count_arr[elem]-1;  //待排序元素在有序數組中的序号
           sorted_arr[index] = elem;       //将待排序元素存入結果數組中
           count_arr[elem]--;              //修正排序結果，其實是針對算得元素的修正
       }  
       free(count_arr);  
}  

程式2：C++(最大最小壓縮桶數)
public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }
        int[] countArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i]-- > 0) {
                arr[index++] = i + min;
        }
}
           

10 基數排序

 10.1 過程

 基數排序是基于資料位數的一種排序算法。 

 它有兩種算法 

 ①LSD–Least Significant Digit first 從低位（個位）向高位排。 

 ②MSD– Most Significant Digit first 從高位向低位（個位）排。 

 時間複雜度O(N*最大位數)。 

 空間複雜度O(N)。

 10.2 圖解

 對a[n]按照個位0~9進行桶排序： 

 對b[n]進行累加得到c[n]，用于b[n]中重複元素計數 

 ！！！b[n]中的元素為temp中的位置！！！跳躍的用++補上： 

 temp數組為排序後的數組，寫回a[n]。temp為按順序倒出桶中的資料（聯合b[n],c[n],a[n]得到），重複元素按順序輸出： 

 10.3 核心程式

//基數排序  
//LSD  先以低位排，再以高位排  
//MSD  先以高位排，再以低位排  
void LSDSort(int *a, int n)  
{  
    assert(a);  //判斷a是否為空，也可以a為空||n<2傳回
    int digit = 0;   //最大位數初始化
    for (int i = 0; i < n; ++i)  
    {   //求最大位數
        while (a[i] > (pow(10,digit)))  //pow函數要包含頭檔案math.h，pow(10,digit)=10^digit
        {  
            digit++;  
        }  
    }  
    int flag = 1;   //位數
    for (int j = 1; j <= digit; ++j)  
    {  
        //建立數組統計每個位出現資料次數（Digit[n]為桶排序b[n]）  
        int Digit[10] = { 0 };  
        for (int i = 0; i < n; ++i)  
        {  
            Digit[(a[i] / flag)%10]++;  //flag=1時為按個位桶排序
        }  
         //建立數組統計起始下标（BeginIndex[n]為個數累加c[n]，用于記錄重複元素位置
         //flag=1時，下标代表個位數值，數值代表位置，跳躍代表重複）
        int BeginIndex[10] = { 0 };  
        for (int i = 1; i < 10; ++i)  
        {  
            //累加個數
            BeginIndex[i] = BeginIndex[i - 1] + Digit[i - 1];  
        }  
        //建立輔助空間進行排序 
        //下面兩條可以用calloc函數實作
        int *tmp = new int[n];  
        memset(tmp, 0, sizeof(int)*n);//初始化  
        //聯合各數組求排序後的位置存在temp中
        for (int i = 0; i < n; ++i)  
        {  
            int index = (a[i] / flag)%10;  //桶排序和位置數組中的下标
            //計算temp相應位置對應a[i]中的元素，++為BeginIndex數組數值加1
            //跳躍間隔用++來補，先用再++
            tmp[BeginIndex[index]++] = a[i];  
        }  
        //将資料重新寫回原空間  
        for (int i = 0; i < n; ++i)  
        {  
            a[i] = tmp[i];  
        }  
        flag = flag * 10;  
        delete[] tmp;  
    }  
}  
           

推薦一個非常好的算法可視化示範的網站：https://visualgo.net/zh

《快速排序、歸并排序、堆排序三種算法性能比較》

上文指出三種算法的性能差異：在資料量小的時候快速排序當屬第一，堆排序最差，但随着資料的不斷增大歸并排序的性能會逐漸趕上并超過快速排序，性能成為三種算法之首。可能在資料量大到一定數量時，快速排序的堆棧開銷比較大，是以在性能上大打折扣，甚至堆排序的性能也能好過它，但總體上來說快速排序表現的還是比較優秀的。