十大經典排序演算法詳解及優化

演算法概述

0.1 演算法分類

十種常見排序演算法可以分為兩大類:

非線性時間比較類排序:通過比較來決定元素間的相對次序,由於其時間複雜度不能突破O(nlogn),因此稱為非線性時間比較類排序。

線性時間非比較類排序:不通過比較來決定元素間的相對次序,它可以突破基於比較排序的時間下界,以線性時間執行,因此稱為線性時間非比較類排序。 

0.2 演算法複雜度

0.3 相關概念

穩定:如果a原本在b前面,而a=b,排序之後a仍然在b的前面。

不穩定:如果a原本在b的前面,而a=b,排序之後 a 可能會出現在 b 的後面。

時間複雜度:對排序資料的總的操作次數。反映當n變化時,操作次數呈現什麼規律。

空間複雜度:是指演算法在計算機內執行時所需儲存空間的度量,它也是資料規模n的函式。 

1、氣泡排序(Bubble Sort)

氣泡排序是一種簡單的排序演算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。 

1.1 演算法描述

  • 比較相鄰的元素。如果第一個比第二個大,就交換它們兩個;
  • 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對,這樣在最後的元素應該會是最大的數;
  • 針對所有的元素重複以上的步驟,除了最後一個;
  • 重複步驟1~3,直到排序完成。

1.2 動圖演示

1.3 程式碼實現

(1)優化1(優化外層迴圈):

     若在某一趟排序中未發現氣泡位置的交換,則說明待排序的無序區中所有氣泡均滿足輕者在上,重者在下的原則,因此,氣泡排序過程可在此趟排序後終止。為此,在下面給出的演算法中,引入一個標籤flag,在每趟排序開始前,先將其置為0。若排序過程中發生了交換,則將其置為1。各趟排序結束時檢查flag,若未曾發生過交換則終止演算法,不再進行下一趟排序。

(2)優化2(優化內層迴圈)

       記住最後一次交換髮生位置lastExchange的氣泡排序。在每趟掃描中,記住最後一次交換髮生的位置lastExchange,(該位置之後的相鄰記錄均已有序)。下一趟排序開始時,R[1..lastExchange-1]是無序區,R[lastExchange..n]是有序區。這樣,一趟排序可能使當前無序區擴充多個記錄,因此記住最後一次交換髮生的位置lastExchange,從而減少排序的趟數。

#include<iostream>  
using namespace std;  
#include<cassert>  
//氣泡排序  
void BubbleSort1(int* arr, size_t size)  
{  
assert(arr);  
int i = 0, j = 0;  
for (i = 0; i < size - 1; i  )//一共要排序size-1次  
{  
for (j = 0; j < size - 1 - i; j  )//選出該趟排序的最大值往後移動  
{  
if (arr[j] > arr[j   1])  
{  
int tmp = arr[j];  
arr[j] = arr[j   1];  
arr[j   1] = tmp;  
}  
}  
}  
}  
//氣泡排序優化1  
void BubbleSort2(int* arr, size_t size)  
{  
assert(arr);  
int i = 0, j = 0;  
for (i = 0; i < size - 1; i  )//一共要排序size-1次  
{  
//每次遍歷標誌位都要先置為0,才能判斷後面的元素是否發生了交換  
int flag = 0;  
for (j = 0; j < size - 1 - i; j  )//選出該趟排序的最大值往後移動  
{  
if (arr[j] > arr[j   1])  
{  
int tmp = arr[j];  
arr[j] = arr[j   1];  
arr[j   1] = tmp;  
flag = 1;//只要有發生了交換,flag就置為1  
}  
}  
//判斷標誌位是否為0,如果為0,說明後面的元素已經有序,就直接return  
if (flag == 0)  
{  
return;  
}  
}  
}  
//氣泡排序優化2  
void BubbleSort3(int* arr, size_t size)  
{  
assert(arr);  
int i = 0, j = 0;  
int k = size - 1,pos = 0;   //pos變數用來標記迴圈裡最後一次交換的位置       
for (i = 0; i < size - 1; i  )  //一共要排序size-1次  
{  
//每次遍歷標誌位都要先置為0,才能判斷後面的元素是否發生了交換  
int flag = 0;  
for (j = 0; j < k; j  )//選出該趟排序的最大值往後移動  
{  
if (arr[j] > arr[j   1])  
{  
int tmp = arr[j];  
arr[j] = arr[j   1];  
arr[j   1] = tmp;  
flag = 1;   //只要有發生了交換,flag就置為1  
pos = j;    //迴圈裡最後一次交換的位置 j 賦給pos  
}  
}  
k = pos;  
//判斷標誌位是否為0,如果為0,說明後面的元素已經有序,就直接return  
if (flag == 0)  
{  
return;  
}  
} 
}  
int main()  
{  
int arr[5] = { 5,4,3,2,1 };  
cout << "初始順序為:";  
for (int i = 0; i < 5; i  )  
{  
cout << arr[i] << " ";  
}  
cout << endl;  
/*BubbleSort1(arr, 5);*/  
/*BubbleSort2(arr, 5);*/  
BubbleSort3(arr, 5);  
cout << "氣泡排序後順序為:";  
for (int i = 0; i < 5; i  )  
{  
cout << arr[i] << " ";  
}  
cout << endl;  
system("pause");  
return 0;  
}  

