快速排序

概述

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

Java实现

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {32,5,66,48,99,21,55};
        System.out.print("QuickSort \n");
        printArray(array);
        System.out.print("start:\n");
        quickSort(array,0,array.length-1);
//        printArray(array);
        System.out.print("end:\n");
    }

    static void quickSort(int[] data, int left, int right){
        if(left>=right)return;
        int i = left,j = right,key = data[left];
        while (i < j){
            while(i < j && key <= data[j])  // 在右边找到一个小于key的值
                j--;
            data[i] = data[j];
            while(i < j && key >= data[i])  // 在左边找到一个大于key的值
                i++;
            data[j] = data[i];
        }
        data[i] = key;// 放回key,此时key左边的数都比key小,key右边的数字都比key大
        printArray(data);
        // 对key的左右两边递归
        quickSort(data,left,i-1);
        quickSort(data,i+1,right);
    }

    static void printArray(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print("\n");
    }
}

排序效果

QuickSort
32 5 66 48 99 21 55 
start:
21 5 32 48 99 66 55 
5 21 32 48 99 66 55 
5 21 32 48 99 66 55 
5 21 32 48 55 66 99 
5 21 32 48 55 66 99 
end:

复杂度
时间复杂度: O(nlogn)