目录
1.交换排序
2.冒泡排序
2.1基本思路
1.1.2复杂度分析
3.快速排序
3.1基本思想
3.2Hoare版本（最初的）
3.2.1缺点
3.2.2优化
第一种——随机选key
第二种——三数取中
第三种——小区间优化
3.3挖坑版本（更好理解）
3.4前后指针法（最优秀的）
4.快速排序非递归版本
4.1递归版本的缺点
4.2使用非递归版本
4.3使用辅助栈
4.2.1Hoare版本
4.3.2挖坑法
4.3.3前后指针法
1.交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
交换排序最具代表的就是冒泡排序和快速排序
2.冒泡排序
2.1基本思路
我们知道冒泡排序的基本思想是两两对比，如果符合条件则交换。
我们知道，冒泡排序是从下标0和下标1的进行对比，交换（如果符号条件），然后下一轮就是下标1和下标2的比较，交换（如果符号条件），再就是下标2和3的进行比较，以此类推，我们就会发现，一趟遍历下来我们就能把最大的移动到最后面去，也就是选出最大值。这个时候最大值就不用再进行新的一轮比较了
也就是说下一趟比较的最大下标会是n-3和n-2这一组。第二趟完成了后这个时候n-2存放的就是第二大的值。依次类推，每一趟都能将次大值放到合适的位置
| 第j趟 | 第j躺排好第几大的值 | 第j趟排好的的第几大的值所在下标 |
| 1 | 1 | n-1 |
| 2 | 2 | n-2 |
| 3 | 3 | n-3 |
| ... | ... | ... |
| n-1 | n-1 | 1 |
| n | n | 0 |
大家有没有发现第三列不就是i的最大值吗？
确实是，因为要产生第j大的值，只能把它放后面去，刚好最后一个位置的下标是n-1，所以第j大的值理所应当放到n-j的位置上面去，也就是说，冒泡排序必须比到这个位置
// 最坏：O(N^2)
// 最好：O(N)
//升序
void BubbleSort(int* a, int n)
{
for (int j = 1; j <= n; j++)//代表在进行第j趟冒泡排序，并且能在这趟选出第j大的值
{
bool exchange = false;
for (int i = 1; i <= n - j; i++)//n-j+1是排好了的序列的第一个元素的下标
//第一次冒泡排序开始之前没有排好的序列
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = true;
}
}
if (exchange == false)
{
break;
}
}
}
我们看个例子
1.1.2复杂度分析
时间复杂度：O(N^2)
空间复杂度：O(1)
3.快速排序
终于我们的高手要登场了，如果将来你工作后，你的老板要让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
事实上，不论是C++STL、Java SDK或者.NET FrameWorkSDK等开发工具包中的源代码中都能找到它的某种实现版本。
快速排序算法最早是由图灵奖获得者Tony Hoare设计出来的，他在形式化方法理论以及ALGOL60编程语言的发明中都有卓越的贡献，是20世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。
更牛的是，我们现在要学习的这个快速排序算法，被列为20世纪十大算法之一。我们这些玩编程的人还有什么理由不去学习它呢？
希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。
而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。
3.1基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的快体现在它使用了分而治之的思想，首先我们以第一个数3为基数
小于等于3的数放到左边，注意3放在最右边
大于3的放到右边 ，接着以231三个数的第一个数2为基数
小于等于2的放在左边，2放在末尾
大于2的放在右边
依次类推，直到左右两边只有一个数为止。
我们发现将每个分枝末尾的数依次从前往后放到一起，就是排好序的数列
下面将介绍多种以这个为基本思想的实现版本
3.2Hoare版本（最初的）
我们直接上图片
这样子我们就完成一轮了，然后我们要在key的左右边再选一个key值，然后依次类推，完成排序
这里有一个点，就是相遇的地方的值一定比key小，为什么？
有的人可能会好奇第二点，L不是找大的吗？怎么比key小呢？这是因为啊在上一轮循环中，L确实是找大的，但是后面它和R找到的小的的值进行了交换，在这轮循环时L的位置还没有变化，所以执向的还是比key值小的
代码
//快速排序（Hoare版本） void QuickSort1(int* a, int begin, int end) { if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作 return; int left = begin;//L int right = end;//R int keyi = left;//key的下标 while (left < right) { //right先走，找小 while (left < right&&a[right] >= a[keyi]) { right--; } //left后走，找大 while (left < right&&a[left] <= a[keyi]) { left++; } if (left < right)//交换left和right的值 { Swap(&a[left], &a[right]); } } int meeti = left;//L和R的相遇点 Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值 //递归 QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作 QuickSort1(a, meeti + 1, end);//key的右序列进行此操作 }时间复杂度O(N*logN)
我们可以看动图再理解一下
3.2.1缺点
快速排序是一种高效的排序算法，其核心思想基于分治法。在最理想的情况下，即每次划分都能将数组分为两个几乎相等的子序列时，快速排序的时间复杂度为O(nlogn)。
然而，在最坏的情况下，对逆序和有序的序列使用快速排序，即每次选择的pivot（基准值）都是最大或最小元素，导致每次只能排除一个元素，剩下的元素还需要继续排序，这样会形成类似冒泡排序的情况，需要进行大约n次的划分，每次划分需要遍历几乎所有元素，因此时间复杂度退化为O(n^2)。
如果给了一个有序的序列，我们选择了第一个元素为key，我们使用快排，发现了错误
我们发现栈溢出了
3.2.2优化
针对上面的有序/逆序的情况，我们对Hoare版本进行了优化
我们发现上面那个时间复杂度很大的原因是key值的选择选择了最大的/小的，因此我们采取新的方法，把最左边那个的值换成不是最大/小的
第一种——随机选key
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
// 随机选key
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
int keyi = left;
while (left < right)
{
// 右边找小
while (left < right && a[right] >= a[keyi])
--right;
// 左边找大
while (left < right && a[left] <= a[keyi])
++left;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
// [begin, keyi-1] keyi [keyi+1, end]
// 递归
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}第二种——三数取中
在三个数里选择不是最大的也不是最小的，获取它的下标，这个性能非常有限
int GetMidNumi(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
// 三数取中
int midi = GetMidNumi(a, left, right);
if(midi != left)
Swap(&a[midi], &a[left]);
int keyi = left;
while (left < right)
{
// 右边找小
while (left < right && a[right] >= a[keyi])
--right;
// 左边找大
while (left < right && a[left] <= a[keyi])
++left;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
// [begin, keyi-1] keyi [keyi+1, end]
// 递归
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}第三种——小区间优化
我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。
//优化后的快速排序
void QuickSort0(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
return;
if (end - begin + 1 > 20)//可自行调整
{
//可调用快速排序的单趟排序三种中的任意一种
//int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
int keyi = PartSort3(a, begin, end);
QuickSort0(a, begin, keyi - 1);//key的左序列进行此操作
QuickSort0(a, keyi + 1, end);//key的右序列进行此操作
}
else
{
//HeapSort(a + begin, end - begin + 1);
ShellSort(a + begin, end - begin + 1);//当序列长度小于等于20时，使用希尔排序
}
}
3.3挖坑版本（更好理解）
有了上面Hoare版本的基础，我们直接把挖坑版的动画放出来，相信你们一定能看懂把！
挖坑法的单趟排序的基本步骤如下：
- 选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
- 还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）。
- 在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）
经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。
//快速排序（挖坑法）
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
return;
int left = begin;//L
int right = end;//R
int key = a[left];//在最左边形成一个坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇点
a[meeti] = key;//将key抛入坑位
QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
}
同样的我们可以对它进行优化
// 挖坑法
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
// 三数取中
int midi = GetMidNumi(a, left, right);
if (midi != left)
Swap(&a[midi], &a[left]);
int key = a[left];
int hole = left;
while (left < right)
{
// 右边找小
while (left < right && a[right] >= key)
--right;
a[hole] = a[right];
hole = right;
// 左边找大
while (left < right && a[left] <= key)
++left;
a[hole] = a[left];
hole = left;
}
a[hole] = key;
// [begin, hole-1] hole [hole+1, end]
// 递归
QuickSort2(a, begin, hole - 1);
QuickSort2(a, hole + 1, end);
}3.4前后指针法（最优秀的）
这种可能是这三种方法里面最优秀的快排版本了
cur一直在找小
前后指针法的单趟排序的基本步骤如下：
- 选出一个key，一般是最左边或是最右边的。
- 起始时，prev指针指向序列开头，cur指针指向prev+1。
- 若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可。
经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。
代码：
//快速排序（前后指针法）
void QuickSort3(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
return;
//三数取中
int midIndex = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[midIndex]);
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)//当cur未越界时继续
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界时，prev的位置
Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
}
4.快速排序非递归版本
4.1递归版本的缺点
4.2使用非递归版本
我们看一下栈展开图
从上面的栈展开图得到递归条件变化的是区间
也就是说栈帧里存的是区间，所以我们用辅助栈的时候，也存的是区间
每次递归函数区间都会被分割，缩小。所以我们在栈里存放的也就是区间通过栈里的区间对序列进行分割，不再使用递归分治的方法分割区间。
- 首先将最初的序列左右区间入栈，要想使用左区间需要先将右区间入栈，然后左区间再入栈（栈的特点）。
- 然后就开始使用栈来辅助修改循环。当栈不为空栈时，就将栈里区间出栈，一次出两个值，也就是左右区间。当左右区间出栈后，我们就可以根据左右区间对序列进行单趟排序选出key，key就将序列分成两个子序列，而这两个子序列又代表着两个区间，再将它们入栈，注意要先将右子序列区间入栈再将左序列区间入栈，然后再出栈重复上面的操作。
- 当出栈的区间拿来分割子序列时，子序列无法再分割了没有区间，就不用入栈。
4.3使用辅助栈
当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。
快速排序的非递归算法基本思路：
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
3、反复执行步骤2，直到栈为空为止。
代码：
//快速排序（非递归实现）
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;//创建栈
StackInit(&st);//初始化栈
StackPush(&st, begin);//待排序列的L
StackPush(&st, end);//待排序列的R
while (!StackEmpty(&st))
{
int right = StackTop(&st);//读取R
StackPop(&st);//出栈
int left = StackTop(&st);//读取L
StackPop(&st);//出栈
//该处调用的是Hoare版本的单趟排序
int keyi = PartSort1(a, left, right);
if (left < keyi - 1)//该序列的左序列还需要排序
{
StackPush(&st, left);//左序列的L入栈
StackPush(&st, keyi - 1);//左序列的R入栈
}
if (keyi + 1 < right)// 该序列的右序列还需要排序
{
StackPush(&st, keyi + 1);//右序列的L入栈
StackPush(&st, right);//右序列的R入栈
}
}
StackDestroy(&st);//销毁栈
}O(NlogN)
4.2.1Hoare版本
Hoare版本的单趟排序代码：
//Hoare版本（单趟排序）
int PartSort1(int* a, int left, int right)
{
int keyi = left;//key的下标
while (left < right)
{
//right走，找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left先走，找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
Swap(&a[left], &a[right]);//交换left和right的值
}
}
int meeti = left;//L和R的相遇点
Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
return meeti;//返回相遇点，即key的当前位置
}4.3.2挖坑法
挖坑法的单趟排序代码：
//挖坑法（单趟排序）
int PartSort2(int* a, int left, int right)
{
int key = a[left];//在最左边形成一个坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇点
a[meeti] = key;//将key抛入坑位
return meeti;//返回key的当前位置
}4.3.3前后指针法
前后指针法的单趟排序代码：
//前后指针法（单趟排序）
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//当cur未越界时继续
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界时，prev的位置
Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
return meeti;//返回key的当前位置
}
