快速排序

上代码

package cn.likent.EightSortMethods;
/**
 * @author: kent
 * @date: 18/03/2018 14:25
 */
public class QuickSort {
    
    private static void swap(int[] array,int a,int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    private static int partition(int[] array, int lo, int hi){
        int i = lo;//头指针初始位置
        int j = hi + 1;//尾指针初始位置
        int key = array[lo];//切分元素
        while(true){
            while(array[++i] < key)if (i == hi) break;//从左开始寻找大于切分元素的,指针右移
            while(array[--j] >key)if (j == lo) break;//从右开始寻找小于切分元素的,指针左移
            if (i >= j)
                break;//相遇退出主循环
            swap(array,i,j);//交换下标i和j对应的元素
        }
        swap(array,lo,j);//获取切分值处用于返回之后的下次递归
        return j;
    }
    private static int[] sort(int[] array, int lo, int hi){
        if (hi > lo){
            int privotKey = partition(array,lo,hi);//获取切分值
            sort(array,lo,privotKey -1);//左边快排
            sort(array,privotKey + 1,hi);//右边快排
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array = new int[(int)(Math.random()* 50)];
        for (int i = 0;i < array.length;i++){
            array[i] = (int)(Math.random()*100);
        }
        for (int element:array
                ) {
            System.out.print(element + "  ");
        }
        System.out.println();
        for (int element: sort(array,0, array.length - 1 )
                ) {
            System.out.print(element + "  ");
        }
        System.out.println();
    }
}

长度为N的无重复数组排序平均需要2NlnN次比较
最坏N<exp>2</exp>次比较,随机打乱数据可以避免这种情况.