快速排序的实现

目录

一、递归

        1、霍尔法：

2、挖坑法：

3、前后指针法：

二、非递归

三、完整代码：

---

基本思想：

先取这个待排序元素序列中的某一个元素最为key值，然后通过这个key值将这个序列分为两边，一边小于这个key，另一边大于这个key，然后接着对这个左边的序列和右边的序列进行相同的操作，直到所有的元素都在相应的位置上。

思路：

这里排序为升序

我们这里找最左边的元素作为key

定义一个变量指向最右边right，再来一个变量指向最左边left（注意，如果key在左边，那么就要从右边开始先走，如果key在右边，那么就要从左边开始走，这样才能保证这两个相遇的位置一定比key要小）

来个循环遍历这个序列：

right开始向左走找一个比key还要小的，

找到后left向右走找到一个比key还要大的，

接着交换这两个位置的元素。

所以结束条件就是left<right。

结束后交换此时这两个所在的共同位置和key的位置，key也要换到这个位置

最后再来递归即可（所以可以在最开始用两个变量begin和end记录left和right的位置）

OK！思路一出直接开写：

在写之前要两个函数，一个是交换函数：

另外一个为优化这个快速排序的代码：三数取中，也就是说在三个数中取中间大的那个数字

。这样可以使单趟排序后左边的和右边的元素个数差不多，进而减小递归的深度。

OK！现在可以开始写了

思路：

首先，将第一个元素存放在临时变量key中，此时将第一个元素定义为hole，这个时候这个hole就可以随便改了。

接着像霍尔法一样，right向左走找比key小的位置，此时将这个位置的元素赋值给hole，然后将hole改到这个right所在的位置。

然后left向右走找比key大的位置，找到后将这个位置的元素赋值给hole，然后将hole改到这个left所在的位置。

直到left == right后退出循环，此时将最开始的变量key放在hole中

最后左递归的区间为[begin, hole - 1]

        右递归的区间为[ hole + 1, end]

OK！思路一出，直接开写：

思路：

首先：定义最左边为key，然后最左边为prev，prev的下一个为cur

然后如果cur所在的值小于key，那么++prev，然后将cur所在的值和prev所在的值相交换，在cur++。

如果cur的值不小于key，那么就cur++。

退出循环的条件为cur小于right。

最后交换此时prev所在的元素和最左边的元素。

 

理解：

prev和cur之间要么紧跟着，要么prev和cur中间间隔着比key大的一段区间。

OK！思路一出，直接开写

这里QuickSort3返回值与上面不同为后面非递归的完成做铺垫。

思路：

因为递归可能会存在栈溢出，那么就需要把这个程序修改为非递归。

那么就需要栈和循环来帮助我们实现递归转非递归。

1、首先将这个序列的right先入栈，再将left入栈（顺序其实是无伤大雅的），

2、然后来个循环，结束条件为这个栈为空

3、在循环中定义begin访问栈顶的元素，就是上面的left（left后入栈的）

定义end访问栈顶元素的下一个为right。

4、接着用QuickSort3来进行单趟排序，返回值记录在keyi中。

所以里面区间就变成了：[begin,keyi-1] keyi [keyi+1, end]（左边比keyi小，右边比keyi大）

5、接着判断，如果keyi+1小于end，那么依次将end和keyi+1入栈，

                        如果keyi-1大于begin，那么将依次将keyi-1和begin入栈。       

所以此时循环上去就继续访问栈顶元素和栈顶元素的下一个来作为begin和end继续排序。

栈的代码：

快排代码：