快速排序、二路快排、三路快排
1. 快速排序
1. 概念
快速排序采用分治的思想对数据进行排序
-
选择一个基准值
-
将比基准值小的放在基准值的左边，其余的（大于或者等于）放在右边
-
然后再对左边和右边继续进行划分，直到划分的区间长度为1
2. 时间复杂度
快速排序划分区间的时候为O(logN)，每次都需要时间复杂度为O(N)进行排序
所以快排的时间复杂度是O(NlogN)，这是将对于基准值可以大概可以将区间进行等分的情况下
如果数据已经有序，每次分治的时候就有可能导致一边没有一个数据，另一边却都是数据，这样就和冒泡排序一样了，时间复杂度是O(N^2)
综上所述：
最好的时间复杂度：O(NlogN)
最坏的时间复杂度：O(N^2)
3. 适合的场景
快速排序适合用于数据无序的情况，当数据有序的时候时间复杂度极有可能是O(N^2)，没有体现出快排的优点
4. 优化
-
当划分成小区间的时候，采用插入排序，不再使用快速排序
-
对于递归实现的快排可以改为非递归，使用栈来进行实现
-
每次选择基准值的时候，不再直接选择第一个或者最后一个元素。
可以采用三数取中法，或者随机选择一个基准值
5. 实现
对于快排的partion函数有着三种实现方法：
-
左右指针的方法
-
挖坑法
-
前后指针法
此处采用前后指针的方法，进行实现
//前后指针法
int Partion(int array[], int left, int right)
{
int cur = left;
int prev = cur - 1;
while (cur < right)
{
if (array[cur] <= array[right] && ++prev != cur)
{
std::swap(array[cur], array[prev]);
}
cur++;
}
std::swap(array[++prev], array[right]);
return prev;
}
void QuickSort(int array[], int left, int right)
{
if (array == nullptr)
{
return;
}
if (left < right)
{
int index = Partion(array, left, right);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
其他实现方法以及优化代码：https://github.com/YKitty/LinuxDir/blob/master/DS/Sort/Sort.c
2. 二路快排
1. 出现的原因
对于快排，如果数据元素过多并且元素的大小都是非常接近的，这时候左右分治的时候，就会导致一边全是数据，另一边没有数据，这样就会导致效率降低，时间复杂度变为O(N^2)
举例：用模板测试归并排序和快速排序的时间，设置一个1000000的数组，数组元素在0-10之间随机取值，那么用归并需要花费0.290727s而快排需要花费171.151s，对，你没有看错。当快速排序最优的时候是o（nlgn），而此时显然退化到了o（n^2）的级别。这是为什么？
对于上面我写的快排，将小于等于基准值的数据全都放到了左边，大于的放到右边了，那么这样就会出现问题。不管是当条件大于等于还是小于等于，当数组中重复元素非常多的时候，等于基准值的元素太多，那么数组就会分成极度不平衡的两个部分，因为等于基准值的一部分总是集中在数组的一边。
此时，使用二路快排就可以进行优化，阻止效率的降低。
二路快排解决的问题：
不会让等于基准值的元素全部都集中在数组的一边。
2. 思想
-
我们将小于基准值的元素全部放在数组的左边，大于基准值的元素放在数组的右边
-
对于左边有着一个索引left，右边有着一个索引right
-
当left小于基准值的时候一直向后++，直到碰到某个大于等于基准值的left；right大于基准值的时候一直向前--，直到碰到某个小于等于基准值的right
-
此时交换left和right处的数据元素，然后left++，right--
-
继续执行第2不，直到left==right停止
-
此时，交换基准值和left位置的元素，返回基准值即可
这种思想，即使是重复的数据元素很多，也可以将其几乎平分开来，不会造成一边数据量极大，另一边没有数据
3. 适合的场景
当数组中重复的元素过多的时候，就不能在用快排，使用二路快排即可
4. 实现
实现的时候，只需要改变，partion函数即可
int Partion_Two(int array[], int left, int right)
{
int l = left;
int r = right - 1;
while (1)
{
while (l <= r && array[l] < array[right])
{
l++;
}
while (l <= r && array[r] > array[right])
{
r--;
}
if (l > r)
{
break;
}
std::swap(array[r], array[l]);
}
std::swap(array[l], array[right]);
return r;
}
注意：左边找不小于的，右边找不大于的，然后进行判断交换
3. 三路快排
1. 思想
将数组分成三部分，小于基准值，大于基准值以及等于基准值的
记录下三个下标：
lt：小于基准值的最后一个下标
gt：大于基准值的第一个下标
index：正在遍历的下标
index小于基准值：交换index和lt+1，lt++
index大于基准值：交换index和gt-1，gt--
index等于基准值：index++
结束条件：index==gt
最后一步交换基准值：
swap(arr[lt], arr[right])
继续进行的区间：
[left,lt-1]
[gt, right]
2. 实现
void QuickSort_Three(int array[], int left, int right)
{
if (array == nullptr)
{
return;
}
if (right <= left)
{
return;
}
int lt = left - 1;
int gt = right;
int index = left;
int key = array[right];
while (index < gt)
{
if (array[index] < key)
{
std::swap(array[index], array[lt + 1]);
lt++;
index++;
}
else if (array[index] > key)
{
std::swap(array[index], array[gt - 1]);
gt--;
}
else
{
index++;
}
}
std::swap(array[index], array[right]);
QuickSort_Three(array, left, lt );
QuickSort_Three(array, gt, right);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
