-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathQuickSortAll.java
More file actions
129 lines (121 loc) · 3.16 KB
/
Copy pathQuickSortAll.java
File metadata and controls
129 lines (121 loc) · 3.16 KB
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package sort;
public class QuickSortAll {
/*
* 快排，递归，选择第一个元素当做指针
*/
public static void quickSort0(int[] nums, int l, int r){
int i=l, j=r;
int x = nums[i];
while(i<j){
while(i<j && x<nums[j]) j--;
nums[i] = nums[j];
while(i<j && nums[i]<=x) i++;
nums[j] = nums[i];
}
nums[i] = x;
if(l<i) quickSort0(nums,l,i-1);
if(i<r) quickSort0(nums,i+1,r);
}
/*
* 快排，递归，选择中间的元素当做指针 面试版~~~~
*/
public static void quickSort1(int[] nums, int l, int r){
int i=l, j=r; //左右指针
int x = nums[(i+j)>>1]; //选择监督哨
while(i<=j){
while(nums[i] < x) i++;
while(x < nums[j]) j--;
if(i<=j){
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
i++;
j--;
}
}
if(l<j) quickSort1(nums,l,j);
if(i<r) quickSort1(nums,i,r);
}
/*
* 快速选择：选择首元素作为监督哨
*/
public static int findKthLargest(int[] nums, int k) {
k--;
int l=0, r=nums.length-1;
while(l<r){
int x = l, y = r;
int key = nums[x];
while(x<y){
while(x < y && key > nums[y]) y--;
nums[x] = nums[y];
while(x < y && nums[x] >= key) x++;
nums[y] = nums[x];
}
nums[x] = key;
if(x == k)
return nums[k];
else if(x > k)
r = x - 1;
else
l = x + 1;
}
return nums[k];
}
/*
* 快速选择： 选择中间元素作为监督哨
*/
public static int findKthLargest1(int[] nums, int k){
k--;
int l=0, r= nums.length - 1;
while(l<r){
int i=l, j= r;
int x = nums[(i+j)>>1];
while(i<j){
while(nums[i]>x) i++;
while(x>nums[j]) j--;
if(i<=j){
int t=nums[i]; nums[i] = nums[j]; nums[j] = t;
i++;
j--;
}
}
if((l<j)&&(k<=j)) r = j;
else if((i<r)&&(i<=k)) l = i;
else return nums[k];
}
return nums[k];
}
/*
* 快速选择：递归版快速选择 面试版~~~~
*/
public static int findKthLargest2(int[] nums, int k){
return findKthLargest20(nums, k-1, 0, nums.length-1);
}
private static int findKthLargest20(int[] nums, int k, int l, int r){
int i=l, j=r;
int x=nums[(i+j)>>1];
while(i<=j){
while(nums[i]>x) i++;
while(x>nums[j]) j--;
if(i<=j){
int t = nums[i]; nums[i]=nums[j]; nums[j]=t;
i++;
j--;
}
}
if((l<j)&&(k<=j)) return findKthLargest20(nums,k,l,j);
else if ((i<r)&&(i<=k)) return findKthLargest20(nums,k,i,r);
else return nums[k];
}
public static void main(String[] args) {
int[] nums = new int[]{6,8,3,6,2,6,4,5,3,2,1,7,3,6};
quickSort0(nums,0,13);
for(int i:nums){
System.out.print(i+"_");
}
System.out.println();
nums = new int[]{2,1};
quickSort1(nums,0,1);
for(int i:nums){
System.out.print(i+"_");
}
}
}