欢迎光临
我们一起进阶

Java 数组(二):快速排序

扫码或搜索:沉默王二
发送 290992
即可立即永久解锁本站全部文章

Java 数组的快速排序

快速排序思想

快速排序的思想通过先选择一个基准点,然后通过左右两个指针先后遍历,并且依次比较数值与基准点的大小,比基准点大的数据放到右边,比基本点小的数据放到左右。在循环遍历左右两边依次进行,每次移到一个数据过后,都会更换遍历方向。

快速排序的核心思想是分治思想。

代码实现

package com.silence.arts.xiaobai;

/**
 * 
 * Function:
 * Author:@author ziyou
 * Date:2019-07-29 22:59
 * Desc:无
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    private static void quickSort(int[] array, int left, int right) {
        if (left < right) {
            int middle = middle(array, left, right);
            quickSort(array, left, middle - 1);
            quickSort(array, middle + 1, right);
        }
    }

    /**
     * 找到中间
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int middle(int[] array, int left, int right) {

        int base = array[left];
        while (left < right) { while (right > left && array[right] >= base) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= base) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = base;
        return left;
    }

}

总结

快速排序几个关键点

  1. 递归调用
  2. 找到中间点
  3. 从右递减
  4. 从左递增

注意:middle 函数找到的中间点,此时 left 和 right 两者是一样的,我们这里的基准点采用的是数组的最左边的数据。

赞(0) 打赏
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

小白学堂,学的不止是技术,更是前程

关于我们免责声明

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