01_04_快速排序(Quick Sort)

这篇具有很好参考价值的文章主要介绍了01_04_快速排序(Quick Sort)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

快速排序(Quick Sort)

快速排序(Quick Sort)介绍:

是一种常用的排序算法,它采用分治的策略来对待排序的序列进行排序。快速排序的基本思想是选择一个基准元素,通过一趟排序将序列分割成两个子序列,其中一个子序列的所有元素都小于基准元素,另一个子序列的所有元素都大于基准元素。然后对这两个子序列分别进行递归排序,最终将整个序列排序完成。

快速排序(Quick Sort)原理:
  1. 选择一个基准元素(通常为序列的第一个或最后一个元素)。
  2. 将序列分成两部分,所有比基准元素小的元素放在基准元素的左边,所有比基准元素大的元素放在基准元素的右边。
  3. 对左右两个子序列分别进行递归排序,直到子序列的长度为1或0,即序列已经有序。
Java 代码实现:
package com.algorithm.sort;

/**
 * 快速排序的原理可以描述如下:
 * <p>
 * 1.选择一个基准元素(通常为序列的第一个或最后一个元素)。
 * 2.将序列分成两部分,所有比基准元素小的元素放在基准元素的左边,所有比基准元素大的元素放在基准元素的右边。
 * 3.对左右两个子序列分别进行递归排序,直到子序列的长度为1或0,即序列已经有序。
 */

public class QuickSort {

    /**
     * 快速排序算法实现
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high); // 将序列分成两部分,并返回基准元素的位置
            quickSort(arr, low, pivotIndex - 1); // 对左子序列进行递归排序
            quickSort(arr, pivotIndex + 1, high); // 对右子序列进行递归排序
        }
    }

    /**
     * 将序列分成两部分
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     * @return 基准元素的位置
     */
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准元素
        int i = low - 1; // i 表示小于基准元素的区域的边界

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j); // 将比基准元素小的元素放到小于区域的右边
            }
        }

        swap(arr, i + 1, high); // 将基准元素放到小于区域和大于区域的中间
        return i + 1; // 返回基准元素的位置
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param arr 待排序数组
     * @param i   数组下标
     * @param j   数组下标
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 测试方法
     *
     * @param args todo
     */
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
代码简单解释:

在上述代码中,quickSort 方法接受一个整数数组 arr、数组的最低索引 low 和最高索引 high 作为输入,并使用快速排序算法对指定范围内的元素进行排序。partition 方法用于将序列分成两部分,并返回基准元素的位置。swap 方法用于交换数组中两个元素的位置。main 方法中创建了一个示例数组 arr,并调用 quickSort 方法进行排序。最后,打印排序后的数组结果。

程序执行结果:
排序后的数组:
11 12 22 25 34 64 90 
Process finished with exit code 0
备注:
  • 快速排序的平均时间复杂度为O(nlogn),它是一种高效的排序算法,在大多数情况下具有较好的性能。
  • 然而,最坏情况下的时间复杂度为O(n^2),当序列已经有序或基本有序时,快速排序的性能会下降。
  • 为了解决这个问题,可以使用随机化的快速排序或者优化的快速排序算法。

============================================ 优化快排算法 ============================================

优化快速排序(Quick Sort)

优化快速排序(Quick Sort)原理:
  1. 随机化选择基准元素:在上述代码中,基准元素的选择是固定的,通常选择第一个或最后一个元素。但如果序列已经有序或近乎有序,固定选择基准元素可能导致快速排序的性能下降。为了解决这个问题,可以随机选择基准元素,例如从待排序序列中随机选择一个元素作为基准元素。

  2. 三数取中法选择基准元素:选择一个合适的基准元素可以避免快速排序在某些特定情况下的退化。一种常用的方法是使用三数取中法,即从待排序序列的第一个、中间和最后一个元素中选择中间大小的元素作为基准元素。

  3. 插入排序优化:对于小规模的子序列,快速排序的递归调用和分割操作可能会带来额外的开销。可以设置一个阈值,在子序列长度小于阈值时,使用插入排序或其他简单排序算法来代替快速排序。

Java 代码实现:
package com.algorithm.sort;

/**
 * 快速排序算法的优化,可以考虑以下几个方面:
 * <p>
 * 1.随机化选择基准元素:
 * 在上述代码中,基准元素的选择是固定的,通常选择第一个或最后一个元素。
 * 但如果序列已经有序或近乎有序,固定选择基准元素可能导致快速排序的性能下降。
 * 为了解决这个问题,可以随机选择基准元素,例如从待排序序列中随机选择一个元素作为基准元素。
 * 2.三数取中法选择基准元素:
 * 选择一个合适的基准元素可以避免快速排序在某些特定情况下的退化。
 * 一种常用的方法是使用三数取中法,即从待排序序列的第一个、中间和最后一个元素中选择中间大小的元素作为基准元素。
 * 3. 插入排序优化:
 * 对于小规模的子序列,快速排序的递归调用和分割操作可能会带来额外的开销。
 * 可以设置一个阈值,在子序列长度小于阈值时,使用插入排序或其他简单排序算法来代替快速排序。
 */

import java.util.Random;

public class QuickSortOptimized {

    /**
     * 优化后的快速排序算法实现
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            if (high - low + 1 <= 10) { // 设置阈值为10
                insertionSort(arr, low, high); // 使用插入排序
            } else {
                int pivotIndex = randomizedPartition(arr, low, high); // 随机化选择基准元素
                quickSort(arr, low, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, high);
            }
        }
    }

    /**
     * 随机化选择基准元素
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     * @return 分成两部分的序列
     */
    public static int randomizedPartition(int[] arr, int low, int high) {
        int randomIndex = new Random().nextInt(high - low + 1) + low; // 随机选择索引
        swap(arr, randomIndex, high);
        return partition(arr, low, high);
    }

