算法实现-快速排序
?
package com.quicksort;
?
public class QuickSort {
?
public int partiTion(int[] a, int start, int end){
int i = start - 1;//小于数组中最后一个数的索引值
int x = a[end];
for(int j = start;j<=end - 1;j++){//将数组分为大于最后一个值部分和小于最后一个值的部分
if(a[j]<=x){
i = i+1;
int tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}
}
//将数组中最靠前的大于最后一个数的数和数组中最后一个数交换,保证交换后的数组是这样一种情形:a[x<=i]<a[i+1]<a[i+2<=x]
int tmp = a[i+1];
a[i+1] = a[end];
a[end] = tmp;
return i+1;
}
public void quickSort(int[] a, int start, int end){
if(start>end){
return;
}
int q = this.partiTion(a, start, end);//在原数组的基础上将数组分为大于某值和小于某值的两堆
quickSort(a, start, q - 1);//对选定值左边的值递归快排
quickSort(a, q + 1, end);//对选定值右边的值递归快拍
}
public static void main(String[] args) {
int[] a = new int[]{0,5,6,7,3,2};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(a, 1, a.length-1);
for(Integer i : a){
System.out.println(i);
}
}
?
}
