【追求卓越08】算法--排序算法

引導

今天開始介紹我們在工作中經常遇到的算法--排序。排序算法有很多，我們主要介紹以下幾種：

冒泡排序

插入排序

選擇排序

歸并排序

快速排序

計數排序

基數排序

桶排序

我們需要了解每一種算法的定義以及實現方式，并且掌握如何評價一個排序算法。今天我們來學習冒泡排序，插入排序，選擇排序。

如何評價排序算法

評價算法的優劣主要從以下幾個方面考慮：

最好情況，最壞情況，平均情況時間復雜度
時間復雜度的系數，低階，常系數都需要考慮進去
是否是原地排序？
算法是否穩定？

第一點毋庸置疑，是我們主要的依判方式；

第二點,我們常常在計算復雜度時會忽略低階和常系數。這是因為當數據量很大，n趨向于無窮時。但是在實際工作中，我們的數據量不會這么大。所以這些低階和常數就需要考慮進去了。

第三點：原地排序就是對空間復雜度的一種描述，當排序算法的空間復雜度為O(1)時，我們就稱為原地排序

第四點：算法的穩定指的時排序之后是否會將值相同的數據對象改變位置。比如
1，3（1），5，7，9，3（2）,這組數據進行排序之后，3(2)還會在3(1)之后嗎？

????????算法的穩定性主要是用于對一組數據進行多次排序時進行參考。比如你要將一組數據按照時間和值大小按照時間從先到后，值從小到大進行排序。一般是按照時間排序，在對值進行排序。但是如果在進行值排序時，使用的是不穩定的算法，那么就會出現問題。（值相等，但時間可能有錯誤）

冒泡排序

冒泡排序原理：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

int bubblesort(int a[],int len)
{
??? int i,j=0;
??? int temp = 0;
??? for(i = 0; i < len ; i++)
??? {
??????? for(j = 0 ; j < len - i - 1? ; j++)
??????? {
??????????? if(a[j] > a[j+1])
??????????? {
???????????????? temp = a[j];
???????????????? a[j] = a[j+1];
???????????????? a[j+1] = temp;
??????????? }
??????? }
??? }
??? return 0;
}

以上是一般的冒泡排序代碼，但是可以稍微優化一下：

int bubblesort(int a[],int len)
{
??? int i,j=0;
??? int temp = 0;
??? int flag = 0;
??? for(i = 0; i < len ; i++)
??? {
??????? flag = 0;
??????? for(j = 0 ; j < len - i - 1? ; j++)
??????? {
??????????? if(a[j] > a[j+1])
??????????? {
???????????????? flag = 1;
???????????????? temp = a[j];
???????????????? a[j] = a[j+1];
???????????????? a[j+1] = temp;
??????????? }
??????? }
??????? if(flag == 1)
??????????? break;
??? }
??? return 0;
}

????????該優化過的代碼，加了一個判斷標志，當某一次冒泡沒有進行數據交互，說明剩下的都是排好序了。故可以直接退出。

分析：

時間復雜度：通過代碼實現我們可以知道，冒泡排序的復雜度為O((1+n)*n/2)。

空間復雜度：由于只有一個temp的額外變量，故空間復雜度為O(1),為原地排序。

穩定性:我們在判斷時，只要確保a[j]>a[j+1]為判斷條件即可保證穩定性。

總結：冒泡排序是原地排序，并且穩定，復雜度為O((1+n)*n/2)的算法。

插入排序

????????插入排序原理比較難描述，類似于我們斗地主理牌的過程，原先是亂序的，左邊第一個作為依據，依次在亂序中找第一個放到有序中。

int insertsort(int a[],int len)
{
??? // 插入排序，a表示數組，n表示數組大小
??? if (len <= 1) return;
??? int i = 0;
??? for (i = 1; i < len; ++i) {
??????? int value = a[i];
??????? int j = i - 1;
??????? // 查找插入的位置
??????? for (; j >= 0; --j) {
??????????? if (a[j] > value) {
??????????????? a[j+1] = a[j];? // 數據移動
??????????? } else {
??????????????? break;
??????????? }
??????? }
??????? a[j+1] = value; // 插入數據
??? }
}

