【算法】快速排序

算法系列博客

【算法】刷题范围建议和代码规范

【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 )

【字符串】最长回文子串 ( 中心线枚举算法 )

【字符串】最长回文子串 ( 动态规划算法 ) ★

【字符串】字符串查找 ( 蛮力算法 )

【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )

【算法】双指针算法 ( 有效回文串 II )

【算法】哈希表 ( 两数之和 )

【算法】快速排序

文章目录

算法系列博客
一、快速排序思想
二、快速排序代码

一、快速排序思想

快速排序的思想 : 先整体有序 , 后局部有序 , 分治算法 ;

先从数组中挑选出一个数 a , 然后进行分割 , 将数组分割成两部分 , 左半部分小于等于 a , 右半部分大于等于 a ;

此时数组左半部分肯定小于右半部分 ;

然后分别对左半部分和右半部分再次挑选一个数 , 进行分割 ;

递归进行分割操作 , 直到数组中所有元素排序完成 ;

分割数组时 , 分割条件是小于等于 / 大于等于的原因 :

分割时 , 挑选的数 a , 如果数组元素为 a , 则该元素即可以在左边 , 又可以在右边 ;

如果数组中除几个数之外 , 其它全都是一样的数 , 如 1,1,1,1,1,1,1,2 , 挑选数字时 , 大概率选中 1 , 此时如果要求左半部分严格小于 1 , 此时左半部分没有任何数值 , 很容易出现不均匀的划分 ;

快速排序的理想划分是每次划分 , 划分的左边和右边的元素个数基本差不多 , 递归时不会出现极端情况 ,

二、快速排序代码

整数排序 : https://www.lintcode.com/problem/463/

下面代码中有三个要点

分割中心点选取 ;
指针限制条件 ;
分割时判定要左右交换元素的条件 ;

取中心点, 一般取 start 与 end 索引的中心索引对应的数组元素值 ;

如下取中间值是强行指定的, 也可以随机指定 , 指定 start 与 end 之间的一个随机值 ;

尽量不选取 start 和 end 索引的值 , 如果选取开始/结束值 , 作为分割点 , 假如该数组是按照升序或降序排列 , 可能出现极端情况 ;

指针限制条件 , 分割遍历时的两个指针的条件是 left <= right , 这里不能是 left < right ;

如果使用 left < right 会造成死循环递归 , 导致栈溢出 ;

使用 [3,2,1,4,5] 进行推导 , 即可出现死循环 ;

判定左右元素交换时 , 必须用 array[left] < pivot 和 array[right] > pivot , 不能使用 array[left] <= pivot 和 array[right] >= pivot , 否则会造成死循环递归 , 导致栈溢出 ;

使用 [3,2,1,4,5] 进行推导 , 即可出现死循环 ;

快速排序的时间复杂度是

O(n log n)

;

代码示例 :

代码语言：javascript复制

class Solution {

    /**
     * 快速排序
     * @param A
     */
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }

        quickSort(A, 0, A.length - 1);
    }

    // 将 array 数组中 start 到 end 之间的元素进行排序
    private void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            // start 如果等于 end, 说明就一个元素, 不用排序
            // start 正常情况下不会大于 end
            return;
        }

        // 设置两个指针, 分别指向头尾
        int left = start, right = end;

        // 1. 分割操作第一步 : 取中心点
        // 取中心点, 一般取 start 与 end 索引的中心索引对应的数组元素值
        // 如下取中间值是强行指定的, 也可以随机指定 , 指定 start 与 end 之间的一个随机值
        // 尽量不选取 start 和 end 索引的值
        int pivot = array[(start   end) / 2];

        // 2. 分割操作第二部 : 进行数组元素分割
        // 注意此处, left 小于等于 right , 不能是小于
        while (left <= right) {
            // 找到一个不属于左边部分的元素, 将其交换到右边
            while (left <= right && array[left] < pivot) {
                // 如果遇到一个元素不属于左边, 则退出循环
                left  ;
            }
            // 找到一个不属于右边部分的元素, 将其交换到左边
            while (left <= right && array[right] > pivot) {
                // 如果遇到一个元素不属于右边, 则退出循环
                right--;
            }

            // 交换上述检测出来的需要交换的元素
            if (left <= right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;

                // 交换完毕后, 继续向后遍历
                left  ;
                right--;
            }
            // 交换完毕后, 继续循环, 该循环退出的条件是 left >= right
        }

        // 分割完毕后, 继续递归
        // 如果按照中心点分割完毕的话, 上面的循环退出, left >= right
        // 索引的分布如下 : start , right, left, end
        quickSort(array, start, right);
        quickSort(array, left, end);
    }
}

排序数组算法指针字符串

0 人点赞

【算法】快速排序

算法 系列博客

文章目录

一、快速排序思想

二、快速排序代码

算法系列博客