快速排序c++實現 快排C++ 第一、演算法描述 快速排序由C. A. R. Hoare在1962年提出，該演算法是目前實踐中使用最頻繁，實用高效的最好排序演算法， 快速排序演算法是採用分治思想的演算法，演算法分三個步驟 ...
快速排序c++實現 快排C++
第一、演算法描述
快速排序由C. A. R. Hoare在1962年提出，該演算法是目前實踐中使用最頻繁，實用高效的最好排序演算法，
快速排序演算法是採用分治思想的演算法，演算法分三個步驟
1.從數組中抽出一個元素作為基數v（我們稱之為劃界元素）,一般是取第一個、最後一個元素或中間的元素
2.將剩餘的元素中小於v的移動到v的左邊，將大於v元素移動到v的右邊
3.對左右兩個分區重覆以上步驟直到所有元素都是有排序好。
第二、演算法實現
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/*序列劃分函數*/
int partition(int a[], int p, int r) {
int key = a[r];//取最後一個
int i = p - 1;
for (int j = p; j < r; j++)
{
if (a[j] <= key)
{
i++;
//i一直代表小於key元素的最後一個索引，當發現有比key小的a[j]時候，i+1 後交換
exchange(&a[i], &a[j]);
}
}
exchange(&a[i + 1], &a[r]);//將key切換到中間來，左邊是小於key的，右邊是大於key的值。
return i + 1;
}
void quickSort(int a[], int p, int r) {
int position = 0;
if (p<r)
{
position = partition(a,p,r);//返回劃分元素的最終位置
quickSort(a,p,position-1);//劃分左邊遞歸
quickSort(a, position + 1,r);//劃分右邊遞歸
}
}
void main() {
int d[] = { 6,4,1,8,7,5 };
cout << "輸入數組 { 6,4,1,8,7,5 } " << endl;
quickSort(d, 0, 5);
print_arr(d, 6);
}
|
兩個輔助函數：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void exchange(int * a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void print_arr(int *a, int size) //列印函數
{
cout << "列印數組：";
for (int i = 0; i<size; i++) //列印數組
{
cout << a[i] << " ";
}
cout << endl << endl;
}
|
測試輸出：
第三、演算法圖解分析
下麵我們來具體分析下程式怎麼運行的，
quickSort(d, 0, 5);代表以靠最有一個元素5作為基數，
程式初始化時候p=0,r=5,i=-1,j=0,key=5
通過上圖我們觀察到：
1.i逐漸增加，它一直代表著小於key=5的最後一個元素，j也在主鍵增加，一直到key前面一個元素停止
2.此時迴圈到了最後一個元素7，以5為基數的迴圈已經結束，此時i=1，a[i+1]=6,交換6和5交換，完成本輪迴圈
返回i+1=2，依索引2為分界線拆分2個數組，進入遞歸迴圈，執行類似上圖操作
第四、總結
快速排序之所以快，相比冒泡排序他的交換是跳躍式的，它的最差時間複雜度是O(N2) 和冒泡一樣，但是它的平均時間複雜度是O(nlog2N),是一種就地排序演算法，
看了很多別人寫的演算法介紹，還是覺的不夠清晰，於是決定自己寫一篇博文，希望能幫助需要的人快速理解，文章中的用圖是自己畫的。
這個博客不錯推薦給大家：https://blog.csdn.net/gjggj/article/details/82962102
