目录
递归实现
思路如下：
1.选择一个值作为基准值key(一般选最左边或最右边，在这里选最左边)。
2.定义L，R（分别为待排序序列最左边与最右边元素的下标)，L从左往右走，R从右往左走(若选最左边为key，R先走；选最右边为key，L先走)。
3.R从右往左走遇到比key小的停下来，接着L从左往右走，遇到比key大的停下来。然后交换R，L对应数组中的值。
4.重复上一步操作，直至L，R二者相遇。将相遇点对应的值与key对应的值交换，此时相遇点左边的值均小于相遇点所对应的值，右边的值均大于相遇点所对应的值。
5.相遇点将待排序序列分为两个子序列，用递归的方式重复上述操作。
6.当左右序列只有一个元素的时候排序完成。
void Swap(int* x, int* y) { int tmp; tmp = *x; *x = *y; *y = tmp; } //arr为待排序数组，start为待排序数组第一个元素的下标，end最后一个元素的下标 void QuickSort(int* arr,int start,int end) { int L = start;//Left int R = end;//Right int key = L;//选择最左边元素为key if (L >= R)//序列不存在或者只有一个元素 return; while (L<R) { //R先走，找小 while (L<R&&arr[R]>=arr[key]) { R--; } //L先走，找大 while (L < R && arr[L] <= arr[key]) { L++; } Swap(&arr[L], &arr[R]);//L,R都停下来了，交换 } //退出循环，L，R已经相遇 Swap(&arr[key],&arr[L]);//交换相遇处与key处的值 //此时key左边的值均小于key处的值，右边的值均大于key处的值 QuickSort(arr,start,L-1); QuickSort(arr,R + 1, end); }
用栈的思想实现
不使用递归进行快速排序，需要将单趟排序进行分装
int PartSort(int* arr, int start, int end) { int L = start;//Left int R = end;//Right int key = L;//选择最左边元素为key if (L >= R)//序列不存在或者只有一个元素 return L; while (L < R) { //R先走，找小 while (L < R && arr[R] >= arr[key]) { R--; } //L先走，找大 while (L < R && arr[L] <= arr[key]) { L++; } Swap(&arr[L], &arr[R]);//L,R都停下来了，交换 } //退出循环，L，R已经相遇 Swap(&arr[key], &arr[L]);//交换相遇处与key处的值 //此时key左边的值均小于key处的值，右边的值均大于key处的值 return L;//新的key——L,R相遇的位置 }
思路如下：
1.先将待排序序列最左边与最右边元素的下标入栈。
2.在栈不为空的情况下进入循环，读取栈中数据记作L，R。
3.将L,R传入部分排序函数，并返回一个将原序列分为左右两部分的下标，记作k。
4.判断左序列是否需要排序，若需要的话将左序列的L，R入栈。右序列进行一样操作。
5.反复执行上述操作，直至栈为空。
void QuickSort(int *arr,int start,int end) { struct Stack ps;//建立栈 StackInit(&ps);//栈的初始化 StackPush(&ps, start); StackPush(&ps, end); while (!StackEmpty(&ps))//栈不为空时进入循环 { int R = StackTop(&ps);//读取R StackPop(&ps);//栈顶出栈 int L = StackTop(&ps);//读取L StackPop(&ps);//栈顶出栈 int key = PartSort(arr,L,R); if (L < key-1)//左序列还要进行排序 { StackPush(&ps, L);//左序列L入栈 StackPush(&ps, key-1);//左序列R入栈 } if(R > key+1)//右序列还要进行排序 { StackPush(&ps, key + 1);//右序列L入栈 StackPush(&ps, R);//右序列R入栈 } } }
