快速排序

递归实现

快速排序方式1

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
/**
* 快速排序入口。
* @param array 待排序的数组
*/
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}

/**
* 对数组中从left到right的区域进行快速排序
* @param array 待排序的数组
* @param left 本次待排序序列的起始位置
* @param right 本次待排序序列的结束位置
*/
private static void quickSort(int[] array, int left, int right) {
if (left < right) {
int index = quickSortOne(array, left, right);
quickSort(array, left, index - 1);
quickSort(array, index + 1, right);
}
}

/**
* 进行一趟快速排序
* @param array 待排序的数组
* @param left 待排序的序列的起始位置
* @param right 待排序序列的结束位置
* @return 分割的位置
*/
private static int quickSortOne(int[] array, int left, int right) {
int pivot = array[left];
int start = left;
int end = right;
while (start < end) {
// 从右向左查找查找第一个比基准数小的元素
// 如果a[j]大于等于基准数,继续查找
while (array[end] >= pivot && start < end) {
end--;
}
// 从左向右查找第一个比基准数大的元素
// 也就是当a[i]小于等于基准数的时候,还得继续查找
while (array[start] <= pivot && start < end) {
start++;
}
// 交换大于基准数的元素和小于基准数的元素的位置
swap(array, start, end);
}
// 把基准数放到中间
swap(array, left, start);
// 返回分割点的下标
return start;
}

/**
* 交换数字中的两个元素的位置
* @param array 数组
* @param left 数字前面的元素
* @param right 数组后面的元素
*/
private static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}

快速排序改进型:省略swap函数的情况

上面的算法为:

  • 使用一个变量,记录下基准数的值,从后向前查找比基准数小的数,
  • 然后从前向后查找大的数,
  • 然后把比基准数小的和比基准数大的进行交换。这样需要使用一个交换方法来实现。

那么这个方法能不能省略掉呢?
是可以的,

  • 使用一个变量,记录下基准数的值,从后向前查找比基准数小的数,
  • 找到以后直接把这个小的数,放到原来基准数的位置上。(因为我们已经记下了基准数的位置,所以不用担心这个数被覆盖掉)
  • 然后从前往后查找比基准数大的数,然后把这个数放到上一步找到的比基准数小的数的位置上。
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
/**
* 对整个数组执行快速排序。
* @param array 待排序的数组
*/
public static void quickSort(int array[]) {
// 合法性判断
if (array == null)
return;
// 对从第一个元素到最后一个元素的数组序列执行快速排序
quickSort(array, 0, array.length - 1);
}

/**
* 对数组中的一段连续的序列执行快速排序。
* @param array 待排序的数组
* @param left 数组中被分割的序列的开始位置
* @param right 数组中被分割的序列的结束位置
*/
private static void quickSort(int array[], int left, int right) {
// 执行一趟快速排序,并返回分割点
int mid = quickOne(array, left, right);
if (left < mid - 1) {
// 对分割点左侧的序列执行快速排序
quickSort(array, left, mid - 1);
}
if (mid + 1 < right) {
// 对分割点右侧的序列执行快速排序
quickSort(array, mid + 1, right);
}
}

/**
* 执行一趟快速排序
* @param array 待排序的数组
* @param left 被分割的序列的开始位置
* @param right 被分割的序列的结束位置
* @return 当前序列的分割点的位置
*/
private static int quickOne(int[] array, int left, int right) {
// 保存基准数
int pivot = array[left];
while (left < right) {
// 从右向左移动右指针,查找比基准数小的数
while (left < right && array[right] >= pivot) {
right--;
}
// 把比基准数小的放到基准数的位置
array[left] = array[right];
// 从左向右移动左指针,查找比基准数大的数
while (left < right && array[left] <= pivot) {
left++;
}
// 把基准数大的数放到后面
array[right] = array[left];
}
// 基准数放到分割点的位置
array[left] = pivot;
// 返回分割点的下标
return left;
}