概念
快速排序(英语:Quick Sort),又称分区交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要 O(nlog n)(大O符号)次比较。在最坏状况下则需要 O(n^2 ) 次比较,但这种状况并不常见。事实上,快速排序(nlogn)通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。
解题思路
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采
用了分治法来解决问题。
运行过程
-
1、从序列中挑出一个元素,称为“基准”(pivot)。一般是选取序列的第一个元素。
(假设每次选择0位置的元素为轴点元素) -
2、重新排序数列,
-
所有比基准值小的元素摆放在基准前面
-
所有比基准值大的元素摆在基准的后面(相同的数可以到任一边)。
-
在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
-
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
-
4、直到序列的大小是0或1,也就是所有元素都已经被排序好了,递归结束。
代码
Java
public class QuickSort {
public int[] array;
public void sort() {
sort(0,array.length);
}
private void sort(int begin ,int end){
if (end - begin < 2) return ;
int mid = pivotIndex(begin,end);
sort(begin,mid);
sort(mid + 1,end);
}
private int pivotIndex(int begin, int end){
// 随机选择一个元素跟begin位置进行交换
swap(begin,begin + (int) (Math.random() * (end - begin)));
// 备份begin位置的元素
int pivot = array[begin];
// end指向最后一个元素
end--;
while (begin < end){
while (begin < end){
if (pivot < array[end]){ // 右边元素 > 轴点元素
end--;
}else { // 右边元素 <= 轴点元素
array[begin++] = array[end];
break;
}
}
while (begin < end){
if (pivot > array[end]){ // 左边元素 < 轴点元素
begin++;
}else { // 左边元素 >= 轴点元素
array[end --] = array[begin];
break;
}
}
}
array[begin] = pivot;
return begin;
}
protected void swap(int i1, int i2) {
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
}
性能
-
在轴点左右元素数量比较均匀的情况下,同时也是最好的情况
OT(n)= 2* T(n/2) + 0(n) = 0(nlogn)
-
如果轴点左右元素数量极度不均匀,最坏情况
0 T(n)= T(n- 1)+ 0(n)= 0(n2) -
为了降低最坏情况的出现概率,一般采取的做法是
随机选择轴点元素 -
最好、平均时间复杂度: 0(nlogn)
-
最坏时间复杂度: 0(n2)
-
由于递归调用的缘故,空间复杂度: 0(logn)
-
属于不稳定排序
参考文章:
经典排序算法(2)——快速排序算法详解
《恋上数据结构与算法第二季》
网友评论