赞
踩
目录
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
知道了QuickSort的基本思想后,我们先来实现其重复过程的基础,也就是它的第一步,实现---》左小右大。(当然也可以左大右小,就看你选哪边为基准值了)
首先,我们将对下面这组数据进行QuickSort的排序。
我们接着来取它的基准值,假如我们取它最左边的值为基准值(KEY),也就是下标为0的值,就是6这个值。那么,我们假设其最左边的的指针为left,最右边的指针为right。
在我们将其最左边的值作为基准值(KEY)之后,我们先让right先向左走。当其找到比KEY值小的数据的时候停下来。这时,left接着向右走,当其找到比KEY值大的数时停下来,并且同时交换right和left的值。
按照以上步骤一直循环,直到left和right相遇(奇遇偶错--奇数个数据相遇,偶数个数据错过)时,先将其共同指向的值和KEY指向的值交换,并且同时将KEY的下标也一并与相遇的数据下标交换。
到这里的时候,我们就实现了KEY这个基准值的左边都比它要小,它的右边都比其要大了,也就是左小右大了。
为啥我将最左边的值作为基准值(KEY)之后,得先让right先走呢?为啥不能是left先走呢?
回答:如果将最左边的值作为基准值(KEY)后,让left先走,那么相遇时的值会比KEY大,这时,如果交换KEY的值和下标,则无法实现左小右大了。
所以为了保证left和right相遇时的值比KEY小或相等(实现左小右大的前提),当我们将最左边的值作为基准值时,就得让right先走了。
当以左边为基准值(KEY)时,让右边先走。
当以右边为基准值(KEY)时,让左边先走。
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <time.h>
-
- int main() {
-
- TestQuick();
- return 0;
- }
-
-
- void TestQuick() {
-
- int a[] = {6,1,2,7,9,3,4,5,10,8};
- int len = sizeof(a) / sizeof(a[0]);
-
- QuickSort(a, 0,len - 1);
- PrintfArray(a, len);
-
- }
-
-
-
- void Swap(int* child, int* parent) {//交换数组中下标为child和parent的值
-
- int tmp;
- tmp = *child;
- *child = *parent;
- *parent = tmp;
-
- }
-
-
- void QuickSort(int* a, int begin, int end) {
-
- int left = begin, right = end;
- int key = left;
-
- //当left与right相遇时或刚要错过时跳出循环
- while (left < right) {
-
- //right向左走,找小。
- //并且同时为了防止极端情况,一直找不到小,如果没加left<right,会产生越界。
- while (left < right && a[right] >= a[key]) {
- right--;
- }
-
- //left向左走,找大。
- //并且同时为了防止极端情况,一直找不到大,如果没加left<right,会产生越界。
- while (left < right && a[left] <= a[key]) {
- left++;
- }
-
- //到这里就说明right找到了小,left找到了大。
- //所以需要交换下left和right的值。
- Swap(&a[left], &a[right]);
- }
-
- //到这里就说明left与right相遇
- //将KEY的值和下标与相遇的值和下标交换
- Swap(&a[left], &a[key]);
- key = left;
-
- }
其实这也比较容易理解:
我们上面已经实现了左小右大了吧,然后KEY的左子序列是不是都是比它小,右子序列都是比它大的。
那么,我们接下来先将其KEY的左子序列进行左小右大,在完成后紧接着对KEY的右子序列进行左小右大。这样,在其完成之后,其实也就是递归完成后,它的整体就成为了左小右大了,也就变有序了。
如下图:这里只递归到了最左边为空的一部分情况,感兴趣可以跟着代码自己画画完整的递归图,相信会对理解代码有更深理解。
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <time.h>
-
- int main() {
-
- TestQuick();
- return 0;
- }
-
-
- void TestQuick() {
-
- int a[] = {6,1,2,7,9,3,4,5,10,8};
- int len = sizeof(a) / sizeof(a[0]);
-
- QuickSort(a, 0,len - 1);
- PrintfArray(a, len);
-
- }
-
-
-
- void Swap(int* child, int* parent) {//交换数组中下标为child和parent的值
-
- int tmp;
- tmp = *child;
- *child = *parent;
- *parent = tmp;
-
- }
-
-
- void QuickSort(int* a, int begin, int end) {
-
- //当递归到空或则只有一个数据的时候
- if (begin >= end) {
- return;
- }
-
- int left = begin, right = end;
- int key = left;
-
- //当left与right相遇时或刚要错过时跳出循环
- while (left < right) {
-
- //right向左走,找小。
- //并且同时为了防止极端情况,一直找不到小,如果没加left<right,会产生越界。
- while (left < right && a[right] >= a[key]) {
- right--;
- }
-
- //left向左走,找大。
- //并且同时为了防止极端情况,一直找不到大,如果没加left<right,会产生越界。
- while (left < right && a[left] <= a[key]) {
- left++;
- }
-
- //到这里就说明right找到了小,left找到了大。
- //所以需要交换下left和right的值。
- Swap(&a[left], &a[right]);
- }
-
- //到这里就说明left与right相遇
- //将KEY的值和下标与相遇的值和下标交换
- Swap(&a[left], &a[key]);
- key = left;
-
- QuickSort(a, begin, key - 1);//左子序列递归实现左小右大
- QuickSort(a, key + 1, end);//右子序列递归实现左小右大
-
- }
好了,到这QucikSort就总结的差不多了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。