介绍
快速排序,又称划分交换排序,简称快排,这种排序算法,最早由东尼·霍尔提出。
演示
Sorting_quicksort复杂度
最坏时间复杂度:O(n^2)
最优时间复杂度:O(nlog n)
平均时间复杂度:O(nlog n)
最坏空间复杂度:根据实现的方式不同而不同
步骤
快速排序使用分治法策略来把一个序列分为两个子序列。
步骤为:
- 从数列中挑出一个元素,称为基准,
- 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割操作。
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。
python
def quick_sort(li):
if len(li) <= 1:
return li
else:
pivot = li[0]
less = quick_sort([i for i in li[1:] if i < pivot])
more = quick_sort([i for i in li[1:] if i >= pivot])
return less + [pivot] + more
print(quick_sort(li))
java
public static void quickSort(List<Integer> items) {
if(items.size() > 1) {
List<Integer> smaller = new ArrayList<>();
List<Integer> same = new ArrayList<>();
List<Integer> larger = new ArrayList<>();
Integer chosenItem = items.get(items.size() / 2);
for(Integer i: items) {
if(i < chosenItem)
smaller.add(i);
else if(i > chosenItem)
larger.add(i);
else
same.add(i);
}
quickSort(smaller);
quickSort(larger);
items.clear();
items.addAll(smaller);
items.addAll(same);
items.addAll(larger);
}
}
网友评论