快速排序使用分治法策略,分 就是把一个序列分为较小数值和较大数值的2个子序列,治 就是通过递归地排序两个子序列
快速排序的步骤是:
- 挑选基准值:从数列中挑出一个元素,称为基准
- 分割:重新排列数列,所有比基准小的元素摆放在基准前面,所以比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成
- 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序
递归终止条件是数列的大小是零或一,此时该数列显然已经有序了。
public class Application {
public static void qSort(int[] arr, int head, int tail){
if(head >= tail || arr == null || arr.length <= 1){
return;
}
int i = head;
int j = tail;
int pivot = arr[(head + tail) / 2];
while (i <= j){
while (arr[i] < pivot){
++i;
}
while (arr[j] > pivot){
--j;
}
if(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
}else if(i == j){
++i;
}
}
qSort(arr,head,j);
qSort(arr,i,tail);
}
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
qSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
网友评论