分析：

復雜度：通過代碼可知，插入排序的復雜度比較難以計算，但可以確定的是O(n^2)。

空間復雜度：O(1),故是原地排序

穩定性：判斷條件是a[j] > value，即可保證穩定性

總結：插入排序是原地排序，具有穩定性的算法。

選擇排序

選擇排序原理：

設置最值位置標記，逐輪掃描未排序部分元素最值。
每一輪掃描過程中，以未排序部分首部元素為基準(將位置標記設置為未排序首元素下標)與后續元素進行比較。
遇到更小(或更大)的元素則將位置標記修改為其下標，直至掃描完成，將標記位置的元素與未排序部分首元素交換位置。
至多進行n-1輪掃描，序列完全有序。

其實，我認為選擇排序和插入排序類似，它比較的操作是在無序中，在無序中找到最值。插入排序是在有序中比較，將新值放到合適的地方。

int selectsort(int a[],int len)
{
??? if (len <= 1)
??????? return 0;
??? int i = 0;
??? int j = 0;
??? int index = 0;
??? int temp = 0;
??? for(i = 0 ; i < len ;i ++)
??? {
??????? for(j = i ,index = i; j < len; j ++ )
??????? {
??????????? if(a[index] > a[j])
??????????????? index = j;
??????? }
??????? temp = a[i];
??????? a[i] = a[index];
??????? a[index] = temp;
??? }
??? return 0;
}

分析：
空間復雜度：為O(1),原地排序
時間復雜度：為O(n^2)。
穩定性：不穩定。因為找到最小值之后，需要于無序中的首元素交換，這里會出現不穩定現象。例如：

比如 5，8，5，2，9 這樣一組數據，使用選擇排序算法來排序的話，第一次找到最小元素 2，與第一個 5 交換位置，那第一個 5 和中間的 5 順序就變了，所以就不穩定了。

總結：選擇排序是原地排序，復雜度為O(n^2),不穩定的算法

歸并排序

歸并操作的工作原理如下：

如果要排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。

其中的問題就是如何獲取兩個排好序的部分：當數組長度變為1，是不是就已經相當于排好序了（實際上不需要再排序），這個時候再將長度為1的數組合并到一起，就變成了長度為2的有序數組。

int merge(int a[],int left , int mid, int right)
{
??? int * arr = (int
*)malloc(sizeof(int)*
(right-left+1));
??? memset(arr,0,sizeof(int)*(right-left+1));
??? int i = left;
??? int j = mid+1;
??? int m = 0;
??? while(i <= mid && j <= right)
??? {
??????? if(a[i]< a[j])
??????? {
??????????? arr[m++] = a[i++];
??????? }
??????? else
??????? {
??????????? arr[m++] = a[j++];
??????? }
??? }
??? if(i>mid)
??? {
??????? for(;? j <= right ; j++)
??????????? arr[m++] = a[j];
??? }
??? else
??? {
??????? for(; i <= mid ; i++)
??????????? arr[m++] = a[i];
??? }
??? for(i = 0 ; i <= right - left; i++)
??????? a[left+i] = arr[i];
??? return 0;
}
int mergesort_separate(int a[], int start, int end)
{
??? if(start >= end)
??????? return 0;
??? int i =(int) ((start+end)/2);
??? mergesort_separate(a,start,i);
??? mergesort_separate(a,i+1,end);
??? merge(a,start,i,end);
}
int mergesort(int a[],int len)
{
??? mergesort_separate(a,0,len-1);
}

其中merge()函數是核心。需要好好品味。

分析：

從歸并算法的實現中，我們依舊從穩定性，是否是原地排序？，時間復雜度來分析。

穩定性：我們知道merge()函數包括主要的數據搬移工作，只要保證這里穩定即可。是可以滿足的。所以歸并排序是穩定算法。

原地排序：在merge()函數中，我們需要將兩個有序數組合并，需要用到額外的臨時數組，故空間復雜度是O(n),故歸并排序不是原地排序

