447
快速排序
49 38 65 97 76 13 27——————49原始
27 38 65 97 76 13 49——————49 1次
27 38 49 97 76 13 65——————49 2次
27 38 13 97 76 49 65——————49 3次
27 38 13 49 76 97 65——————49 4次
一趟快速排序
排序1：
#include <iostream> #include <time.h> #define ARYSIZE 100000 using namespace std; void QuickSort(int ary[], int nBegin, int nEnd) { int tKey = ary[nBegin]; int tLeft = nBegin; int tRight = nEnd;//以第一個數為參照做比較 if(tLeft >= tRight) { return; } while(tLeft < tRight) { while(tLeft < tRight && ary[tRight] >= tKey) { tRight--; } ary[tLeft] = ary[tRight]; while(tLeft < tRight && ary[tLeft] <= tKey) { tLeft++; } ary[tRight] = ary[tLeft]; } ary[tRight] = tKey; QuickSort(ary, nBegin, tRight-1); QuickSort(ary, tRight+1, nEnd);//遞歸 } int main(int argc, char *argv[]) { int ary[ARYSIZE] = {0}; srand((unsigned int)time(NULL)); for (int i = 0; i < ARYSIZE; ++i) { ary[i] = rand() % 100; } QuickSort(ary, 0, ARYSIZE - 1); getchar(); }
排序1比較塊；
排序2：
#include <iostream> #include <time.h> #define ARYSIZE 100000 using namespace std; void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; } void QuickSort(int arr[], int beg, int end) { if (end >= beg + 1) { int piv = arr[beg], k = beg + 1, r = end; while (k < r) { if (arr[k] < piv) { k++; } else { swap(&arr[k], &arr[r--]); } } if (arr[k] < piv) { swap(&arr[k],&arr[beg]); QuickSort(arr, beg, k); QuickSort(arr, r, end); } else { if (end - beg == 1) { return; } swap(&arr[--k],&arr[beg]); QuickSort(arr, beg, k); QuickSort(arr, r, end); } } } int main(int argc, char *argv[]) { int ary[ARYSIZE] = {0}; srand((unsigned int)time(NULL)); for (int i = 0; i < ARYSIZE; ++i) { ary[i] = rand() % 100; } QuickSort(ary, 0, ARYSIZE - 1); getchar(); }
最後更新：2017-04-02 06:51:35