2、選擇排序(Selection Sort)

選擇排序(Selection-sort)是一種簡單直觀的排序演算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。 

2.1 演算法描述

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法描述如下:

  • 初始狀態:無序區為R[1..n],有序區為空;
  • 第i趟排序(i=1,2,3…n-1)開始時,當前有序區和無序區分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k],將它與無序區的第1個記錄R交換,使R[1..i]和R[i 1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區;
  • n-1趟結束,陣列有序化了。

2.2 動圖演示

  

2.3 程式碼實現

(1)優化

在每一次查詢最小值的時候,也可以找到一個最大值,然後將兩者分別放在它們應該出現的位置,這樣遍歷的次數就比較少了。程式碼中,第一次交換結束後,如果left那個位置原本放置的就是最大數,交換之後,需要將最大數的下標還原。 需要注意的是,每次記住的最小值或者最大值的下標,這樣方便進行交換。

//選擇排序
void SelectSort(vector<int>& v)
{
for(int i = 0; i < v.size() - 2;   i)
{
int k = i;
for(int j = i   1; j < v.size() - 1;   j)
{
//找到最小的數的下標
if(v[j] < v[k])
k = j;
}
if(k != i)
{
swap(v[k],v[i]);
}
}
}
//優化
void SelectSort(vector<int>& a)
{
int left = 0;
int right = a.size() - 1;
int min = left;//儲存最小值的下標
int max = left;//儲存最大值的下標
while(left <= right)
{
min = left;
max = left;
for(int i = left; i <= right;   i)
{
if(a[i] < a[min])
{
min = i;
}
if(a[i] > a[max])
{
max = i;
}
}
swap(a[left],a[min]);
if(left == max)
max = min;
swap(a[right],a[max]);
left;
--right;
}
}

2.4 演算法分析

表現最穩定的排序演算法之一,因為無論什麼資料進去都是O(n2)的時間複雜度,所以用到它的時候,資料規模越小越好。唯一的好處可能就是不佔用額外的記憶體空間了吧。理論上講,選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序資料,在已排序序列中從後向前掃描,找到相應位置並插入。

3.1 演算法描述

一般來說,插入排序都採用in-place在陣列上實現。具體演算法描述如下:

  • 從第一個元素開始,該元素可以認為已經被排序;
  • 取出下一個元素,在已經排序的元素序列中從後向前掃描;
  • 如果該元素(已排序)大於新元素,將該元素移到下一位置;
  • 重複步驟3,直到找到已排序的元素小於或者等於新元素的位置;
  • 將新元素插入到該位置後;
  • 重複步驟2~5。

3.2 動圖演示

3.2 程式碼實現

(1)優化1

改寫,將搜尋和資料後移這二個步驟合併。即每次a[i]先和前面一個資料a[i-1]比較,如果a[i] > a[i-1]說明a[0…i]也是有序的,無須調整。否則就令j=i-1,temp=a[i]。然後一邊將資料a[j]向後移動一邊向前搜尋,當有資料a[j]<a[i]時停止並將temp放到a[j 1]處。

(2)優化2

再對將a[j]插入到前面a[0…j-1]的有序區間所用的方法進行改寫,用資料交換代替資料後移。如果a[j]前一個資料a[j-1] > a[j],就交換a[j]和a[j-1],再j–直到a[j-1] <= a[j]。這樣也可以實現將一個新資料新併入到有序區間。

//插入排序
void Insertsort1(int a[], int n)  
{  
int i, j, k;  
for (i = 1; i < n; i  )  
{  
//為a[i]在前面的a[0...i-1]有序區間中找一個合適的位置  
for (j = i - 1; j >= 0; j--)  
if (a[j] < a[i])  
break;  
//如找到了一個合適的位置  
if (j != i - 1)  
{  
//將比a[i]大的資料向後移  
int temp = a[i];  
for (k = i - 1; k > j; k--)  
a[k   1] = a[k];  
//將a[i]放到正確位置上  
a[k   1] = temp;  
}  
}  
}  
//優化1
void Insertsort2(int a[], int n)  
{  
int i, j;  
for (i = 1; i < n; i  )  
if (a[i] < a[i - 1])  
{  
int temp = a[i];  
for (j = i - 1; j >= 0 && a[j] > temp; j--)  
a[j   1] = a[j];  
a[j   1] = temp;  
}  
}  
//優化2
void Insertsort3(int a[], int n)  
{  
int i, j;  
for (i = 1; i < n; i  )  
for (j = i - 1; j >= 0 && a[j] > a[j   1]; j--)  
Swap(a[j], a[j   1]);  
}  

3.4 演算法分析

插入排序在實現上,通常採用in-place排序(即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。

4、希爾排序(Shell Sort)

1959年Shell發明,第一個突破O(n2)的排序演算法,是簡單插入排序的改進版。它與插入排序的不同之處在於,它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

4.1 演算法描述

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,具體演算法描述:

  • 選擇一個增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列個數k,對序列進行k 趟排序;
  • 每趟排序,根據對應的增量ti,將待排序列分割成若干長度為m 的子序列,分別對各子表進行直接插入排序。僅增量因子為1 時,整個序列作為一個表來處理,表長度即為整個序列的長度。

4.2 動圖演示

4.3 程式碼實現

(1)優化1

shellsort1程式碼雖然對直觀的理解希爾排序有幫助,但程式碼量太大了,不夠簡潔清晰。因此進行下改進和優化,以第二次排序為例,原來是每次從1A到1E,從2A到2E,可以改成從1B開始,先和1A比較,然後取2B與2A比較,再取1C與前面自己組內的資料比較…….。這種每次從陣列第gap個元素開始,每個元素與自己組內的資料進行直接插入排序顯然也是正確的。

(2)優化2

將直接插入排序部分用直接插入排序的第三種方法來改

//希爾排序
void shellsort1(int a[], int n)  
{  
int i, j, gap;  
for (gap = n / 2; gap > 0; gap /= 2) //步長  
for (i = 0; i < gap; i  )        //直接插入排序  
{  
for (j = i   gap; j < n; j  = gap)   
if (a[j] < a[j - gap])  
{  
int temp = a[j];  
int k = j - gap;  
while (k >= 0 && a[k] > temp)  
{  
a[k   gap] = a[k];  
k -= gap;  
}  
a[k   gap] = temp;  
}  
}  
}  
//優化1
void shellsort2(int a[], int n)  
{  
int j, gap;  
for (gap = n / 2; gap > 0; gap /= 2)  
for (j = gap; j < n; j  )//從陣列第gap個元素開始  
if (a[j] < a[j - gap])//每個元素與自己組內的資料進行直接插入排序  
{  
int temp = a[j];  
int k = j - gap;  
while (k >= 0 && a[k] > temp)  
{  
a[k   gap] = a[k];  
k -= gap;  
}  
a[k   gap] = temp;  
}  
}  
//優化2
void shellsort3(int a[], int n)  
{  
int i, j, gap;  
for (gap = n / 2; gap > 0; gap /= 2)  
for (i = gap; i < n; i  )  
for (j = i - gap; j >= 0 && a[j] > a[j   gap]; j -= gap)  
Swap(a[j], a[j   gap]);  
}  

4.4 演算法分析

希爾排序的核心在於間隔序列的設定。既可以提前設定好間隔序列,也可以動態的定義間隔序列。動態定義間隔序列的演算法是《演算法(第4版)》的合著者Robert Sedgewick提出的。 

5、歸併排序(Merge Sort)

歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為2-路歸併。 

5.1 演算法描述

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列;
  • 對這兩個子序列分別採用歸併排序;
  • 將兩個排序好的子序列合併成一個最終的排序序列。

5.2 動圖演示

5.3 程式碼實現

void mergeArray(int arr[], int first, int mid, int last, int temp[])
{
int i = first;   //第一個序列開始位置
int j = mid   1; //第二個序列開始位置
int m = mid;     //第一個序列結束位置
int n = last;    //第二個序列結束位置
int k = 0;       //temp下標
while (i <= m && j <= n)  //序列一二是否放完
{
if (arr[i] < arr[j])  //k一直  ,i,j任意時刻只有一個  
temp[k  ] = arr[i  ];
else
temp[k  ] = arr[j  ];
}
while (i <= m)  //序列一是否放完
{
temp[k  ] = arr[i  ];
}
while (i <= m && j <= n)  //序列一二是否放完
{
temp[k  ] = arr[j  ];
}
//合併成一個有序序列
for (i = 0; i < k; i  )
{
arr[first   i] = temp[i];
}
}
void merge(int arr[], int first, int mid, int last, int temp[])
{
int mid;
if (first >= last)
return;
mid = (first   last) / 2;
merge(arr,first,mid,temp);
merge(arr, mid 1, last, temp);
mergeArray(arr, first, mid,last,temp);
}
void mergeSort(int arr[], int num)
{
int *temp = (int *)malloc(sizeof(arr[0])*num);
if (temp == NULL)
return;
merge(arr, 0, num - 1, temp);
}

5.4 演算法分析

歸併排序是一種穩定的排序方法。和選擇排序一樣,歸併排序的效能不受輸入資料的影響,但表現比選擇排序好的多,因為始終都是O(nlogn)的時間複雜度。代價是需要額外的記憶體空間。

6、快速排序(Quick Sort)

快速排序的基本思想:通過一趟排序將待排記錄分隔成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序。

6.1 演算法描述

快速排序使用分治法來把一個串(list)分為兩個子串(sub-lists)。具體演算法描述如下:

  • 從數列中挑出一個元素,稱為 “基準”(pivot);
  • 重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割槽退出之後,該基準就處於數列的中間位置。這個稱為分割槽(partition)操作;
  • 遞迴地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序。

6.2 動圖演示

6.3 程式碼實現

int QKPass(int r[], int left, int right)
{
int low = left;
int high = right;
r[0] = r[left];
while (low < high)
{
while (low < high && r[high] > r[0])
{
high--;
}
if (low < high)
{
r[low] = r[high];
low  ;
}
while (low < high && r[low] < r[0])
{
low  ;
}
if (low < high)
{
r[high] = r[low];
high--;
}
}
r[low] = r[0];
return low;
}
void QKSort(int r[], int low,int high)
{
if (low < high)
{
int pos = QKPass(r,low,high);
QKSort(r, low, pos - 1);
QKSort(r, pos   1, high);
}
}

優化1:三平均分割槽法

選用待排陣列最左邊、最右邊和最中間的三個元素的中間值作為中軸。通過比較選出其中的中值。取這3個值的好處是在實際問題中,出現近似順序資料或逆序資料的概率較大,此時中間資料必然成為中值,而也是事實上的近似中值。萬一遇到正好中間大兩邊小(或反之)的資料,取的值都接近最值,那麼由於至少能將兩部分分開,實際效率也會有2倍左右的增加,而且利於將資料略微打亂,破壞退化的結構。

資料集較小時,不必繼續遞迴呼叫快速排序演算法,而改為呼叫其他的對於小規模資料集處理能力較強的排序演算法來完成。Introsort就是這樣的一種演算法,它開始採用快速排序演算法進行排序,當遞迴達到一定深度時就改為堆排序來處理。克服了快速排序在小規模資料集處理中複雜的中軸選擇,也確保了堆排序在最壞情況下O(n log n)的複雜度。
//introsort 演算法實現
//資料量的分界線,決定了使用quick sort/heap sort還是insertion sort
const int threshold=16;
//堆排序用到的輔助函式
int parent(int i)
{
return (int)((i-1)/2);
}
int left(int i)
{
return 2 * i 1;
}
int right(int i)
{
return (2 * i   2);
}
void heapShiftDown(int heap[], int i, int begin,int end)
{
int l = left(i-begin) begin;
int r = right(i-begin) begin;
int largest=i;
//找出左右位元組點與父節點中的最大者
if(l < end && heap[l] > heap[largest])
largest = l;
if(r < end && heap[r] > heap[largest])
largest = r;
//若最大者不為父節點,則需交換資料,並持續向下滾動至滿足最大堆特性
if(largest != i)
{
swap(heap[largest],heap[i]);
heapShiftDown(heap, largest, begin,end);
}
}
//自底向上的開始建堆,即從堆的倒數第二層開始
void buildHeap(int heap[],int begin,int end)
{
for(int i = (begin end)/2; i >= begin; i--)
{
heapShiftDown(heap, i, begin,end);
}
}
//堆排序
void heapSort(int heap[], int begin,int end)
{
buildHeap(heap,begin,end);
for(int i = end; i >begin; i--)
{
swap(heap[begin],heap[i]);
heapShiftDown(heap,begin,begin, i);
}
}
//插入排序
void insertionSort(int array[],int len)
{
int i,j,temp;
for(i=1;i<len;i  )
{
temp = array[i];//store the original sorted array in temp
for(j=i;j>0 && temp < array[j-1];j--)//compare the new array with temp(maybe -1?)
{
array[j]=array[j-1];//all larger elements are moved one pot to the right
}
array[j]=temp;
}
}
//三點中值
int median3(int array[],int first,int median,int end)
{
if(array[first]<array[median])
{
if(array[median]<array[end])
return median;
else if(array[first]<array[end])
return end;
else
return first;
}
else if(array[first]<array[end])
return first;
else if(array[median]<array[end])
return end;
else 
return median;
}
//對陣列分割
int partition(int array[],int left,int right,int p)
{
//選擇最右側的元素作為分割標準
int index = left;
swap(array[p],array[right]);
int pivot = array[right]; 
//將所有小於標準的點移動到index的左側	
for (int i=left; i<right; i  )
{
if (array[i] < pivot)    
swap(array[index  ],array[i]);
}
//將標準與index指向的元素交換,返回index,即分割位置
swap(array[right],array[index]);
return index;
}
//遞迴的對陣列進行分割排序
void introSortLoop(int array[],int begin,int end,int depthLimit)
{
while((end-begin 1)>threshold) //子陣列資料量大小,則交給後面的插入排序進行處理
{
if(depthLimit==0)      //遞迴深度過大,則由堆排序代替
{
heapSort(array,begin,end);
return ;
}
--depthLimit;
//使用quick sort進行排序
int cut=partition(array,begin,end,
median3(array,begin,begin (end-begin)/2,end)); 
introSortLoop(array,cut,end,depthLimit);
end=cut;    //對左半段進行遞迴的sort
}
}
//計算最大容忍的遞迴深度
int lg(int n)
{
int k;
for(k=0;n>1;n>>=1)   k;
return k;
}
//霸氣的introsort
void introSort(int array[],int len)
{
if(len!=1)
{
introSortLoop(array,0,len-1,lg(len)*2);
insertionSort(array,len);
}
}

優化2:當分割槽的規模達到一定小時,便停止快速排序演算法。即快速排序演算法的最終產物是一個“幾乎”排序完成的有序數列。數列中有部分元素並沒有排到最終的有序序列的位置上,但是這種元素並不多。可以對這種“幾乎”完成排序的數列使用插入排序演算法進行排序以最終完成整個排序過程。因為插入排序對於這種“幾乎”完成的排序數列有著接近線性的複雜度。這一改進被證明比持續使用快速排序演算法要有效的多。

優化3:在遞迴排序子分割槽的時候,總是選擇優先排序那個最小的分割槽。這個選擇能夠更加有效的利用儲存空間從而從整體上加速演算法的執行。

對於快速排序演算法來說,實際上大量的時間都消耗在了分割槽上面,尤其是當要分割槽的所有的元素值都相等時,一般的快速排序演算法就陷入了最壞的一種情況,也即反覆的交換相同的元素並返回最差的中軸值。對於這種情況的一種改進辦法就是將分割槽分為三塊而不是原來的兩塊:一塊是小於中軸值的所有元素,一塊是等於中軸值的所有元素,另一塊是大於中軸值的所有元素。另一種簡單的改進方法是,當分割槽完成後,如果發現最左和最右兩個元素值相等的話就避免遞迴呼叫而採用其他的排序演算法來完成。

7、堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆這種資料結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或者大於)它的父節點。

7.1 演算法描述

  • 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆,此堆為初始的無序區;
  • 將堆頂元素R[1]與最後一個元素R[n]交換,此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n];
  • 由於交換後新的堆頂R[1]可能違反堆的性質,因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆,然後再次將R[1]與無序區最後一個元素交換,得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1,則整個排序過程完成。

