快速排序(QuickSort)是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
设要排序的数组是 A[0] …… A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
上面这种算法的描述理解起来有点绕(通过Java代码做了示例),但是这种算法通过交换的方式节省了空间。在现在内存空间比较大的情况下,可以考虑下面这种算法(通过Python代码做了示例):
class QuickSort {
public static int[] qsort(int arr[], int start, int end){
int refNumber = arr[start];
int i = start;
int j = end;
while( i < j ){
while( (i < j) && (arr[j] > refNumber) ){
j--;
}
while( (i < j) && (arr[i] < refNumber) ){
i++;
}
if( (arr[i] == arr[j]) && (i < j)){
i++;
}else{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if( i - 1 > start) arr = qsort(arr, start, i - 1);
if( j + 1 < end ) arr = qsort(arr, j + 1 ,end);
return arr;
}
public static void main(String[] args){
int arr[] = new int[]{ 5, 10, 2, 15, 21, 99, 3, 1, 17, 23, 1, 35};
int len = arr.length - 1;
arr = qsort(arr, 0, len);
for(int i:arr){
System.out.print(i + "\t");
}
}
}
这个算法使用的数组支持不定长,对于其他语言来说不一定适用。
# -*- coding: utf-8 -*-
def quick_sort(data):
if len(data) >= 2: # 递归入口及出口
mid = data[0] # 选取基准值,也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
data.remove(mid) # 从原始数组中移除基准值
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
快速排序(Quicksort)有几个值得一提的变种算法,这里进行一些简要介绍: