Algorithm Quick Sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

前言

    快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序

快速排序思想:

1)先从数列中取出一个数作为基准数;
2)分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;
3)再对左右区间重复第二步,直到各区间只有一个数。

快速排序解析:


快速排序动图:


快速排序代码:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* @Auther: Arsenal
* @Date: 2020-03-22 9:44
* @Description: 快速排序
*/
public class QuickSort {
public static void main(String[] args) {

// int[] arr = {-9, 78, 0, 23, -567, 70};
// System.out.println("原始的数组:" + Arrays.toString(arr));
// quickSort(arr, 0, arr.length - 1);
// System.out.println("排序后数组:" + Arrays.toString(arr));

int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1); // 8000000数据 1166 毫秒。比希尔排序快
long end = System.currentTimeMillis();
System.out.println("8000000个数字排序所用时间:" + (end - start));
}

/**
* 快速排序
* @param arr 需排序数组
* @param left 左下标
* @param right 右下标
*/
public static void quickSort(int[] arr, int left, int right) {

int l = left; //左下标
int r = right; // 右下标
int pivot = arr[(left + right) / 2]; //中轴的值
int temp = 0;
//让比pivot中轴值小的放在左边
while (l < r) {

//在pivot左边一直找,找到比pivot值大的才退出
while (arr[l] < pivot) {
l++;
}

//在pivot右边一直找,找到比pivot值小的才退出
while (arr[r] > pivot) {
r--;
}

//当左边的下标大于等于右边的下标时,说明pivot左边的值都是小于pivot; pivot右边的值都是大于pivot
if (l >= r) {
break; //退出
}

//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;

//如果交换完后,发现arr[l] == pivot,那左边就排序完了,让右边继续排序,即r--;
if (arr[l] == pivot) {
r--;
}

//如果交换完后,发现arr[r] == pivot,那右边就排序完了,让左边继续排序,即l++;
if (arr[r] == pivot) {
l++;
}
}

//如果l==r,必须执行 l++,r--。否则出现栈溢出。
if (l == r) {
l++;
r--;
}

//向左递归
if (left < r) {
quickSort(arr, left, r);
}

//向右递归
if (right > l) {
quickSort(arr, l, right);
}
}
}

延伸

    快速排序
    快速排序算法
    图解 快速排序
    韩顺平数据结构和算法
    Data Structure and Algorithms - Quick Sort

Content
  1. 1. 前言
  2. 2. 快速排序
  3. 3. 延伸