7.2 動圖演示

7.3 程式碼實現

//堆排序
void HeapSort(int arr[],int len){
int i;
//初始化堆,從最後一個父節點開始
for(i = len/2 - 1; i >= 0; --i){
Heapify(arr,i,len);
}
//從堆中的取出最大的元素再調整堆
for(i = len - 1;i > 0;--i){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//調整成堆
Heapify(arr,0,i);
}
}
再看 調整成堆的函式
void Heapify(int arr[], int first, int end){
int father = first;
int son = father * 2   1;
while(son < end){
if(son   1 < end && arr[son] < arr[son 1])   son;
//如果父節點大於子節點則表示調整完畢
if(arr[father] > arr[son]) break;
else {
//不然就交換父節點和子節點的元素
int temp = arr[father];
arr[father] = arr[son];
arr[son] = temp;
//父和子節點變成下一個要比較的位置
father = son;
son = 2 * father   1;
}
}
}
var len;   // 因為宣告的多個函式都需要資料長度,所以把len設定成為全域性變數
function buildMaxHeap(arr) {  // 建立大頂堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) {    // 堆調整
var left = 2 * i   1,
right = 2 * i   2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}

8、計數排序(Counting Sort)

計數排序不是基於比較的排序演算法,其核心在於將輸入的資料值轉化為鍵儲存在額外開闢的陣列空間中。 作為一種線性時間複雜度的排序,計數排序要求輸入的資料必須是有確定範圍的整數。

