思路

數(shù)組排序任務(wù)可以如下完成：
1）設(shè)k=a[0], 將k挪到適當(dāng)位置，使得比k小的元素都
在k左邊,比k大的元素都在k右邊，和k相等的，不關(guān)心
在k左右出現(xiàn)均可 （O（n)時間完成）
2) 把k左邊的部分快速排序
3) 把k右邊的部分快速排序

圖解
一組數(shù)據(jù)：

7138121129

首先 左指針為i，右邊的指針為j，中間值為a[0]=7;
然后，左邊的讓著右邊的，右邊j向左移動，如下圖

發(fā)現(xiàn)2比7小停止移動了，所以2和7就進(jìn)行調(diào)換

這時候右邊的調(diào)換一次了，總不能一直讓右邊移動，太累了，這時候左邊開始移動了，但是他發(fā)現(xiàn)1比7小就沒停，繼續(xù)移動

發(fā)現(xiàn)3比7還是小，就繼續(xù)移動，一直移動到8停下來了

8比7大，所以8和7進(jìn)行了調(diào)換

這時候，右邊開始移動，發(fā)現(xiàn)11，12都比7大所以，沒有調(diào)換，最后ij都移動到了7的位置，他們倆相遇了，就停止了

對左右兩邊進(jìn)行遞歸，就會得到有序的數(shù)組了

代碼：

#include <iostream> using namespace std; void swap(int& a, int& b) //交換變量a,b值 { int tmp = a; a = b; b = tmp; } void QuickSort(int a[], int s, int e) {if (s >= e)//相當(dāng)于左指針跑到右指針右邊了，必然就停止了return;int k = a[s];//以a[s],即左邊第一個數(shù)為中間值int i = s, j = e;while (i != j) {while (j > i&& a[j] > k)//找不到比中間值小的就一直走--j;swap(a[i], a[j]);//找到了，進(jìn)行交換while (i < j && a[i] <= k)//找不到比中間值大的就一直走++i;swap(a[i], a[j]);//找到了，交換}//處理完后，a[i]=k;QuickSort(a, s, i - 1);//對左右兩邊遞歸，得到QuickSort(a, i + 1, e); } int a[] = { 93,27,30,2,8,12,2,8,30,89 }; int main() {int size = sizeof(a) / sizeof(int);QuickSort(a, 0, size - 1);for (int i = 0; i < size; ++i)cout << a[i] << ",";cout << endl;return 0; } }

總結(jié)

以上是生活随笔為你收集整理的快速排序图解(分治)--算法学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。