快速排序是对冒泡排序的一种改进，快速思想是使用分治法，其中有一个基准值，把一个数组中的数分为较基准值大和较基准值小的两部分（子数组），所有比基准值大的放在基准值后面，所有比基准值小的放在基准值前面，然后递归再次切分，直至子数组的大小为1或0，此时全局有序。
图示：
快速排序是不稳定的排序，在排序后，相同值的先后顺序可能会变化，所以是不稳定的。
所谓是稳定性是指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，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这么优雅的语言，真的让人赏心悦目。