专栏首页Golang开发quickSort快速排序

quickSort快速排序

1. 算法步骤

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序; 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

quickSort.gif

public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值(pivot)
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
```![quickSort.gif](https://upload-images.jianshu.io/upload_images/143845-771d1b8d2ab769f3.gif?imageMogr2/auto-orient/strip)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SelectionSort选择排序

    羊羽shine
  • BubbleSort冒泡排序

    冒泡排序是一种简单的排序算法。它适合小规模数据的排序,并且其效率比较低。冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没...

    羊羽shine
  • InsetSort插入排序

    羊羽shine
  • 一遍文章搞定快排-java版

    首先将将要排序的数据分割成两组,其中一组的所有数据都要比另外一组的任何一个数据小,然后再按照此方法进行快速排序。

    shengjk1
  • 第三节:带你详解Java的操作符,控制流程以及数组

    大家好,我是 Vic,今天给大家带来带你详解Java的操作符,控制流程以及数组的概述,希望你们喜欢

    达达前端
  • 各种排序算法总结

    排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今...

    前朝楚水
  • C语言实现插入排序

    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

    仙士可
  • 深入浅出的排序算法-选择排序

    选择排序是第一个人和后续排序的人进行比较,若第一个人大于第二个人,就进行交换,那么这时第一人就是最小的,然后这时的第一个人和第三个人进行比较,若这时的第一个人大...

    达达前端
  • 快速排序与寻找第k小的数算法

    慕课网 首发了,放在垂直领域吧。简书备份。 出现了一点小问题,就是index,要注意。想法网上一大堆,不多说了。 ubuntu18下输入法有问题,sogou...

    东风冷雪
  • 八大排序算法

    ​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

    lwen

扫码关注云+社区

领取腾讯云代金券