快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。

基本思想

1.先从数列中取出一个数作为基准数。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。

思路

快速排序的进一步说明:挖坑填数+分治法

以一个数组作为示例,取区间第一个数为基准数。(基准数可以为数组内的任意元素,一般取首、尾或中间的元素)

0 1 2 3 4 5 6 7 8 9
72 6 57 88 60 42 83 73 48 85

初始时,i = 0; j = 9; temp = arr[i] = 72

由于已经将arr[0]中的数保存到temp这个临时变量中,可以理解成在数组arr[0]上挖了个坑,可以将其它数据填充到这来。

从 j 开始向前找一个比temp小或等于temp的数。当 j =8 时,符合条件,将arr[8]挖出再填到上一个坑arr[0]中。arr[0]=arr[8]; 这样一个坑arr[0]就被搞定了,但又形成了一个新坑arr[8],这怎么办呢?简单,再找数字来填arr[8]这个坑。这次从 i 开始向后找一个大于temp的数,当 i=3 时,符合条件,将arr[3]挖出再填到上一个坑中。arr[8]=arr[3];


数组变为:

0 1 2 3 4 5 6 7 8 9
48 6 57 88 60 42 83 73 88 85

i = 3; j = 8; temp=72

再重复上面的步骤,先从后向前找,再从前向后找

从 j 开始向前找,当 j=5 时,符合条件,将arr[5]挖出填到上一个坑中,arr[3] = arr[5];

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将temp填入arr[5]。


数组变为:

0 1 2 3 4 5 6 7 8 9
48 6 57 42 60 72 83 73 88 85

可以看出arr[5]前面的数字都小于它,arr[5]后面的数字都大于它。因此再对arr[0…4]和arr[6…9]这二个子区间重复上述步骤就可以了。

总结

1.i =L; j = R; 将基准数挖出形成第一个坑arr[i]。

2.j–由后向前找比它小的数,找到后挖出此数填前一个坑arr[i]中。

3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑arr[j]中。

4.再重复执行2,3二步,直到i==j,将基准数填入arr[i]中。

代码

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
package com.nanzx.sort;

import java.util.Arrays;

public class QuickSort {

public static void main(String[] args) {
int[] arr = { -9, 78, 0, 23, -567, 70 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}

public static void quickSort(int arr[], int l, int r) {
if (l < r) {
// 用于遍历
int i = l;
int j = r;
// 临时变量用于存储
int temp = arr[i];

while (i < j) {
while (i < j && arr[j] > temp) {// 从右向左找第一个小于等于temp的数
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= temp) { // 从左向右找第一个大于temp的数
i++;
}
arr[j] = arr[i];
}

arr[i] = temp;
quickSort(arr, l, i - 1); // 递归调用
quickSort(arr, i + 1, r);
}
}
}

测试快速插入排序的速度

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
46
47
48
49
package com.nanzx.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class QuickSort {

public static void main(String[] args) {
// 创建一个8000000个的随机的数组 八百万
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}

Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);

quickSort(arr, 0, arr.length - 1);

Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间是=" + date2Str);
}

public static void quickSort(int arr[], int l, int r) {
if (l < r) {
// 用于遍历
int i = l;
int j = r;
// 临时变量用于存储
int temp = arr[i];
while (i < j) {
while (i < j && arr[j] > temp) {// 从右向左找第一个小于temp的数
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= temp) { // 从左向右找第一个大于等于temp的数
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
quickSort(arr, l, i - 1); // 递归调用
quickSort(arr, i + 1, r);
}
}
}

排序前的时间是=2020-08-03 00:13:30 排序后的时间是=2020-08-03 00:13:32

可以看出快速排序比希尔排序还要快些。


原文作者: MoreWindows

原文链接: http://blog.csdn.net/morewindows/article/details/6684558

韩顺平老师的视频里快速排序讲得有些晦涩,很感谢这位博主的文章,通俗易懂。