時間復雜度：我們知道歸并排序的時間復雜度是O(nlogn)，但是至于怎么推導出來的，肯定很多人都處于茫然狀態。這里我就稍微推導一下，看不懂沒有關系。

假設數據量為n，歸并排序的復雜度為T(n),由于歸并排序的思路是將大問題分解為小問題，
再將小問題的結果合并。
故T(n) = T(n/2)+T(n/2)+n;其中n表示將結果合并消耗的時間。
T(n) = 2
*T(n/2)+n = 4*
T(n/4)+4n = 8
T(n/8)+8n
*T(n) = 2^kT(n/2^k)+2^k*
n
當 n/2^k=1時，T(n) = 2^k+2^k*n，將k帶入得：T(n) = logn+n*logn=n*logn。

故歸并排序的時間復雜度為O(n*logn);

快速排序

快速排序原理：

如果要排序數組中下標從 p 到 r 之間的一組數據，我們選擇 p 到 r 之間的任意一個數據作為 pivot（分區點）。我們遍歷 p 到 r 之間的數據，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。

經過這一步驟之后，數組 p 到 r 之間的數據就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的

分析

穩定性：在快速排序中，需要對數組進行搬移，比如：6，8，7，6,3，5，4,會發生不穩定。所以快速排序是不穩定。

原地排序：由于交換數據時，只需要一個臨時變量，空間復雜度為O(1),故快速排序是原地排序。

時間復雜度：同歸并排序同理，快速排序的事件復雜度也是O(n*logn)。

注意：快速排序 在大部分情況下的時間復雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n^2)。

問題：O(n) 時間復雜度內求無序數組中的第 K 大元素？

思路：一般情況下，我們需要先進行排序，再通過下標直接訪問。雖然數組的訪問復雜度是O(1),但是排序較為耗時，即使使用歸并排序和快速排序也是O(n*logn)。

???????既然該題出現在這里，很容易想到會用到歸并排序和快速排序。比較一下兩者實現的原理，發現快速排序比較適合這道題。當我們sort()返回的mid等于K-1。是不是就表示a[mid],就是第K大的元素（mid左邊由K-1個數，都比mid小。雖然不是有序，但沒有影響）。當mid+1<K時，說明第K大的元素在[mid+1,end]之間。反之在[start,mid-1]之間。

int sort(int a[],int start, int end)
{
??? int target = a[end];
??? int i = start;
??? int j = start;
??? int temp = 0;
??? for(j = start ; j < end ; j++)
??? {
??????? if(a[j] < target)
??????? {
??????????? temp = a[i];
??????????? a[i] = a[j];
??????????? a[j] = temp;
??????????? i++;
??????? }
??? }
??? temp = a[i];
??? a[i]=target;
??? a[end] = temp;
??? return i;
}
int findKnum(int a[], int start ,int end,int K)
{
??? int mid = sort(a,start,end);
??? int result = 0;
??? if(mid+1 == K )
??? {
??????? result=? a[mid];
??? }
??? else if(mid+1 < K)
??? {
????? result = findKnum(a,mid+1,end,K);
??? }
??? else
??? {
????? result = findKnum(a,start,mid-1,K);
??? }
?? return result;
}
int main()
{
??????? int a[10]={1,3,5,7,4,9,10,8,6,2};
??????? printf("%d\n",findKnum(a,0,9,6));
??????? return 0;
}

分析：為什么該解法的復雜度是O(n)呢？

假設復雜度為T(n),我們已知sort的復雜度是O(n),當我們第一次沒有找到正確元素是，我們只需在n/2個數據中進行查找。同理接下來的復雜度是n/4,n/8...直至數組長度為1，及找到對應數據（最壞情況）。這很明顯是等比數列。T(n)=2n-1=O(n)。

桶排序

桶排序原理：核心思想是將要排序的數據分到幾個有序的桶里，每個桶里的數據再單獨進行排序。桶內排完序之后，再把每個桶里的數據按照順序依次取出，組成的序列就是有序的了。