8.1 演算法描述

  • 找出待排序的陣列中最大和最小的元素;
  • 統計陣列中每個值為i的元素出現的次數,存入陣列C的第i項;
  • 對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加);
  • 反向填充目標陣列:將每個元素i放在新陣列的第C(i)項,每放一個元素就將C(i)減去1。

8.2 動圖演示

8.3 程式碼實現

function countingSort(arr, maxValue) {
var bucket =new Array(maxValue   1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue   1;
for (var i = 0; i < arrLen; i  ) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]  ;
}
for (var j = 0; j < bucketLen; j  ) {
while(bucket[j] > 0) {
arr[sortedIndex  ] = j;
bucket[j]--;
}
}
return arr;
}

8.4 演算法分析

計數排序是一個穩定的排序演算法。當輸入的元素是 n 個 0到 k 之間的整數時,時間複雜度是O(n k),空間複雜度也是O(n k),其排序速度快於任何比較排序演算法。當k不是很大並且序列比較集中時,計數排序是一個很有效的排序演算法。

9、桶排序(Bucket Sort)

桶排序是計數排序的升級版。它利用了函式的對映關係,高效與否的關鍵就在於這個對映函式的確定。桶排序 (Bucket sort)的工作的原理:假設輸入資料服從均勻分佈,將資料分到有限數量的桶裡,每個桶再分別排序(有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排)。

