快速排序的递归与非递归实现

快排的基本概念

快速排序就是找一个数为基准值，遍历数组，小于基准值的在基准值左边，

大于基准值的在基准值右边，等于基准值的可以在左边或右边，

之后把数组从基准值的位置分开，一左一右，等于基准值的不用在排了，只需排小于的左边，

和大于的右边，也可以随便放一边就行，只要不跨到另一边，逻辑就没问题。

缺点：重复数多的时候，效率会变差。

快速排序的两个效率优化

一、三数取中

基准值的如果直接选最左边的值，

如果最左边的值就是数组的最小值，那么遍历一遍后根本没分出左右，左边啥也没有，

就成了去掉一个基准值再排一遍，

如果等待排序的是一个有序的数组或者接近有序的数组

快速排序的速度就跟冒泡一样慢了，

所以为了处理接近有序的数组，基准值选取三个数中不大不小的数

三个数分别是最左边的，最右边的和数组中间的

三个数中选一下，时间很快，但就可以避免遇到有序数组和接近有序的数组

如果数组是有无序的，那么三数取中和随便选一个没区别

但如果接近有序了，那么三数取中得到的基准值大概就是中间值，可以把数组分为大小相似的左右区间

代码实现 返回中间大小的数的地址

//三个数比大小选中间的 int* san_zhong(int* a, int* b, int* c) { if (*a > *b) { if (*c > *a) { return a; } else if(*b>*c) { return b; } else { return c; } } else { if (*c > *b) { return b; } else if (*c > *a) { return c; } else { return a; } } }

二、小区间优化

字面意思，如果数组很小的话就不用快速排序了，直接用插入排序

很小是多小？小到使用插入排序比快速排序更快

如果是递归的快速排序，长度10的数组要递归好几次，

如果是非递归的快速排序也是用栈模拟递归

但如果用插入排序就不需要递归了

空间和时间上都要更快

一个10万的数组要递归大概14万次。

加上小区间优化递归后就只需要递归大约3万次，省很多事。

快速排序的递归实现

快速排序有

左右指针法，这是最先研究出来的，不好理解

挖坑法，比左右指针法好理解

前后指针法，俩指针一前一后往后走

三个目的都一样让小于基准值的在前面，大于基准值的在右面

只是方法不一样

左右指针法

//快速排序递归实现+三选一优化+小区间插入排序优化 void kuai_pai_1(int* a, int left, int right) { if (left >= right) return; if (right - left + 1 < 11) { cha_ru(a + left, right - left + 1); return; } int zhong = left; int leftt = left; int rightt = right; int * q = san_zhong(&a[(left+right)/2],&a[left],&a[right]); jiao_huan(&a[zhong], q); while (left != right) { while (left != right && a[right] > a[zhong]) { right--; } while (left != right && a[left] <= a[zhong]) { left++; } jiao_huan(&a[left], &a[right]); } jiao_huan(&a[left], &a[zhong]); kuai_pai_1(a, leftt, left - 1); kuai_pai_1(a, right + 1, rightt); return; }

右指针往左走，遇到不大于基准值的数停下

左指针往右走，遇到比基准值大的数停下

之后交换俩数，没相遇就重复

最后俩指针相遇时停下的位置

停下的位置一定小于等于基准值

因为如果是右指针停下，左指针走的时候遇到右指针停下，右指针一定是在小于等于基准值的数上

左子针停下，是刚交换完右指针才走，左子针也停在小于等于基准值的数上，所以

停下的位置一定小于等于基准值

挖坑法

// 快速排序挖坑法 void kuai_pai_2(int* a, int left, int right) { if (left >= right) return; if (right - left + 1 < 11) { cha_ru(a + left, right - left + 1); return; } int leftt = left; int rightt = right; int* q = san_zhong(&a[(left + right) / 2], &a[left], &a[right]); jiao_huan(&a[left], q); int zhong = a[left]; while (left < right) { while (left < right && a[right] > zhong) { right--; } a[left] = a[right]; while (left < right && a[left] <= zhong) { left++; } a[right] = a[left]; } a[left] = zhong; kuai_pai_2(a, leftt, left - 1); kuai_pai_2(a, right + 1, rightt); return; }

开始存一下基准值，这样左边就算有一个坑

右指针左移动找小的，找到了把这个值放到左边挖好的坑里，这里就算新的坑，

左指针右移找大的，找到了把这个值给右指针的坑

最后相遇在一个坑里

把基准值的值放入坑中

跟左右指针法差不多，更好理解

前后指针法

// 快速排序前后指针法 void kuai_pai_3(int* a, int left, int right) { if (left >= right) return; if (right - left + 1 < 11) { cha_ru(a + left, right - left + 1); return; } int* q = san_zhong(&a[(left + right) / 2], &a[left], &a[right]); jiao_huan(&a[left], q); int qian = left; int hou = left+1; int zhong = a[left]; while (hou <= right) { if (a[hou] <= zhong&&++qian<hou) { jiao_huan(&a[qian], &a[hou]); } hou++; } jiao_huan(&a[qian], &a[left]); kuai_pai_3(a, left, qian-1); kuai_pai_3(a, qian + 1, right); return; }

前指针指向最左边，后指针指向最左边后一位

如果后指针指向了比基准值小的或一样的数，就前后指针一起往后移动一格，前指针先移动，

如果跟后指针位置不同就交换指向的数，

后指针若指向的大的数，前指针就不动了，

前指针移动的步数就是小于等于基准值的数的数量，第一个数是基准值，

后指针找到大的值，就会让前指针停下，等到后指针找到小的值，才会让前指针移动一步

交换后就把大的数移后面去了，

后指针走出数组，前指针的位置放入基准值，开头的位置放前指针指向的位置的值。

快速排序非递归法

// 快速排序 非递归实现 void kuai_pai_4(int* a, int lefttt, int righttt) { Stack arr; StackInit(&arr); StackPush(&arr, righttt); StackPush(&arr, lefttt); while (!StackEmpty(&arr)) { // 获取栈顶元素 int left = StackTop(&arr); // 出栈 StackPop(&arr); // 获取栈顶元素 int right = StackTop(&arr); // 出栈 StackPop(&arr); if (left >= right) { continue; } if (right - left + 1 < 11) { cha_ru(a + left, right - left + 1); continue; } int zhong = left; int leftt = left; int rightt = right; int* q = san_zhong(&a[(left + right) / 2], &a[left], &a[right]); jiao_huan(&a[zhong], q); while (left != right) { while (left != right && a[right] > a[zhong]) { right--; } while (left != right && a[left] <= a[zhong]) { left++; } jiao_huan(&a[left], &a[right]); } jiao_huan(&a[left], &a[zhong]); StackPush(&arr, left-1); StackPush(&arr, leftt); StackPush(&arr, rightt); StackPush(&arr, right+1); } StackDestroy(&arr); }

就是建造个栈，把需要递归的区间放入栈中，模拟递归，取一个区间，排完之后基准值的左区间和右区间放入栈，一直循环直到栈空了。把递归改为出栈入栈。