快速排序是对冒泡排序的一种改进,快速思想是使用分治法,其中有一个基准值,把一个数组中的数分为较基准值大和较基准值小的两部分(子数组),所有比基准值大的放在基准值后面,所有比基准值小的放在基准值前面,然后递归再次切分,直至子数组的大小为1或0,此时全局有序。

图示:

7789414-007520d3d4a7610c

快速排序是不稳定的排序,在排序后,相同值的先后顺序可能会变化,所以是不稳定的。

所谓是稳定性是指:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

代码实现:

Java版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int low = left;
int high = right;
int pivot = arr[left];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
quickSort(arr, left, low - 1);
quickSort(arr, low + 1, right);
}
}

Scala版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quickSort(arr: Array[Int], left: Int, right: Int): Unit = {
if (left < right) {
var low = left
var high = right
val pivot = arr(low)
while (low < high) {
while (low < high && arr(high) >= pivot) high -= 1
arr(low) = arr(high)
while (low < high && arr(low) <= pivot) low += 1
arr(high) = arr(low)
}
arr(low) = pivot
quickSort(arr, low + 1, right)
quickSort(arr, left, low - 1)
}
}

在网上看了不少人的快速排序代码,其整体思想都是一样的,分治,递归。但是具体实现细节上则各不相同,八仙过海,大显神通。上面代码是我觉得比较好简洁,且理解相对容易的一种写法。另外Scala版本有一个十分精简的写法:

1
2
3
4
5
6
7
def quickSort(list: List[Int]): List[Int] = list match {
case Nil => Nil
case List() => List()
case head :: tail =>
val (left, right) = tail.partition(_ < head)
quickSort(left) ::: head :: quickSort(right)
}

Scala这么优雅的语言,真的让人赏心悦目。