1.算法原理
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。
一趟快速排序的算法是：
1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]互換；
4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]互換；
5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
2.代碼
<code>static void swap(int* a,int* b){ int tmp = *b; *b = *a; *a = tmp;} void QuickSort(int *arr,int left,int right){ if (arr == NULL) { return; } if (left >= right) { return; } int key = arr[left]; int i = left; int j = right; while (i < j) { while (i < j && arr[j] >= key) { j--; } swap(&arr[j], &arr[i]); while (i < j && arr[i] <= key) { i++; } swap(&arr[i], &arr[j]); } QuickSort(arr,left,i-1); QuickSort(arr, i+1,right);}/<code>
分享到:
閱讀更多 知秋一葉h 的文章
