欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java算法(三)详细解析:快速排序

程序员文章站 2024-03-25 13:21:34
...

原理:

  快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,都是采用不断的比较和移动来实现排序的。快速排序是一种非常高效的排序算法,它的实现减少了总的比较次数和移动次数。

  选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素或者最后一个元素。
   一次循环:先从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。接着分别比较左右两边的序列,重复上述的循环。

我今天写了两个方法,第一种是通过单下标方式,还有一种是双下标方式实现快速排序。

代码中注释都很齐全,这边就不在赘述。

单下标:

 /**
     * 递归调用
     *
     * @param array
     * @param start
     * @param end
     */
    public static void quick(int array[], int start, int end) {
        //当数组只有一个元素的时候结束
        if (end - start < 1) {
            return;
        }
        //获取基数
        int part = quickSort(array, start, end);
        //和基数相等的就下标加1,继续排序
        if (part == start)
            quick(array, part + 1, end);
        else if (part == end)
            quick(array, start, end - 1);
        else {
            quick(array, start, part - 1);
            quick(array, part + 1, end);
        }
    }

    /**
     * 实现从小达到快速排序   单下标方式
     *
     * @param array [ 8 2 1 7 3 5 9 6 ]
     * @param start
     * @param end
     */
    public static int quickSort(int array[], int start, int end) {
        //选择一个基数,就用数组最后一个吧
        int base = array[end];
        //假设数组中所有的数都比基数小  num 代表该数组中一共有几个比他小的数,排序完的时候把基数换到num的位置
        int num = start;
        //开始比较
        for (int i = start; i < end; i++) {
            if (array[i] < base) {
                //把小于基数的数放在左边
                changePosition(array, i, num);
                num++;
            }
        }
        //比较完之后把基数放在num的位置上,
        changePosition(array, num, end);
        return num; //返回基数的位置
    }

    /**
     * 改变两个数的位置
     *
     * @param array
     * @param index1
     * @param index2
     */
    public static void changePosition(int array[], int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

双下标:

 /**
     * 快速排序  双下标
     *
     * @param array
     * @param low
     * @param high  {6, 1, 8, 9, 5, 2, 3, 7, 10, 4}
     */
    public static void quickS(int array[], int low, int high) {
        int base = array[low]; //基准位数组第一个数
        int start = low; //代表从前往后找到了比基准大的数的下标
        int end = high;  //代表从后往前找到了比基准小的数的下标
        while (end > start) {//只有当数组两个数有可比性的时候再进入循环
            //先从数组后面往前比较,如果找到了比基准小的,记录位置并和start交换位置
            while (end > start && array[end] >= base) {
                end--;
            }
            System.out.println("end= " + end);
            //调换位置
            if (array[end] <= base) {
                changePosition(array, end, start);
                System.out.println("从后面调换了一次位置后:" + Arrays.toString(array));
            }

            //从前往后比较,如果找到了比基准大的,记录位置并和end交换位置
            while (end > start && array[start] <= base) {
                start++;
            }
            System.out.println("start= " + start);
            if (array[start] >= base) {
                changePosition(array, start, end);
                System.out.println("从前面调换了一次位置后:" + Arrays.toString(array));
            }
        }
        System.out.println("循环结束后:start= " + start + " end= " + end);
        //根据基准分成左右两边再递归
        if (start > low)
            quickS(array, low, start - 1);
        if (end < high)
            quickS(array, end + 1, high);
    }

最后附上运行函数

public static void main(String[] args) {
        int[] arr = {6, 1, 8, 9, 5, 2, 3, 7, 10, 4};
        quickS(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。