-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort1.java
More file actions
58 lines (54 loc) · 1.04 KB
/
Copy pathQuickSort1.java
File metadata and controls
58 lines (54 loc) · 1.04 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
public class QuickSort1{
public static void main(String[] args)
{
//新建一个数组
int arr[]=new int[]{8,9,5,2,15,60,20,40};
quicksort(arr,0,arr.length-1);
for(int a:arr)
{
System.out.println(a);
}
}
public static int Partition(int arr[],int first,int end)
{
//i，j分别存取arr数组的头和尾
int i=first,j=end;
while(i<j){
while(i<j&&arr[i]<arr[j])
{
j--;
}
//从后面往前扫描，如果小于轴指则 ，且i<j，则交换
if(i<j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;//切换到从i开始往后扫描
}
while(i<j&&arr[i]<arr[j])
{
i++;
}
//如果arr[i]>arr[j]
if(i<j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
j--;//切换到从j开始往前扫描
}
}
return i;
}
public static void quicksort(int arr[],int first,int end)
{
int pivot=0;//定义一个变量来存取轴值
if(first<end)
{
pivot=Partition(arr,first,end); //取得第一个轴值得位置
quicksort(arr,first,pivot-1);//划分对左侧进行快排
quicksort(arr,pivot+1,end);//对右侧进行快排
}
}
}