【TODO】【算法】快速排序

Flands 发布于2019-08-16 18:00 / 551人阅读

摘要：双边循环法快速排序的基本方法待排序的数组开始的结束的循环次数找到基准位置。需要加限制条件和指针重合点交换单边循环法分治单循环法把小于基准值的，交换和基准值的到的左边待交换的数组起始下标结束下标默认起始位置为基准值基准值的位置，不断移动。

0. 索引 1. 简单介绍

关于原理，虽然很重要，但是在这里不做过多介绍。因为随便搜索一下。就可以找到更好的答案。

本质是回顾，记住核心的思想，然后通过code 深刻已有概念的印象。

2. 双边循环法

/**
 * 快速排序的基本方法
 *
 * @param intArr     待排序的数组
 * @param startIndex 开始的 index
 * @param endIndex   结束的 index
 * @return 循环次数
 */
public static long sort(int[] intArr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return 0;
    }
    // 找到基准位置。 位置左边的的都是小于的，位置右边的都是大于的。 + 同事做好了排序
    int pivotIndex = doubleSideSortFindPivot(intArr, startIndex, endIndex);

    sort(intArr, startIndex, pivotIndex - 1);
    sort(intArr, pivotIndex + 1, endIndex);

    return 1;
}

/**
 * 分治（双边循环法）
 *
 * @param intArr     待交换的数组
 * @param startIndex 起始下标
 * @param endIndex   结束下标
 */
public static int doubleSideSortFindPivot(int[] intArr, int startIndex, int endIndex) {
    int pivotVal   = intArr[startIndex];
    int leftIndex  = startIndex;
    int rightIndex = endIndex;

    // MARK : 之前用if leftIndex < rightIndex 报错
    while (leftIndex != rightIndex) {

        // 之前自己的写法比较混乱
        // step 1 :控制 right 指针，左移
        // 错误1 ： 使用了 if ，毕竟可以一直左移。 逻辑判断 MARK
        while (leftIndex < rightIndex && intArr[rightIndex] > pivotVal) {
            rightIndex--;
        }
        // step 2 : 控制 left 指针 右移
        while (leftIndex < rightIndex && intArr[leftIndex] <= pivotVal) {
            leftIndex++;
        }

        // step 3 ：交换 left 和 right。 需要加限制条件
        if (leftIndex < rightIndex) {
            int temp = intArr[leftIndex];
            intArr[leftIndex] = intArr[rightIndex];
            intArr[rightIndex] = temp;
        }
    }

    // 【replace】pivot和指针重合点交换
    intArr[startIndex] = intArr[leftIndex];
    intArr[leftIndex] = pivotVal;

    return leftIndex;
}

3. 单边循环法

/**
 * 分治（单循环法） 把 小于基准值的，交换(和基准值的index )到 pivot 的左边
 *
 * @param intArr     待交换的数组
 * @param startIndex 起始下标
 * @param endIndex   结束下标
 */
public static int oneSideSort(int[] intArr, int startIndex, int endIndex) {
    // 默认起始位置为基准值
    int pivotVal = intArr[startIndex];
    // 基准值的位置，不断移动。左边的代表交换过来的小于 pivotVal 的
    int mark = startIndex;

    // 如果小于基准值的，交换，mark 右移
    for (int i = startIndex + 1; i <= endIndex; i++) {
        // 小于的做交换
        if (intArr[i] < pivotVal) {
            mark++; // 基准位右移
            int temp = intArr[mark];
            intArr[mark] = intArr[i];
            intArr[i] = temp;
        }
    }

    // 交换
    intArr[startIndex] = intArr[mark];
    intArr[mark] = pivotVal;

    return mark;
}

GPU云服务器云服务器快速排序算法最好的快速排序算法最快速的排序算法快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74881.html

【TODO】【算法】鸡尾酒排序

0. 索引 1. 基本介绍 2. 算法实现

dinfer 2019-08-16 18:00 评论0 收藏0
Java常用的八种排序算法与代码实现精解

摘要：直接插入排序的算法重点在于寻找插入位置。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。简单选择排序常用于取序列中最大最小的几个数时。将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。 1.直接插入排序直接插入排序算法是排序算法中最简单的，但在寻找插入位置时的效率不高。基本思想就是将一个待排序的数字在已经排序的序列中寻找找到一个插...

2501207950 2019-08-14 18:07 评论0 收藏0
利用PHP实现常用的数据结构之二叉树（小白系列文章六）

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～ /** * PHP二叉树算法 * Create...

Cympros 2019-06-28 13:56 评论0 收藏0
利用PHP实现常用的数据结构之二叉树（小白系列文章五）

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～ /** * PHP二叉树算法 * Create...

developerworks 2019-06-27 16:27 评论0 收藏0
【算法】冒泡排序

摘要：简单实现左边是大不是正常的排序顺序的做交换考虑优化优化冒泡排序优化版本，节约有序的第一轮，永远是找到最大的第二轮，找到的是第二大的，所以右边个永远是有序的如果有一种特殊情况，右边经过对比，发现不需要交换了，那就是后面的都是最大的。 No bb . Show me the code 1. 简单实现 public static long sort(int[] intArr) { ...

kel 2019-08-16 18:00 评论0 收藏0