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(); }