復雜度為什么是O(n)?

如果要排序的數據有 n 個，我們把它們均勻地劃分到 m 個桶內，每個桶里就有 k=n/m 個元素。每個桶內部使用快速排序，時間復雜度為 O(k * logk)。m 個桶排序的時間復雜度就是 O(m * k * logk)，因為 k=n/m，所以整個桶排序的時間復雜度就是 O(n*log(n/m))。當桶的個數 m 接近數據個數 n 時，log(n/m) 就是一個非常小的常量，這個時候桶排序的時間復雜度接近 O(n)。

注意：

上述的情況是桶排序最好的情況，即每個桶中的數據均勻。最壞情況，所有數據都集中再一個桶中的話，那么復雜度就會退化到O(nlogn)
我覺得桶排序的思想并不困難，關鍵在于元素值域的劃分，也就是值到桶之間的映射規則。(確定規則之后，就可以確定桶的數量f(max) - f(min)+1)。
實際上桶排序是用空間換時間來提高處理速度的。

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int sort(int a[],int start, int end)
{
??? int target = a[end];
??? int i = start;
??? int j = start;
??? int temp = 0;
??? for(j = start ; j < end ; j++)
??? {
??????? if(a[j] < target)
??????? {
??????????? temp = a[i];
??????????? a[i] = a[j];
??????????? a[j] = temp;
??????????? i++;
??????? }
??? }
??? temp = a[i];
??? a[i]=target;
??? a[end] = temp;
??? return i;
}
int quicksort(int a[], int start, int end)
{
??? if(start >= end)
??????? return 0;
??? int mid = sort(a,start,end);
??? quicksort(a,start,mid-1);
??? quicksort(a,mid+1,end);
}
int insertnum(int a[],int len,int num)
{
??? int i = 0;
??? while(i<len)
??? {
??????? if(a[i]==0)
??????? {
??????????? a[i] = num;
??????????? break;
??????? }
??????? i++;
??? }
??? return 0;
}
int main()
{
??????? int a[20]={1,3,5,7,4,9,10,8,6,2,12,13,15,14,17,16,19,18,20,11};
??????? //這個二位數組是我們根據數據源分析出來的
??????? int buket[5][5] = {0};
??????? int i = 0;
??????? for(i = 0 ; i < 20 ; i++)
??????? {
??????????? insertnum(buket[a[i]/5],5,a[i]);
??????? }
??????? for(i = 0 ; i < 5 ;i ++)
??????????? quicksort(buket[i],0,4);

??????? int j = 0;
??????? for(i = 0 ; i < 5 ; i ++)
??????? {
??????????? for(j = 0 ; j < 5 ; j ++)
??????????????? buket[i][j] == 0 ? :printf("%d\n",buket[i][j]);

??????? }
??????? return 0;
}

分析

????????由于數據源較為簡單和均勻，所以我選擇間隔為5作為映射函數。將數據放到[0,4]5個桶中，再將每個桶中的數據進行排序，再一次將五個桶中的數據依次輸出。

????????桶排序只要映射函數合理，那么其復雜度是O(n),這一點我們已經介紹過了。

????????桶排序需要額外的內存用于桶，空間復雜度是O(n+m),其中m是桶的個數。

????????桶排序在將數據隱射到桶的過程是穩定的。但是在排序的過程中如果你選擇的是快速排序，就不是穩定的了，如上面的例子。若選擇歸并排序，就是穩定排序。

計數排序

計數排序和桶排序的原理類似，更像是特例：

????????當要排序的 n 個數據，所處的范圍并不大的時候，比如最大值是 k，我們就可以把數據劃分成k個桶。每個桶內的數據值都是相同的，省掉了桶內排序的時間。

