快速排序
快速排序是一种不稳定的排序算法，平均时间复杂度为O(n*logn)。快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-list).步骤为:
- 从数列中挑出一个元素，称为"基准" (pivot)。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束后，该基准处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursive)把小于基准值元素的子数列和大于基准值的子数列排序。
** 快速排序的时间主要花在划分上，所以 **
- 最坏情况：时间复杂度为O(n^2)。因为最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1 元素的时候。
- 最后情况：每次划分选取的基准都是当前无序区的中值。如果每次划分过程产生的区间大小都是n/2，则快速排序运行就快得多。
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
}
a[first] = key;
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
快速排序的优化
- 当待排序序列的长度分割到一定大小后，使用插入排序。
- 快速排序函数尾部有两次递归操作，我们可以对其使用尾递归优化。优化后，可以缩减堆栈深度，同原来的O(n) 缩减为O(logn),将会提高性能。
- 从左，中，右三个数中取中间值。
