c++ 快速排序算法【過程圖解】。本站提示廣大學習愛好者:(c++ 快速排序算法【過程圖解】)文章只能為提供參考,不一定能成為您想要的結果。以下是c++ 快速排序算法【過程圖解】正文
投稿:jingxian
下面小編就為大家帶來一篇c++ 快速排序算法【過程圖解】。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧第一、算法描述
快速排序由C. A. R. Hoare在1962年提出,該算法是目前實踐中使用最頻繁,實用高效的最好排序算法,
快速排序算法是采用分治思想的算法,算法分三個步驟
1.從數組中抽出一個元素作為基數v(我們稱之為劃界元素),一般是取第一個、最後一個元素或中間的元素
2.將剩余的元素中小於v的移動到v的左邊,將大於v元素移動到v的右邊
3.對左右兩個分區重復以上步驟直到所有元素都是有排序好。
第二、算法實現
/*序列劃分函數*/ 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); }
兩個輔助函數:
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),是一種就地排序算法,
看了很多別人寫的算法介紹,還是覺的不夠清晰,於是決定自己寫一篇博文,希望能幫助需要的人快速理解,文章中的用圖是自己畫的。
以上這篇c++ 快速排序算法【過程圖解】就是小編分享給大家的全部內容了,希望能給大家一個參考,也希望大家多多支持。