快速排序
快速排序使用分治法策略，分 就是把一个序列分为较小数值和较大数值的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));
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-2-28 1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读