特性

快速排序特点

  • 非稳定排序
  • 分治模式:那么就存在拆分和组合

快速排序步骤

  • 分治思想,那么源数组每层递归逻辑为:一分为二、对子问题同样方式处理
  • 选取枢纽元素(枢纽元素的选取决定有多种快速排序的实现方式)
  • 找到枢纽元素在数组中的位置(此处找位置的方法可以多种)
  • 对枢纽元素左边,右边做类似处理
  • 递归退出,数据已排好序

代码演示:

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
/**
* 快速排序, 举例为升序
*
* @param a
* @param m
* @param n
*/
public static void quickSort(int[] a, int m, int n) {
if (m < n) {
int i = m;
int j = n;
int pivot = a[m]; // 枢纽元素为当前层级的数据第一个元素
while (i < j) {
while (i < j && a[j] > pivot) { // 找到右边第一个小于等于(取决升序还是降序)pivot的位置j,或者i=j
j--;
}
while (i < j && a[i] <= pivot) {// 找到左边第一个大于pivot的位置j,或者i=j。此处=由于选取的m作为枢纽,从m之后开始处理
i++;
}
if (i < j) { // i<j 交换ij位置的值,继续按此方法循环找ij位置
swap(a, i, j);
}else if(i==j){ // i=j找到了pivot的位置, 此位置的元素不会大于pivot
swap(a, m, i);
}
} // 以上定位到枢纽元素pivot的索引位置i。找到后固定改位置,对i左边和右边的同样方法处理
quickSort(a, m, i - 1);
quickSort(a, i + 1, n);
}
}
/**
* 交换函数
*
* @param a
* @param i
* @param j
*/
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

代码文件:C7QuickSort.java

总结

  • 初始条件
  • 选取枢纽元素,找到枢纽元素安置的位置
  • 对枢纽元素的前面部分,后面部分分别进行快速排序

版权声明:本文为博主原创文章,未经允许不得转载。