9.1 演算法描述

  • 設定一個定量的陣列當作空桶;
  • 遍歷輸入資料,並且把資料一個一個放到對應的桶裡去;
  • 對每個不是空的桶進行排序;
  • 從不是空的桶裡把排好序的資料拼接起來。 

9.2 圖片演示

9.3 程式碼實現

function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i  ) {
if (arr[i] < minValue) {
minValue = arr[i];               // 輸入資料的最小值
}else if (arr[i] > maxValue) {
maxValue = arr[i];               // 輸入資料的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5;           // 設定桶的預設數量為5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize)   1;  
var buckets =new Array(bucketCount);
for (i = 0; i < buckets.length; i  ) {
buckets[i] = [];
}
// 利用對映函式將資料分配到各個桶中
for (i = 0; i < arr.length; i  ) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i  ) {
insertionSort(buckets[i]);                     // 對每個桶進行排序,這裡使用了插入排序
for (var j = 0; j < buckets[i].length; j  ) {
arr.push(buckets[i][j]);                     
}
}
return arr;
}

9.4 演算法分析

桶排序最好情況下使用線性時間O(n),桶排序的時間複雜度,取決與對各個桶之間資料進行排序的時間複雜度,因為其它部分的時間複雜度都為O(n)。很顯然,桶劃分的越小,各個桶之間的資料越少,排序所用的時間也會越少。但相應的空間消耗就會增大。 

