快速排序

快速排序（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

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