简单快速排序 Java版

Ⅰ 快速排序:快速,但不稳定。优势在于原地排序,需要很小的辅助数组,并且内循环相对于其他的短小。

Ⅱ 递归实现简单的快速排序:参考博客白话经典算法系列之六 快速排序 快速搞定

Ⅲ整体的思路如下:

思路一:

① 寻找一个切分元素; ② 生成两个指针一个从左到右遍历一个从右到左遍历; ③ 从左到右寻找比切分元素大的,从右向左寻找比切分元素小的; ④ 进行判断 如果 左指针 小于 右指针(还没有相遇) 就继续执行; ⑤ 最后一步将左侧的最后一个元素和切分元素进行更换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
protected static int getIndex2(int[]a,int low,int high){
int key = a[low];
int i = low,j = high+1;
while(true){
//先执行 i++ 再判断a[i] < key,左侧从第二个元素开始比较了。
while(a[++i] < key) if(i == high) break;
// 先执行 --j 再判断a[j] > key,右侧从倒数第一个元素开始比较了。
while(a[--j] > key) if(j == low) break;
if(i >= j) break;
swap(a,i,j);
}
swap(a,j,low);
return j;
}

思路二: ① 设置第一个数是基数; ② 从右往左扫描碰到比基数小的就放在基数的左侧; ③ 接着从左向右扫描碰到比基数大的就放在上面那个数交换的位置; ④ 最后将i的位置赋值为 key

这样 key的左边都小于 key,key的右边都大于 key
举个例子:

source 2 4 3 5 10 6 9 0 12 17
one 0 2 3 5 10 6 9 4 12 17
two 0 2 3 5 10 6 9 4 12 17
three 0 2 3 4 5 6 9 10 12 17
four 0 2 3 4 5 6 9 10 12 17
five 0 2 3 4 5 6 9 10 12 17
six 0 2 3 4 5 6 9 10 12 17
seven 0 2 3 4 5 6 9 10 12 17
eight 0 2 3 4 5 6 9 10 12 17
nine 0 2 3 4 5 6 9 10 12 17
ten 0 2 3 4 5 6 9 10 12 17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
protected static int getIndex1(int[] a,int low,int high){
int key = a[low];//挖坑完毕
int i = low,j = high;
while(i < j){
while(i < j && a[j] >= key )// 从右往左走
j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] <= key)// 从左往右走
i++;
if(i < j) a[j--] = a[i];
}
a[i] = key;
return i;
}

Ⅳ 排序的算法:

1
2
3
4
5
6
7
public static void sort(int a[],int low,int high){
if(low < high){
int i = getIndex1(a,low,high);//获取中间的位置
sort(a,0,i-1);//左边排序
sort(a,i+1,high);//右边再排序
}
}

Ⅴ 全部代码

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 QuickSort {
protected static int getIndex1(int[] a,int low,int high){
int key = a[low];//挖坑完毕
int i = low,j = high;
while(i < j){
while(i < j && a[j] >= key )// 从右往左走
j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] <= key)// 从左往右走
i++;
if(i < j) a[j--] = a[i];
}
a[i] = key;
return i;
}
protected static int getIndex2(int[]a,int low,int high){
int key = a[low];
int i = low,j = high+1;
while(true){
while(a[++i] < key) if(i == high) break;
while(a[--j] > key) if(j == low) break;
if(i >= j) break;
swap(a,i,j);
}
swap(a,j,low);
return j;
}
/*数组中元素交换*/
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void sort(int a[],int low,int high){
if(low < high){
int i = getIndex1(a,low,high);//获取中间的位置
sort(a,0,i-1);//左边排序
sort(a,i+1,high);//右边再排序
}
}
/*主函数*/
public static void main(String[] args) {
int temp[] = {2,4,3,5,10,6,9,0,12,1,7,22,15,11,14,13,8};
sort(temp,0,temp.length-1);
traverse(temp);
}
/*遍历*/
private static void traverse(int[] temp) {
for(int x:temp)
System.out.print(" " + x);
System.out.println();
}
}