几乎所有的编程语言都会提供排序函数,比如 C 语言的 qsort(), C++ STL 中的 sort(),这些排序函数是如何实现的呢?
如果要实现一个通用的高效率的排序函数,我们应该选择那种排序算法呢?
各种排序算法的特点如下所示。
线性排序算法的时间复杂度比较低,适用场景特殊,因此不适合作为通用的排序函数。
小规模数据可以选择时间复杂度为 \(O(n^2)\) 的算法,大规模数据选择时间复杂度为 \(O(nlogn)\) 的算法则会更加高效。为了兼顾任意规模的数据,一般会首选复杂度为 \(O(nlogn)\) 的算法来实现排序函数。
快速排序最坏情况下时间复杂度退化为 \(O(n^2)\) ,我们怎样来避免这种情况的发生呢?
实际上,这种 \(O(n^2)\) 复杂度出现的主要原因还是分区点选取得不合理。
理想的分区点应该是,被分区点分开的两个区间,数据的数量差不多。
三数取中法。从待排序数据首、尾、中分别取出一个数,然后对比大小,以这三个数的中间值作为分区点。
如果排序数据比较多,可能要“五数取中”或者“十数取中”。
随机法。每次从要排序的区间随机选择一个元素作为分区点,这种情况下,就可以避免每次分区点都选得非常糟糕。
快速排序是利用递归来实现的,当递归的的深度过深时,就会导致堆栈溢出。
qsort 优先使用归并排序,在数据规模比较小的时候,以空间换时间。
当数据规模比较大时,qsort 会改为快速排序,以三数取中法来选取分区点。
qsort 通过在堆上模拟函数调用栈来解决堆栈溢出问题。
当快速排序区间内元素小于等于 4 时,qsort 退化为插入排序。因为在小数据规模下, \(O(n^2)\) 时间复杂度算法并不一定比 \(O(nlogn)\) 的算法执行时间长。
int Partition(float data[], int left, int right)
{
int i = left, j = left;
int pivot = data[right];
for (j = left; j < right; j++)
{
if (data[j] < pivot)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
}
}
data[j] = data[i];
data[i] = pivot;
return i;
}
void Quick_Sort(float data[], int left, int right)
{
if (left < right)
{
stack<int> s;
s.push(left);
s.push(right);
while (!s.empty())
{
int j = s.top();
s.pop();
int i = s.top();
s.pop();
int mid = Partition(data, i, j);
// 至少有两个元素
if (mid-1 > i)
{
s.push(i);
s.push(mid-1);
}
if (j > mid+1)
{
s.push(mid+1);
s.push(j);
}
}
}
}
针对有重复数据的情况,三路划分将数据分为三部分:小于主元的、等于主元的和大于主元的,然后递归调用的时候只对两端的数据再排序,而不用处理中间相等的情况。
void Quick_Sort_3_Way(float data[], int left, int right)
{
if (left < right)
{
float pivot = data[right];
int l = left - 1;
int j = left;
int r = right;
/*
[left, l] 小于主元
[l+1, j] 等于主元
[j+1, right] 大于主元
*/
while (j < r)
{
if (data[j] < pivot)
{
swap(data[j], data[++l]);
j++;
}
else if (data[j] > pivot)
swap(data[j], data[--r]);
else j++;
}
swap(data[j], data[right]);
Quick_Sort_3_Way(data, left, l);
Quick_Sort_3_Way(data, j+1, right);
}
}
获取更多精彩,请关注「seniusen」!
原文:https://www.cnblogs.com/seniusen/p/11979848.html