目录
一、交换排序
常见的排序算法有：
而本篇文章要介绍的是交换排序。
插入排序可以分为 冒泡排序 和 快速排序 。本文重点介绍了快速排序的认识
二、冒泡排序（bubble sort）
1. 基本思想
通过多次遍历待排序的序列，依次比较相邻元素，并根据大小关系交换它们的位置，使得每一轮遍历后，当前未排序部分的最大（或最小）元素“冒泡”到正确的位置。
2. 思路介绍
思路：
- 将待排序的数据划分为有序区和无序区，初始时有序区为空，无序区包含所有待排序数据。
- 对于无序区从前向后依次相邻数据进行比较，，若返序则交换，从而时值较小的数据向前移动，值较大的数据向后移动。（就像水中的气泡，体积大的现浮上来）
- 重复步骤2，直到无序区没有返序的数据。
对于一组数据：3，44，38，5，47，15，36，26，27，2，46，4，19，50，48 它的排序个过程如下：
排序动态图如下：
3. 代码实现
C语言代码实现：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)// n个数据比较n-1趟
{
for (int j = 1; j < n - i; j++)// 每一趟比较n-1-i
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
}
}
}
}4. 冒泡排序的优化
上述冒泡排序的代码中，可以发现无论数据是否有序，它都会消耗O(n^2)的时间性能。如果要解决这一问题，可以增加一个判断标志，判断是否已经有序。
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)// n个数据比较n-1趟
{
bool exchange = false;
for (int j = 1; j < n - i; j++)// 每一趟比较n-1-i
{
if (a[j - 1] > a[j])
{
//如果已经进入了需要交换的这一步，说明数据还存在无序的数据
Swap(&a[j - 1], &a[j]);
exchange = true;
}
}
if (exchange == false)
{
break;
}
}
}5. 特性总结
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
三、快速排序（quick sort）
1. 基本思想
快速排序是一种高效的分治排序算法，其核心思想是通过选择一个基准元素（pivot），将序列划分为两部分，使得基准元素的左边部分的所有元素小于等于基准值，基准元素的右边部分的所有元素大于等于基准值，然后递归地对这两部分进行排序，左右子序列重复该过程，直到所有元素都排列在相应位置上为止。最终完成整个序列的排序。
排序基本逻辑：
首先选择基准元素key值，基准值下标为keyi。然后进行划分，使得基准元素的左边部分的所有元素小于等于基准值，基准元素的右边部分的所有元素大于等于基准值，此时key所在位置的数据位置就定下来了。再分别对左右两边的区间 [left, keyi-1] 和 [keyi+1, right] 分别进行划分，当然每次划分后都会出现这两种区间，重复此过程，直到每个划分区间只有一个元素就停止划分。如图所示：
可以发现这二叉树有点相似。
代码逻辑实现（递归）：
// 假设按照升序对a数组中[left, right]区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if (left >= right)
return;
// 按照基准值对a数组的 [left, right]区间中的元素进行划分
int keyi = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right]
// 递归排[left, keyi-1]
QuickSort(array, left, keyi - 1);
// 递归排[keyi+1, right]
QuickSort(array, keyi + 1, right);
}2. 划分思路的分类
知道了快排的逻辑方法，只要通过划分找到每一次划分后的key的位置就可以完成这个快排算法了。对于划分方法，又可以分为多种，如：hoare法，挖坑法，前后指针法。但它们都有一个共同点：都需要选取一个位置的元素为基准值，我们选取的是最左边的位置或者最右边的位置，不会选取中间的位置。对于不同的排序，需要注意：
- 排升序：
- 如果选取左边做key，就要从右边先走，找小
- 如果选取右边做key，就要从左边先走，找大
- 排降序：
- 如果选取左边做key，就要从右边先走，找大
- 如果选取右边做key，就要从左边先走，找小
以下版本都是以选取左边做key，就要从右边先走，找小，排升序为例的。
（1）hoare版本
a. 思路介绍
划分操作：
对于区间 [left, right ] 进行一次划分（如果选取左边做key，就要从右边先走，找小--排升序为例）：
此时key所在位置是左边第一个元有位置。右边的right先开始向左移动，找比key值更小的元素，找到后停下，然后，左边的left才向右开始移动，找比key值大的元素，找到后停下，然后交换此时left和right所在的元素。重复操作，直到left和right相遇，相遇后就将key所在位置的元素与相遇位置的元素进行交换。此时，key的左边数据就都小于或等于key，右边数据就大于或等于key，将原来的区间划分为了两部分。
这样就完成了一次划分
如图是选取左边做key，右边取小的一次划分的一个动态图示例：
划分详细过程如下：
b. 代码实现
对于划分部分的代码实现：
//hoare版本
int partion(int* a, int left, int right)
{
//对[left,right]这部分区间的数据进行划分，并返回划分后的key值
int keyi = left;//初始时，key值在该区间最左边;keyi为key值的下标,因为通过下标才能修改数组的内容
while (left < right)
{
//右边找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左边找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);//交换左右两边的值
}
//此时left=right
Swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}（2）挖坑法
a. 思路介绍
进行划分的操作是：
对于区间 [left, right ] 进行一次划分（如果选取左边做key，就要从右边先走，找小--排升序为例）：
将基准值（左边第一个元素）放在一个临时变量key中，此时在第一个元素位置就形成了一个坑位，然后从右边（即另一边）开始找比key值更小的值，找到后，将找到的值放入上次的坑中，此时该位置有形成了一个坑，再从左边开始找比可以key值更大的值，找到后，将找到的值放入上一次形成的坑中。重复次操作，直到left与right相遇。相遇时，相遇为值又是一个坑，这时就将key值填入该位置。此时key的左边数据就都小于或等于key，右边数据就大于或等于key，将原来的区间划分为了两部分。
如图是挖坑法的选取左边做key，右边取小的一次划分的一个动态图示例：
b .代码实现
C语言实现：
//挖坑法
int partion(int* a, int left, int right)
{
//对[left,right]这部分区间的数据进行划分，并返回划分后的key值所在的位置
int key = a[left];//初始时，key值在该区间最左边;将a[left]的值用变量key存储起来
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;//此时形成新的坑位
}
//此时left=right=hole
a[hole] = key;
return hole;
}（3）前后指针版本
a. 思路介绍
对于区间 [left, right ] 进行一次划分的思路：
它需要两个指针prev和cur。初始时prev指向该序列最前面的开头，而cur指向prev的后一个位置。
然后开始判断cur指向的数据与key的大小：
- 如果cur指向的数据比key小，找到后，prev后移一位，再将prev和cur指向的数据相互互换，最后cur再后移一位。
- 如果cur指向的数据比key大，则只用将cur后移一位。
重复上述操作，直到cur越界，越界后就将prev指向的位置的数据与key所在位置进行交换。
这样也保证了此时key的左边数据就都小于或等于key，右边数据就大于或等于key，将原来的区间划分为了两部分。
说明：prev一定是在cur的前面的。
如图是前后指针法的选取左边做key，右边取小的一次划分的一个动态图示例：
b. 代码实现
C语言代码实现：
//前后指针法
int partion(int* a, int left, int right)
{
//对[left,right]这部分区间的数据进行划分，并返回划分后的key值
int keyi = left;//初始时，key值在该区间最左边;keyi为key值的下标,因为通过下标才能修改数组的内容
//在数组中，prev和cur用下标表示比较方便
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;//不论a[cur]比key大还是小，都会将cur后移
}
//此时cur已经越界
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}3. 对快速排序的优化
（1）优化的原因
时间复杂度最好情况：
理想状态下，快排每次在划分完后，都会产生2个大小相等的区间 [left, keyi-1] 和 [keyi+1, right]，而这2个区间再次进行划分，又会产生4个大小相等的区间，这4个区间继续进行划分，又会产生8个大小相等的区间，重复划分下去，直到每个区间中只有一个元素时才停止划分。
这种情况就和满二叉树的递归相似。这样子的时间性能就是快排中最好的情况。
时间复杂度是O(N*logN)。
时间复杂度最坏情况：
但是，如果我们要排序的是一个逆序的数据。我们还是选择第一个数据转为基准值key，那么这时在进行划分时，就不会有两个区间了。因为是逆序，那么就有：如果要排升序，而此时是一个降序的话，key仍然选择第一个数据，当进行第一次划分后，key就就处在最后一个位置了，此时，假如有n个数，那么key前面就有n-1个数据，后面就没有数据了，此时第一次划分就结束了。然后再对前面这个区间进行划分，如此重复的话，直到只剩第一个数据时排序才结束。如图：
同理，如果对一个升序，排降序也是如此。
当然这种情况是最坏的情况了，时间复杂度为。
原因：
以对一个降序，要排升序为例。由于是一个降序，所以第一个元素一定是最大的一个元素，最大的元素如果在升序中，一定是处于最后一个元素的，所以，对于第一次划分，就是将第一个元素固定位置，只是要固定的位置是最后一个元素而已，同样的，对于后续的区间划分也是如此。如此重复，就会出现这种情况了。
解决办法;
如果遇到这种情况，就需要对所选的基准值key进行调整，尽量不让它处于最大或最小，如果比较处在中间大小就很好了。
（2）优化办法
方法一：随机选key
由于我们所选的key的位置一定是在第一个或者最后一个，即位置不能变，所以就需要找一个值来与它进行交换。
那么就可以通过产生随机下标，让产生的随机下标对应的值与第一个位置的值进行交换。
C语言代码实现如下：
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//hoare版本
int partion1(int* a, int left, int 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]);//交换左右两边的值
}
//此时left=right
Swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
//挖坑法
int partion2(int* a, int left, int right)
{
// 随机选key
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
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;//此时形成新的坑位
}
//此时left=right=hole
a[hole] = key;
return hole;
}
//前后指针法
int partion3(int* a, int left, int right)
{
// 随机选key
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
int keyi = left;
//在数组中，prev和cur用下标表示比较方便
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;//不论a[cur]比key大还是小，都会将cur后移
}
//此时cur已经越界
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}方法二：三数取中
让待排序数组这个区间中的第一个数据、中间的数据以及最后一个数据，进行比较，选择中间的数据做key，当然这得到的数据也要和这个区间的第一个数据进行交换。
C语言代码实现如下：
//得到中间数
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 Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//hoare版本
int partion1(int* a, int left, int 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]);//交换左右两边的值
}
//此时left=right
Swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
//挖坑法
int partion2(int* a, int left, int 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;//此时形成新的坑位
}
//此时left=right=hole
a[hole] = key;
return hole;
}
//前后指针法
int partion3(int* a, int left, int right)
{
//三数取中
int midi = GetMidNumi(a, left, right);
if (midi != left)//避免重复
{
Swap(&a[midi], &a[left]);
}
int keyi = left;
//在数组中，prev和cur用下标表示比较方便
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;//不论a[cur]比key大还是小，都会将cur后移
}
//此时cur已经越界
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
4. 快速排序的非递归实现
快速排序的非递归实现需要借助 栈 这一数据结构来实现。
使用栈，其中在栈中存储的元素类型是区间。初始时，将待排序的数据的区间先入栈，然后通过取栈顶的操作，来得到待划分区间，然后间其出栈，再对所取的栈顶元素进行划分，划分完后，会产生两个区间，如果这两个区间中有元素个数一定大于1的区间，就将该元素个数一定大于1的区间入栈。后续重复次操作，直到栈为空才停止。这时就排完序了。
对于，某一数据进行的非递归快排的操作如图所示：
代码实现：
使用栈的结构，就需要使用到栈的处理函数。
栈的知识链接为：【数据结构】栈（stack）_数据结构栈-CSDN博客
则C语言代码实现：
void QuickSortNotRecursive(int* a, int left, int right)
{
Stack st;
Init(&st);
//存储区间
Interval tmp = { left,right };
//将初始数据区间入栈
Push(&st, tmp);
//直到栈空才停止
while (!IsEmpty(&st))
{
Interval cur = GetTop(&st);//取栈顶
Pop(&st);//出栈
int keyi= partion1(a, cur.left, cur.right);//划分区间
//划分后：[cur.left,keyi-1] [keyi+1，cur.right]
//判断是否有元素个数大于1的区间,若有，则将它们入栈
if (cur.left < keyi - 1)
{
Interval tmp = { cur.left,keyi - 1 };
Push(&st, tmp);
}
if (keyi + 1 < cur.right)
{
Interval tmp = { keyi + 1,cur.right };
Push(&st, tmp);
}
}
Destroy(&st);//销毁动态顺序表
}5. 特性总结
快速排序的特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
四、总结
- 冒泡排序通过多次遍历序列，比较相邻元素并交换位置，时间复杂度O(n²)，空间复杂度O(1)。
- 快速排序采用分治思想，选取基准值将序列划分为两部分递归排序，平均时间复杂度O(nlogn)，但最坏情况会退化为O(n²)，文章详细介绍了hoare、挖坑法和前后指针三种划分方法，并提出了随机选key和三数取中两种优化方案，最后还给出了快速排序的非递归实现。
感谢各位观看！希望能多多支持！