算法-快速排序

快速排序

//1．先从数列中取出一个数作为基准数。
//2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
//3．再对左右区间重复第二步，直到各区间只有一个数。
public static void quickSort(int[] target, int left, int right ) {
    if (left >right) return;

    int baseValue = target[left];//取出基准元素
    int i = left;
    int j = right;
    //左右两边同时跟目标元素做对比. 分出两个数组， 一个左一个右
    while (i < j) {

         // 从右向左找第一个小于baseValue的数，一直找，直到找到或者一直都没有为止
        while(i < j && target[j] >= baseValue)
        j--;
        if(i < j)
            target[i++] = target[j];

         // 从左向右找第一个大于等于baseValue的数,一直找，直到找到或者一直都没有为止
        while(i < j && target[i] < baseValue)
            i++;
        if(i < j)
            target[j--] = target[i];
    }
    target[i] = baseValue;

    quickSort(target,left,i-1);
    quickSort(target,i+1,right);
}

变形 ：

快速排序（剪枝法）-找出数组中第k小的数

• 采用快速排序的思想来实现。选一个数 baseValue = target[left] 作为枢纽， 把比他小的数都放在他的左边，比他大的数放在他的右边，然后判断baseValue 的位置，
• 如果他的位置 == k-1, 那么它就是第k个最小的数；
• 如果它的位置 < k-1, 那么第k个小的元素一定在数组的右半部分, 采用递归的方法在数组的右半部分继续查找；
• 如果它的位置 > k-1, 那么第k个小的元素一定在数组的左半部分, 采用递归的方法在数组的左半部分继续查找；

    public static void main(String[] args) {
        int target[] = {5, 42, 31, 32, 11};
        for (int i = 1; i <= target.length; i++) {
            System.out.println("第" + i + "小的数 ：" + quickSort_k_Element(target, 0, target.length - 1, i));
        }
    }

    private static int quickSort_k_Element(int[] target, int left, int right, int k) {
        if (left > right) return Integer.MIN_VALUE;//表示未找到

        int baseValue = target[left];//取出基准元素
        int i = left;
        int j = right;
        //左右两边同时跟目标元素做对比. 分出两个数组， 一个左一个右
        while (i < j) {
            // 从右向左找第一个小于baseValue的数，一直找，直到找到或者一直都没有为止
            while (i < j && target[j] >= baseValue) 
                j--;
            if (i < j)
                target[i++] = target[j];
            // 从左向右找第一个大于等于baseValue的数,一直找，直到找到或者一直都没有为止
            while (i < j && target[i] < baseValue)
                i++;
            if (i < j)
                target[j--] = target[i];
        }
        target[i] = baseValue;

//      判断i+1与k的大小
        if (i + 1 == k) {
            return baseValue;
        } else if (i + 1 > k) {
            return quickSort_k_Element(target, left, i - 1, k);
        } else {
            return quickSort_k_Element(target, j + 1, right, k);
        }
    }