专栏首页指缝阳光算法——快速排序

算法——快速排序

一、简介

步骤如下

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

二、编码如下

/**
 * 快速排序
 *
 * @author xjf
 * @date 2020/8/28 16:08
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 20, 8, 666, 56, 256, 7, 256, 351, 666, 96};
        System.out.println("排序前:");

        for (int i : arr) {
            System.out.print(i + "  \t");
        }

        System.out.println();
        quickSort(arr, 0, arr.length -1);
        System.out.println("排序后:");
        for (int i : arr) {
            System.out.print(i + "  \t");
        }
    }

    /**
     * 快速排序实现方法
     *
     * @param arr 原始无序数组
     * @param low 数组起始索引
     * @param high 数组最大索引
     */
    private static void quickSort(int[] arr, int low, int high){
        if (low < high) {
            int i = low;
            int j = high;
            // 取第一个数为基准数
            int x = arr[low];

            // 一轮排序需要将元素都遍历一遍
            while (i < j) {
                // 首先从右往左遍历,直到找到一个比基准数小的位置索引
                while (i < j && arr[j] >= x) {
                    j--;
                }
                // 将在右边小于基准的数赋值到左边的位置 i 上,初次 i 位置的数就是基准数,被保存在 x 变量上,所以覆盖没问题
                if (i < j) {
                    arr[i++] = arr[j];
                }

                // 再从左往右遍历,找比基准数大的数
                while (i < j && arr[i] < x) {
                    i++;
                }
                // 将左边大的数,赋值给右边的位置 j 上,此时 j 这个位置的数已经被赋值到左边去了,所以直接覆盖没问题
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }

            // 上面的外层循环条件为 i < j,所以跳出循环时,i = j。
            // 此处这个点的值是被赋值到其他位置上的,所以需要填充这个点的真实值,即为基准值
            arr[i] = x;

            // 上面执行一次排序后,数据根据基准值分成了两块,再分别对两块进行同样的排序
            quickSort(arr, low, i - 1);
            quickSort(arr, i + 1, high);
        }
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CentOS7卸载OpenJDK,然后安装Oracle JDK

    凡人飞
  • 算法——二分查找算法

    介绍:二分查找,也称折半搜索,是一种在 有序数组 中 查找某一特定元素 的搜索算法。下面简单介绍其优缺点,以及编码实现。

    凡人飞
  • Sharding-JDBC 实现分库分表

    凡人飞
  • 交换排序之快速排序

    通常是以第一个元素为基准元素开始,然后从头部和尾部开始遍历,左边都是比基准元素小,右边是比基准元素大。

    OPice
  • 排序算法

    基本思想:现在有一个数组arr= {12,35,99,18,76},需要将其从小到大排序

    说故事的五公子
  • Java|实现冒泡排序

    冒泡排序是一种简单的常见的排序算法,算法重复的走访排序的数组,通过不断的两两比较,最终把最大数浮于上方,好比是可乐的气泡冒泡的过程,所以生动的称之为“冒泡排序”...

    算法与编程之美
  • 结构与算法(04):排序规则与查找算法

    递归就是方法自己调用自己,每次调用时传入不同的变量,可以让代码变得简洁。递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法,递归式方...

    知了一笑
  • 排序算法 --- 堆排序

    可以发现,arr[i] > arr[2*i + 1],arr[i] > arr[2*i + 2]。

    贪挽懒月
  • 动画+原理+代码,解读十大经典排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

    昱良
  • Java 必会10大的经典算法

    原文链接:https://github.com/hustcc/JS-Sorting-Algorithm

    业余草

扫码关注云+社区

领取腾讯云代金券