快速排序

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次

一趟快速排序

排序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：

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--]);

swap(&arr[k],&arr[beg]);

quicksort(arr, beg, k);

quicksort(arr, r, end);

if (end - beg == 1)

swap(&arr[--k],&arr[beg]);