方法一：
|
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
|
public class QuickSortExp1{
public
static void main(String[] args){
int[] sortArray = new
int[]{5,7,4,2,9,8,3,6};
System.out.println("before sorting ,the numbers are:");
show(sortArray);
quickSort(sortArray,0,sortArray.length-1);
System.out.println("after sorting,the numbers are:");
show(sortArray);
}
public
static void quickSort(int[] intArray,int
left,int
right){
if(left<right){
int
partValue = intArray[left];
int
low = left;
int
high = right;
while(low < high){
while(low <high && intArray[high]>partValue){
high--;
}
intArray[low] = intArray[high];
while(low <high && intArray[low] <partValue){
low++;
}
intArray[high] = intArray[low];
}
intArray[low] = partValue;
quickSort(intArray,left,low-1);
quickSort(intArray,low+1,right);
}
}
public
static void show(int[] intArray){
for(int
i=0;i<intArray.length;i++){
System.out.print(intArray[i]+"\t");
}
System.out.println();
}
} |
方法二：
|
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
|
import java.util.*;
public class QuickSortExp2{
public
static void main(String[] args){
List<Integer> sortList = new
ArrayList<Integer>();
sortList.add(5);
sortList.add(7);
sortList.add(4);
sortList.add(2);
sortList.add(9);
sortList.add(8);
sortList.add(3);
sortList.add(6);
System.out.println("before sorting ,the numbers are:");
show(sortList);
quickSort(sortList);
System.out.println("after sorting,the numbers are:");
show(sortList);
}
public
static void quickSort(List<Integer> sortList){
if(sortList.size() <= 1){
return;
} else
if(sortList.size() == 2){
if(sortList.get(0)>sortList.get(1)){
int
temp = sortList.get(0);
sortList.set(0,sortList.get(1));
sortList.set(1,temp);
}
} else{
List<Integer> leftList = new
ArrayList<Integer>();
List<Integer> rightList = new
ArrayList<Integer>();
int
partValue = sortList.get(0);
for(int
i=1;i<sortList.size();i++){
if(sortList.get(i)< partValue){
leftList.add(sortList.get(i));
} else{
rightList.add(sortList.get(i));
}
}
quickSort(leftList);
quickSort(rightList);
sortList.clear();
sortList.addAll(leftList);
sortList.add(partValue);
sortList.addAll(rightList);
leftList.clear();
rightList.clear();
}
}
public
static void show(List<Integer> sortList){
for(Integer i:sortList){
System.out.print(i+"\t");
}
System.out.println();
}
} |