平均时间复杂度:O(N logN)
package com.bj.zl.learn.sort;
/**
* 快速排序
*
* 思路
* 取任一一个元素为目标元素,然后用目标元素与其他元素进行比较
* 比目标元素大的放在右边,小的放在左边.
* 然后对左子树和右子树做以上递归调用,直到左子树和右子树只剩下一个元素为止
*
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {50,88,79,52,548,1,2,7,5,69};
quickSort(arr,0,arr.length-1);
for (int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
private static void quickSort(int[] arr,int left,int right){
int r =right;
int l =left;
int base = arr[left];
while (left < right){
while (left<right && arr[right] >= base){
right--;
}
arr[left] =arr[right];
while (left<right && arr[left] <=base){
left++;
}
arr[right] = arr[left];
}
arr[left] =base;
if (left < r){
quickSort(arr,right+1,r);
}
if (right > l){
quickSort(arr,l,left-1);
}
}
}