int findmaxmin(int a[],int len, int*max ,int *min)
{
??? if(len == 0)
??????? return 0;
??? int i = 0;
??? *max = a[0];
??? *min = a[0];
??? for(i = 0; i < len ; i++)
??? {
??????? if(a[i] > *max)
??????????? *max = a[i];
??????? else if(a[i] < *min)
??????????? *min = a[i];
??? }
??? return 0;
}
int countsort(int a[],int len)
{
??? int max,min = 0;
??? findmaxmin(a,len,&max,&min);
??? int *count = (int *) malloc((max-min+1)*sizeof(int));
??? memset(count,0,(max-min+1)*sizeof(int));
??? int i = 0 ;
??? for(i = 0 ; i < len ; i++)
???????? count[a[i]-min]++; /
*count*
/
??? for(i = 1 ; i < max-min+1 ; i++)
??????? count[i] += count[i-1];
??? int
*target = (int *
**) malloc(len**
sizeof(int));
*??? memset(target,0,len*
sizeof(int));
??? for(i = 0 ; i < len ; i++)
??? {
??????? target[--count[a[i] - min]] = a[i];
??? }
??? memcpy(a,target,sizeof(int)*len);
??? free(count);
??? free(target);
}
int main()
{
??????? int a[20]={10,12,11,13,13,15,14,12,11,14,15,15,14,13,12,11,13,12,10,10};
??????? countsort(a,20);
??????? int i = 0;
??????? for(i = 0 ; i < 20 ; i ++)
??????? {
??????????? printf("%d\n",a[i]);
??????? }
??????? return 0;
}

分析

????????計數排序的時間復雜度為O(n),在算法的過程中涉及到了4個循環.第一個是在數據源中找到最大最小值；第二次循環是遍歷數據源，統計數據出現的次數；第三次遍歷確認數據的位置；第四次遍歷，是進行排序。

計數排序的空間復雜度是O(n+max-min)。故不是原地排序。

????????計數排序在進行排序時在第四個循環中進行的。若判斷條件為for(i = len -1 ; i > 0 ; i-- )，排序就是穩定的。否則就不是穩定的。

????????注意：計數排序只能用在數據范圍不大的場景中，如果數據范圍 k 比要排序的數據 n 大很多，就不適合用計數排序了。而且，計數排序只能給非負整數排序，如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。

基數排序

基數排序原理：其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。

????????我覺得基數排序和計數排序類似，不過計數排序要求數據范圍max和min的差距不要太大。但是當數據范圍很大時，很明顯計數排序和桶排序就不能在使用了。而基數排序就是從位的角度切入到計數排序。

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int findmaxbit(int a[],int len)
{
??? if(len == 0)
??????? return 0;
??? int bit = 0;
??? int temp= bit;
??? int i = 0 ;
??? int num = 0;
??? for(i = 0 ; i < len ; i++)
??? {
??????? num = a[i];
??????? temp = 0;
??????? while(num != 0 )
??????? {
??????????? num/=10;
??????????? temp++;
??????? }
??????? if(temp > bit)
?????????? bit = temp;
??? }
??? return bit;
}
int basesort(int a[],int len)
{
??? int max,min = 0;
??? int bit = findmaxbit(a,len);

??? int
*temp = (int*
)malloc(sizeof(int)*len);
??? int count[10] = {0};
??? int i = 0;
??? int j = 0;
??? int radix = 1;
??? for(j = 0 ; j < bit ; j++)
??? {
??????? memset(count,0,sizeof(int)*10);
??????? memset(temp,0,sizeof(int)*len);
??????? for(i = 0 ; i < len ; i++)
??????????? count[((int) a[i]/radix) %10]++;
??????? for(i = 1 ; i < 10 ; i++)
???????????? count[i]+= count[i-1];
??????? for(i = len -1? ; i >= 0? ; i--)
??????????? temp[--count[((int) a[i]/radix) %10]]=a[i];
??????? memcpy(a,temp,sizeof(int)
len);
*??????? radix*
=10;
??? }
??? free(temp);
??? return 0;
}
int main()
{
??????? int a[10]={56,123,12315,5312366,1234783,245671,123421,568421,643261,93458};
???????? basesort(a,10);

??????? int i = 0;
??????? for(i = 0 ; i < 10 ; i ++)
??????? {
??????????? printf("%d\n",a[i]);
??????? }
??????? return 0;
}