10、基數排序(Radix Sort)

基數排序是按照低位先排序,然後收集;再按照高位排序,然後再收集;依次類推,直到最高位。有時候有些屬性是有優先順序順序的,先按低優先順序排序,再按高優先順序排序。最後的次序就是高優先順序高的在前,高優先順序相同的低優先順序高的在前。

10.1 演算法描述

  • 取得陣列中的最大數,並取得位數;
  • arr為原始陣列,從最低位開始取每個位組成radix陣列;
  • 對radix進行計數排序(利用計數排序適用於小範圍數的特點);

10.2 動圖演示

 

10.3 程式碼實現

// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i  , dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j  ) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j  ) {
var value =null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) !=null) {
arr[pos  ] = value;
}
}
}
}
return arr;
}

10.4 演算法分析

基數排序基於分別排序,分別收集,所以是穩定的。但基數排序的效能比桶排序要略差,每一次關鍵字的桶分配都需要O(n)的時間複雜度,而且分配之後得到新的關鍵字序列又需要O(n)的時間複雜度。假如待排資料可以分為d個關鍵字,則基數排序的時間複雜度將是O(d*2n) ,當然d要遠遠小於n,因此基本上還是線性級別的。

基數排序的空間複雜度為O(n k),其中k為桶的數量。一般來說n>>k,因此額外空間需要大概n個左右。