快速排序三种实现方式
大家都知道快速排序一次后左边比标兵小，右边比标兵大。但是要注意市面上现在主要有两种快速排序：一种是标兵不动版（只在每趟最后做一次交换），一种是标兵移动版。两种效率都一样，原因在于最初的论文和《算法》书中的不一样。
一般做选择题来说都采用标兵移动版，且默认标兵选每部分最左边的第一个。
标兵移动版：从右往左找到第一个比标兵小的值并交换，从左往右找到第一个比标兵大的值并交换。
标兵不动版：将[1 : n]分为左边小[1 : mid]，右边大[mid + 1 : n]，这趟后再将标兵0和mid交换。
两种都能达到最终目的：排序一次后左边比标兵小，右边比标兵大
标兵移动版（推荐）
一般选择题都默认这种最初版本，我推荐这种做法。做了优化，无需每次都换来换去，只需要换该换的元素，最后换掉标兵即可。例如：标兵从0换到了5，又从5换到了3，又从3换到了4，那么先用一个temp暂存标兵的值，直接n[0]=n[5], n[5]=n[3],n[3]=n[4],最后n[4]=temp即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public void quickSort(int[] nums, int l, int r){
if (nums == null || nums.length <= 1 || l >= r) return;
int left = l, right = r;
int temp = nums[left];
while (left < right) {
while (temp <= nums[right] && left < right) right--;
if (left < right) {
nums[left] = nums[right];
left++;
}
while (temp >= nums[left] && left < right) left++;
if (left < right) {
nums[right] = nums[left];
right--;
}
}
nums[left] = temp;
quickSort(nums, l, left);
quickSort(nums, left + 1, r);
}
|
标兵不动版
参考柳神代码，改成了左边为标兵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int[] quickSort(int[] nums, int l, int r) {
int mid = r;
for (int i = r; i >= l; i--) {
if (nums[i] > nums[l]) {
nums[i] = swap(nums[mid], nums[mid] = nums[i]);
mid--;
}
}
nums[l] = swap(nums[mid], nums[mid] = nums[l]);
if (mid > l + 1) quickSort(nums, l, mid - 1);
if (mid < r - 1) quickSort(nums, mid + 1, r);
return nums;
}
public static int swap(int a, int b){
return a;
}
|
BFS版本，可以获取第n次的排序结果
相比于DFS更简单的实现，BFS更加符合手写顺序
在标兵移动版的基础上改进，不用递归（dfs），而是使用队列（bfs）
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
| public void quickSort(int[] nums){
Queue<int[]> queue = new LinkedList<>();
int[] idx = {0, nums.length - 1};
queue.offer(idx);
while (!queue.isEmpty()){
idx = queue.poll();
if (idx[0] > idx[1]) continue;
int left = idx[0], right = idx[1], temp = nums[left];
while (left < right){
while (left < right && temp <= nums[right]) right--;
if (left < right){
nums[left] = nums[right];
left++;
}
while (left < right && temp >= nums[left]) left++;
if (left < right){
nums[right] = nums[left];
right--;
}
}
nums[left] = temp;
int[] idxL = {idx[0], left - 1};
queue.offer(idxL);
int[] idxR = {left + 1, idx[1]};
queue.offer(idxR);
}
}
|
我想在博客里高冷一点，细节不多说了，这几种自己调调看吧，断点打在哨兵交换前就可以很清楚的看出3种方法的区别了
2020.10.29场中信信用卡附加题
求第n趟快排结果
完整代码如下
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
| public class zhongxin_004_快速排序第n趟结果 {
@Test
public void test(){
int[] array = {42,35,63,96,56,11,17,42,88};
int[] res = nthResultOfQuickSort(array, 4);
System.out.println(Arrays.toString(res));
}
private int sum = 1;
public int[] nthResultOfQuickSort (int[] array, int n) {
for (int i = 1; i < n; i++) {
sum += 2 * i;
}
quickSort(array);
return array;
}
public void quickSort(int[] nums){
Queue<int[]> queue = new LinkedList<>();
int[] idx = {0, nums.length - 1};
queue.offer(idx);
while (!queue.isEmpty()){
idx = queue.poll();
if (idx[0] > idx[1]) continue;
int left = idx[0], right = idx[1], temp = nums[left];
while (left < right){
while (left < right && temp <= nums[right]) right--;
if (left < right){
nums[left] = nums[right];
left++;
}
while (left < right && temp >= nums[left]) left++;
if (left < right){
nums[right] = nums[left];
right--;
}
}
nums[left] = temp;
if (--sum == 0) return;
int[] idxL = {idx[0], left - 1};
queue.offer(idxL);
int[] idxR = {left + 1, idx[1]};
queue.offer(idxR);
}
}
}
|
其他排序的题目点击这里