    /**
     * 将序列分成两部分
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     * @return 基准元素的位置
     */
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    /**
     * 插入排序算法实现:在子序列长度小于阈值时,使用插入排序代替快速排序。
     *
     * @param arr  待排序数组
     * @param low  数组的最低索引
     * @param high 数组的最高索引
     */
    public static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param arr 待排序数组
     * @param i   数组下标
     * @param j   数组下标
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 测试方法
     *
     * @param args todo
     */
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
代码简单解释:

在上述优化代码中,randomizedPartition 方法用于随机化选择基准元素,并将其交换到待排序序列的最后一个位置。quickSort 方法中加入了阈值判断,当子序列长度小于等于阈值时,使用插入排序代替快速排序。其他部分与之前的代码类似。文章来源地址https://www.toymoban.com/news/detail-497413.html

程序执行结果:
排序后的数组:
11 12 22 25 34 64 90 
Process finished with exit code 0
备注:
  • 运行优化后的代码将得到与之前相同的排序结果。
  • 这些优化措施可以提高快速排序算法的性能,在处理大规模数据或特定情况下的排序任务时,能够更好地发挥快速排序的优势。

到了这里,关于01_04_快速排序(Quick Sort)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 01_01_冒泡排序(Bubble Sort)

    冒泡排序(Bubble Sort)介绍: 是一种简单的排序算法。它通过多次遍历待排序的元素,比较相邻两个元素的大小,并根据需要交换它们的位置,从而将较大元素逐渐“冒泡”到最右侧,知道整个序列排序完成。 冒泡排序(Bubble Sort)原理: 从序列的第一个元素开始,依次比较

    2024年02月09日
    浏览(28)
  • 01_02_选择排序(Selection Sort)

    选择排序(Selection Sort)介绍: 是一种简单的排序算法。它的原理是每次从待排序的元素中选择最小(或最大)的元素,将其放置在已排序序列的末尾,然后再从剩余的未排序元素中选择最小(或最大)的元素,以此类推,直到整个序列排序完成。 选择排序(Selection Sort)原

    2024年02月11日
    浏览(31)
  • 【C++STL】快速排序算法(sort)的原理与使用

    一、 sort 算法原理 std::sort 是 C++ 标准库中提供的排序算法,它使用的是一种经典的排序算法—— 快速排序 (Quicksort)或者是其变种。 快速排序是一种基于比较的排序算法,通过不断地选择一个基准值(pivot),将待排序序列分割为两个子序列,其中一个子序列的所有元素小

    2024年02月09日
    浏览(42)
  • C#中sort排序相关用法介绍

     C#中,List.Sort() 不仅为我们提供了默认的排序方法,还为我们提供了4种自定义排序的方法,通过默认排序方法,我们无需重写任何Sort()方法的实现代码,就能对单参数类型的List数据进行单一规则的排序,如果通过对这些方法进行改进我们可以轻松做到对多参数、多规则的复

    2024年02月15日
    浏览(56)
  • Intel Quick Sync Video(QSV)(快速视频同步)介绍

    参考文章:英特尔® 快速视频同步 (Quick Sync Video) 技术-英特尔® 官网 Intel Quick Sync Video(QSV)是由Intel开发的专门用于视频编码和解码的技术。这项技术从Sandy Bridge微架构开始引入,自那时起,一直被集成在Intel的大多数桌面和移动处理器中。 这项技术充分利用了内置在处理器

    2024年02月20日
    浏览(37)
  • 十大排序算法之冒泡排序、快速排序的介绍

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 说起来冒泡排序,是我们接触到的最早的一个排序算法了,这次就当进行一个巩固提升了。冒泡排序还被称为 交换排序 。 冒泡排序: 它重

    2024年02月07日
    浏览(42)
  • 数据结构——快速排序的介绍

    快速排序是霍尔(Hoare)于1962年提出的一种二叉树结构的交换排序方法。快速排序是一种常用的排序算法,其基本思想是通过选择一个元素作为\\\"基准值\\\",将待排序序列分割成两个子序列,其中一个子序列的元素都小于等于基准值,另一个子序列的所有素都大于基准值。然后对这

    2024年02月11日
    浏览(40)
  • 【数据结构】- 排序(详细介绍几种排序算法!!!*直接插入排序,*希尔排序,*选择排序,*堆排序,*冒泡排序,*快速排序,*归并排序)

    排序无处不在,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 内部排序 :数据元素全部放在内存中的排序。 外部排序 :数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 今天

    2024年01月20日
    浏览(59)
  • 排序算法(stable_sort(), sort())

    sort函数我相信大家都不陌生,今天介绍一个新的排序算法stable_sort stable_sort:稳定排序算法,维持相等元素的原有顺序。 假如我们定义一个字符串数组 这些字符串是按照字典序排列的,我们现在想要words按照单词长度从小到大重排的同时,还希望具有相同长度的元素按照字典

    2024年02月07日
    浏览(49)
  • 高通Quick Charge快速充电原理分析

    1 三段式AC充电器 涓流、恒流、恒压。 2 QC 2.0 2.1 高通Quick Charge 2.0 快速充电原理分析 QC 2.0快速充电需要手机端和充电器都支持才行。 当将充电器端通过数据线连到手机上时,充电器默认的是将D+和D-短接的,这样手机端探测到的充电器类型是DCP(参见本人另一篇博文《高通平

    2024年02月08日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包