算法入门 - 快速排序

关注

发布于: 1 小时前

快速排序经常会出现在面试题中，甚至有个简称叫快排。这个待遇是其他排序算法不曾有过的待遇，包括网友的讨论都是默认快速排序。其实上一篇文章所提及的归并排序的性能很好而且很稳定，唯一的缺点是需要一个额外的 O(n)的空间开销。快排也是分治思想的一种应用，当可以把问题一分为二解决时，问题的复杂度会大大降低。

快速排序还有一个比较大的优势是：算法的实现相对简单。

从数组中挑出一个元素作为基准值，可以任意选择。
遍历一下数组，比基准值小的放左边，比基准值大的放右边，完成之后基准值这个位置就已经排序了。
基准值左右两边的数组各自递归执行一下以上的过程

有人说这个基准值的选择有什么讲究吗？没有，因为需要做交换，你也不可能正好选中那个中间的值。所以我建议直接选首位的元素就好了。

复杂度与适用场景

复杂度想必已经很清楚了，首先有一个比较和交换，要遍历整个列表所以是个 O(n)，然后分治会有一个 O(logn)，所以最终的复杂度为 O(nlogn)。但极少的概率下会产生 O(n^2)的最差情况，当数组完全有序时才会发生。应用场景方面就太多了，很多开发者应对简单排序时首选都是快速排序。

实现

public 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;    }     public int partition(int[] arr, int left, int right) {        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;    } public void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }

复制代码

发布于: 1 小时前阅读数: 4

ES_her0

关注

还未添加个人签名 2018.03.21 加入

还未添加个人简介

发布

暂无评论

创作场景

算法入门 - 快速排序

复杂度与适用场景

实现

ES_her0

评论