快速排序及优化

普通快速排序

原理:

分治法 将快速排序的分为三步:

  • 在数据集之中,选择一个元素作为”基准”(pivot)
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

quick_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QuickSort {

public static void main(String[] args) {
Integer[] array = {6, 7, 9, 3, 6, 8, 1, 9, 3};
sort(array);
for (int i : array) {
System.out.println(i);
}
}

public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}

public static <T extends Comparable<? super T>> void sort(T[] array, int left, int right) {
if (left > right) {
return;
}
int storeIndex = partition(array, left, right);
sort(array, left, storeIndex - 1);
sort(array, storeIndex + 1, right);
}

private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
T base = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (base.compareTo(arr[i]) > 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, left, j);
//返回一躺排序后基准值的下角标
return j;
}

public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

传送门: golang写法

优化:随机选取基准值

在数组几乎有序时,快排性能不好(因为每趟排序后,左右两个子递归规模相差悬殊,大的那部分最后很可能会达到O(n^2))。

解决:基准值随机地选取,而不是每次都取第一个数。这样就不会受“几乎有序的数组”的干扰了。

但是对“几乎乱序的数组”的排序性能可能会稍微下降,至少多了排序前交换的那部分,乱序时这个交换没有意义…有很多“运气”成分。

1
2
3
//排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
//就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
swap(arr,left,(int)(Math.random()*(right - left + 1)+left));

继续优化:配合着使用插入排序

快排是不断减小问题规模来解决子问题的,需要不断递归。但是递归到规模足够小时,如果继续采用这种 不稳定+递归 的方式执行下去,效率不见得会很好。

所以当问题规模较小时,近乎有序时,插入排序表现的很好。Java自带的Arrays.sort()里经常能看到这样的注释:“Use insertion sort on tiny arrays”,“Insertion sort on smallest arrays”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @param arr 待排序的数组
* @param left 左闭
* @param right 右闭
* @param k 当快排递归到子问题的规模 <= k 时,采用插入排序优化
* @param <T> 泛型,待排序可比较类型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
// 规模小时采用插入排序
if (right - left <= k) {
insertionSort(arr, left, right);
return;
}
int p = partition(arr, left, right);
sort(arr, left, p - 1, k);
sort(arr, p + 1, right, k);
}

public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
T cur = arr[i];
int j = i - 1;
for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = cur;
}
}

继续优化:两路快排

在最开始的普通快速排序说过,让基准值base左边的都比base小,而base右边的都大于等于base。等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。

这样在数组中重复数字很多的时候,就又会导致两边子递归规模差距悬殊的情况。这时想把等于base的那些数分派到base两边,而不是让他们聚集到一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
//排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
//就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));

T base = arr[left];//基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序

int i = left + 1; //对于上一行提到的[left+1.....right]区间,i表示 [left+1......i)左闭右开区间的值都小于等于base。

int j = right;//对于上二行提到的[left+1.....right]区间,j表示 (j......right]左开右闭区间的值都大于等于base。

while (true) {
//从左到右扫描,扫描出第一个比base大的元素,然后i停在那里。
while (i <= right && arr[i].compareTo(base) < 0) i++;

//从右到左扫描,扫描出第一个比base小的元素,然后j停在那里。
while (j >= left && arr[j].compareTo(base) > 0) j--;

if (i > j) {//虽说是i>j,但其实都是以j=i-1为条件结束的
break;
}
swap(arr, i++, j--);
}

swap(arr, left, j);
return j;//返回一躺排序后,基准值的下角标
}

继续优化:两路快排 不用swap, 用直接赋值

上面的两路在找到大于base的值和小于base的值时,用的是swap()方法来进行交换。两数交换涉及到第三个变量temp的操作,多了读写操作。

接下来用直接赋值的方法,把小于的放到右边,大于的放到左边,当i和j相遇时,那个位置就是base该放的地方。至此一趟完成。递归即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
//排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
//就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));

T base = arr[left];//基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序

int i = left; //对于上一行提到的[left+1.....right]区间,i表示 [left+1......i)左闭右开区间的值都小于等于base。

int j = right;//对于上二行提到的[left+1.....right]区间,j表示 (j......right]左开右闭区间的值都大于等于base。

while (i < j) {
//从右到左扫描,扫描出第一个比base小的元素,然后j停在那里。
while (j > i && arr[j].compareTo(base) > 0) j--;

arr[i] = arr[j];

//从左到右扫描,扫描出第一个比base大的元素,然后i停在那里。
while (i < j && arr[i].compareTo(base) < 0) i++;

arr[j] = arr[i];

}

arr[j] = base;
return j;//返回一躺排序后,基准值的下角标
}

继续优化:当大量数据,且重复数多时,用三路快排

把数组分为三路,第一路都比base小,第二路都等于base,第三路都大于base。

用指针从前到后扫描,如果:

1.cur指向的数小于base,那么:交换arr[cur]和arr[i]的值,然后i++,cur++。

2.cur指向的数等于base, 那么:cur++

3.cur指向的数大于base,那么:交换arr[cur]和arr[j]的值,然后j–

当cur > j的时候说明三路都已经完成
quick_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 /**
* @param arr 待排序的数组
* @param left 待排序数组的左边界
* @param right 待排序数组的右边界
* @param <T> 泛型
* @return
*/
private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {
//排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
//就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));

T base = arr[left];//基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序

//三路快排分为下面这三个路(区间)
int i = left; // left表示,[lleft...left) 左闭右开区间里的数都比base小
int j = right;// left表示,(rright...right] 左开右闭区间里的数都比base大
int cur = i;//用cur来遍历数组。[left...cur)左闭右开区间里的数都等于base

while (cur <= j) {
if (arr[cur].compareTo(base) == 0) {
cur++;
} else if (arr[cur].compareTo(base) < 0) {
swap(arr, cur++, i++);
} else {
swap(arr, cur, j--);
}
}
return new int[]{i - 1, j + 1};//[i...j]都等于base,子问题就只需要解决i左边和j右边就行了
}
分享到: