冒泡排序：
重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到不再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名。
算法步驟：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。對所有元素在一趟比較之後，最後的元素應該就是最大的數。
3.針對除最後已排好序的所有的元素重復以上步驟1和2，直到沒有任何一對數字需要比較。
時間復雜度：
若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數和記錄移動次數均達到最小值：C(min) = n-1, M(min) = 0。所以，冒泡排序最好的時間復雜度為：o(n)。
若初始文件是反序的，需要進行趟排序。每趟排序要進行次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：C(max) = n(n-1)/2 = o(n^2) M(max) = 3n(n-1)/2 = o(n^2)。所以，冒泡排序的最壞時間復雜度：o(n^2)
綜上，因此冒泡排序總的平均時間復雜度為：o(n^2)。
空間復雜度：
該算法只有在進行數據交換時最多需要一個臨時變量，因此空間復雜度為o(1)。
算法穩定性：
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，則不需要進行交換；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，因此相同元素的前後順序不會發生改變，冒泡排序是一種穩定排序算法。
[cpp]
#include <stdio.h>
void Swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int arr[],int len)
{
/*需要n-1趟排序*/
for (int i = 0; i < len - 1; ++i)
{
for (int j = 0; j < len -1 - i; ++j)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j],&arr[j+1]);
}
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
BubbleSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
void Swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int arr[],int len)
{
/*需要n-1趟排序*/
for (int i = 0; i < len - 1; ++i)
{
for (int j = 0; j < len -1 - i; ++j)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j],&arr[j+1]);
}
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
BubbleSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}直接插入排序：
有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序。
算法步驟：
1.從第一個元素開始，該元素可以認為已經被排序。
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描。
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置。
4. 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置。
5. 將新元素插入到下一位置中。
6. 重復步驟2。
時間復雜度：
如果目標是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間復雜度為O(n^2）。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。
空間復雜度：
直接插入排序只有需要一個臨時變量存儲將要插入的數據，因此空間復雜度為o(1)。
算法穩定性：
直接插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。
[cpp]
#include <stdio.h>
void InsertSort(int arr[],int n)
{
for (int i = 1; i < n; ++i)
{
int tmp = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] > tmp ; --j)
{
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
InsertSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
void InsertSort(int arr[],int n)
{
for (int i = 1; i < n; ++i)
{
int tmp = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] > tmp ; --j)
{
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
InsertSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}希爾排序：
希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。
算法步驟：
先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
時間復雜度：
希爾排序的時間復雜度與增量序列的選取有關，例如希爾增量時間復雜度為O(n^2)，而Hibbard增量的希爾排序的時間復雜度為O(N^(5/4))，但是現今仍然沒有人能找出希爾排序的精確下界。
空間復雜度：
希爾排序只有需要一個臨時變量存儲將要插入的數據，因此空間復雜度為o(1)。
算法穩定性：
由於進行了多次直接插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以希爾排序是不穩定的。
[cpp]
#include <stdio.h>
void ShellSort1(int arr[],int n)
{
/*步長為gap，每次排序後gap減半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*對各組進行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
void ShellSort2(int arr[],int n)
{
/*步長為gap，每次排序後gap減半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*對各組進行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j -gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
arr[j -gap] = tmp ;
}
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
ShellSort1(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
void ShellSort1(int arr[],int n)
{
/*步長為gap，每次排序後gap減半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*對各組進行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
void ShellSort2(int arr[],int n)
{
/*步長為gap，每次排序後gap減半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*對各組進行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j -gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
arr[j -gap] = tmp ;
}
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
ShellSort1(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
簡單選擇排序：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
算法步驟：
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
1.初始狀態：無序區為R[1..n]，有序區為空。
2.第1趟排序在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
3.第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
時間復雜度：
選擇排序的交換操作介於 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介於 0 和 3 (n - 1） 次之間。 比較次數O(n^2），比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+...+1=n*(n-1）/2。交換次數O(n），最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。因此簡單選擇排序的時間復雜度是O(n^2)。
空間復雜度：
這裡需要一個額外的空間存儲當前臨時的最小值，因此空間復雜度為O(1)。
算法穩定性：
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以選擇排序不是一個穩定的排序算法。
[cpp]
#include <stdio.h>
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SimpleSelectSort(int arr[],int len)
{
for (int i = 0; i < len; ++i)
{
int min_index = i;
for (int j = i + 1; j < len ; ++j)
{
if (arr[j] < arr[min_index])
{
min_index = j;
}
}
if (min_index != i)
{
swap(&arr[i],&arr[min_index]);
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
SimpleSelectSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SimpleSelectSort(int arr[],int len)
{
for (int i = 0; i < len; ++i)
{
int min_index = i;
for (int j = i + 1; j < len ; ++j)
{
if (arr[j] < arr[min_index])
{
min_index = j;
}
}
if (min_index != i)
{
swap(&arr[i],&arr[min_index]);
}
}
}
int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
SimpleSelectSort(arr,len);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
堆排序：
堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素。
算法步驟：
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。 （1）用大根堆排序的基本思想 ：
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區 。
② 再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key 。
③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 …… 直到無序區只有一個元素為止。
（2）大根堆排序算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆。
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆（亦稱重建堆）。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。
時間復雜度：
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成。堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近於最壞性能。由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
空間復雜度：
和上面算法一樣，堆排序是就地排序，輔助空間為O(1）。
算法穩定性：
堆排序是不穩定的排序方法。
[cpp]
#include <stdio.h>
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
/*堆調整*/
void HeapAdjust(int *arr,int i,int size){
int lchild = 2*i+1; //節點i的左子節點
int rchild = 2*(i+1); //節點i的右子節點
int max = i;
if (i <= size/2) //只對非葉節點進行調整
{
if (lchild < size && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild < size && arr[rchild] > arr[max])
{
max = rchild;
}
if (max != i)
{
swap(&arr[i],&arr[max]);
HeapAdjust(arr,max,size);//對調整過的max節點重新進行堆調整
}
}
}
/*建立無序大頂堆*/
void BulidHeap(int *arr,int size)
{
for (int i = size/2; i >= 0; --i)
{
HeapAdjust(arr,i,size);
}
}
/*堆排序*/
void HeapSort(int *arr, int size)
{
BulidHeap(arr,size);
for (int i = size - 1; i > 0; --i)
{
swap(&arr[0], &arr[i]);
HeapAdjust(arr,0,i);
}
}
int main(int argc, char const *argv[])
{
int size = 10;
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
HeapSort(arr, size);
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
/*堆調整*/
void HeapAdjust(int *arr,int i,int size){
int lchild = 2*i+1; //節點i的左子節點
int rchild = 2*(i+1); //節點i的右子節點
int max = i;
if (i <= size/2) //只對非葉節點進行調整
{
if (lchild < size && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild < size && arr[rchild] > arr[max])
{
max = rchild;
}
if (max != i)
{
swap(&arr[i],&arr[max]);
HeapAdjust(arr,max,size);//對調整過的max節點重新進行堆調整
}
}
}
/*建立無序大頂堆*/
void BulidHeap(int *arr,int size)
{
for (int i = size/2; i >= 0; --i)
{
HeapAdjust(arr,i,size);
}
}
/*堆排序*/
void HeapSort(int *arr, int size)
{
BulidHeap(arr,size);
for (int i = size - 1; i > 0; --i)
{
swap(&arr[0], &arr[i]);
HeapAdjust(arr,0,i);
}
}
int main(int argc, char const *argv[])
{
int size = 10;
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
HeapSort(arr, size);
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
歸並排序：
歸並（Merge）排序法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列的排序算法。歸並排序是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。它將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為2-路歸並。
算法步驟：
歸並操作的工作原理如下：第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置重復步驟3直到某一指針達到序列尾將另一序列剩下的所有元素直接復制到合並序列尾。
例如：
如 設有數列{6，202，100，301，38，8，1}
初始狀態：[6] [202] [100] [301] [38] [8] [1] 比較次數
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]3
i=2[ 6 100 202 301 ] [ 1 8 38 ]4
i=3 [ 1 6 8 38 100 202 301 ]4
總計： 11次
時間復雜度：
將參加排序的初始序列分成長度為1的子序列進行第一趟排序，得到 n / 2 個長度為 2 的各自有序的子序列（若n為奇數，還會存在一個最後元素的子序列），再調用排序函數進行第二趟排序，得到 n / 4 個長度為 4 的各自有序的子序列， 第 i 趟排序就是兩兩歸並長度為 2^(i-1) 的子序列得到 n / (2^i) 長度為 2^i 的子序列，直到最後只剩一個長度為n的子序列。由此看出，一共需要 log2n 趟排序，每一趟排序的時間復雜度是 O(n), 由此可知 該算法的總的時間復雜度是是 O(n log2n)。
空間復雜度：
歸並排序算法需要和原數據規模一樣大的輔助空間 ，因此其空間復雜度是 O(n)。
算法穩定性：
歸並（Merge）排序法是一個穩定的排序算法。
[cpp]
#include <stdio.h>
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int tmp[10];
void Merge(int begin,int middle,int end)
{
int i = begin;
int j = middle + 1;
int k = begin;
while(i <= middle && j <= end)
{
if (arr[i] <= arr[j] )
{
tmp[k++] = arr[i++];
}
else
{
tmp[k++] = arr[j++];
}
}
while(i <= middle)
{
tmp[k++] = arr[i++];
}
while(j <= end)
{
tmp[k++] = arr[j++];
}
for (k = begin; k <= end; ++k)
{
arr[k] = tmp[k];
}
}
void MergeSort(int begin,int end)
{
if (begin < end)
{
int middle = (begin + end) / 2;
MergeSort(begin,middle);
MergeSort(middle + 1,end);
Merge(begin,middle,end);
}
}
int main(int argc, char const *argv[])
{
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
MergeSort(0,len - 1);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
return 0;
}
#include <stdio.h>
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int tmp[10];
void Merge(int begin,int middle,int end)
{
int i = begin;
int j = middle + 1;
int k = begin;
while(i <= middle && j <= end)
{
if (arr[i] <= arr[j] )
{
tmp[k++] = arr[i++];
}
else
{
tmp[k++] = arr[j++];
}
}
while(i <= middle)
{
tmp[k++] = arr[i++];
}
while(j <= end)
{
tmp[k++] = arr[j++];
}
for (k = begin; k <= end; ++k)
{
arr[k] = tmp[k];
}
}
void MergeSort(int begin,int end)
{
if (begin < end)
{
int middle = (begin + end) / 2;
MergeSort(begin,middle);
MergeSort(middle + 1,end);
Merge(begin,middle,end);
}
}
int main(int argc, char const *argv[])
{
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
MergeSort(0,len - 1);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
return 0;
}
快速排序：
快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
算法步驟：
一趟快速排序的算法是：
1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由後開始向前搜索（j -- ），找到第一個小於key的值A[j]，A[i]與A[j]交換；
4）從i開始向後搜索，即由前開始向後搜索（i ++ ），找到第一個大於key的A[i]，A[i]與A[j]交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後令循環結束。
例如：
待排序的數組A的值分別是：（初始關鍵數據：key=49） 注意關鍵key永遠不變，永遠是和key進行比較，無論在什麼位置，最後的目的就是把key放在中間，小的放前面大的放後面。
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
49 38 65 97 76 13 27
進行第一次交換後：27 38 65 97 76 13 49
( 按照算法的第三步從後面開始找，此時:J=6）
進行第二次交換後：27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找>key的值，65>49,兩者交換，此時：I=2 )
進行第三次交換後：27 38 13 97 76 49 65
( 按照算法的第五步將又一次執行算法的第三步從後開始找
進行第四次交換後：27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大於key的值，97>49，兩者交換，此時：I=3,J=5 )
此時再執行第三和四步的時候就發現i=J=4，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所有大於key49的數全部在49的後面，所有小於key（49）的數全部在key（49）的前面。
時間復雜度：
快速排序每次將待排序數組分為兩個部分，在理想狀況下，每一次都將待排序數組劃分成等長兩個部分，則需要logn次劃分。而在最壞情況下，即數組已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為冒泡排序，所以快速排序時間復雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應用中，快速排序的平均時間復雜度為O(nlogn)。
空間復雜度：
快速排序需要一個額外的空間存儲關鍵元素（pivot element）,因此空間復雜度為O(1)。
算法穩定性：
快速排序不穩定，且是在關鍵元素和某個元素發生交換時導致穩定性被破壞，比如序列5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下標從1開始計)交換就會破壞元素3的穩定性。
[cpp]
#include <stdio.h>
#include <string.h>
#include <malloc.h>
void swap(int *a,int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int *arr,int low,int high)
{
int pivot = arr[low];
while(low < high)
{
while(low < high && arr[high] >= pivot)
{
high--;
}
if (low < high)
{
swap(&arr[low],&arr[high]);
low++;
}
while(low < high && arr[low] <= pivot)
{
low++;
}
if(low < high)
{
swap(&arr[low],&arr[high]);
high--;
}
}
return low;
}
void quickSort(int *arr,int low,int high)
{
int pivotpos;
if (low < high)
{
pivotpos = partition(arr,low,high);
quickSort(arr,low,pivotpos-1);
quickSort(arr,pivotpos+1,high);
}
}
int main(int argc, char const *argv[])
{
int n ;
printf("please input the length of arr:\n");
scanf("%d",&n);
//int *arr = (int*)malloc(n * sizeof(int));
int arr[n];
printf("please input %d numbers for each elements\n", n);
for(int i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
quickSort(arr,0,n-1);
for (int i = 0; i < n; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <string.h>
#include <malloc.h>
void swap(int *a,int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int *arr,int low,int high)
{
int pivot = arr[low];
while(low < high)
{
while(low < high && arr[high] >= pivot)
{
high--;
}
if (low < high)
{
swap(&arr[low],&arr[high]);
low++;
}
while(low < high && arr[low] <= pivot)
{
low++;
}
if(low < high)
{
swap(&arr[low],&arr[high]);
high--;
}
}
return low;
}
void quickSort(int *arr,int low,int high)
{
int pivotpos;
if (low < high)
{
pivotpos = partition(arr,low,high);
quickSort(arr,low,pivotpos-1);
quickSort(arr,pivotpos+1,high);
}
}
int main(int argc, char const *argv[])
{
int n ;
printf("please input the length of arr:\n");
scanf("%d",&n);
//int *arr = (int*)malloc(n * sizeof(int));
int arr[n];
printf("please input %d numbers for each elements\n", n);
for(int i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
quickSort(arr,0,n-1);
for (int i = 0; i < n; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
