`

[排序算法4] - 快速排序

 
阅读更多

 

算法介绍:

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

 

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

 

假设用户输入了如下数组:
下标
0
1
2
3
4
5
数据
6
2
7
3
8
9

 

创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

我们取走了下标0的数据,于是,我们需要找到一个数字来替换他。由于我们要把所有比6小的数移动到左面,所以我们可以开始寻找比6小的数并从右往左找。别急,我们要按顺序找哦。不断递减j的值,我们发现下标3的数据比6小,于是把3移到下标0(实际是i指向的位置。代码中要用i,因为后面还会循环这个步骤,不用i的话第二次循环:
下标
0
1
2
3
4
5
数据
3
2
7
6
8
9
i=0 j=3 k=6
由于变量k已经储存了下标0的数据,所以我们可以放心的把下标0覆盖了。如此一来,下标3虽然有数据,但是相当于没有了,因为数据已经复制到别的地方了。于是我们再找一个数据来替换他。这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2是第一个比k大的,于是用下标2的数据7替换j指向的下标3的数据,数据状态变成下表:
下标
0
1
2
3
4
5
数据
3
2
6
7
8
9
i=2 j=3 k=6
重复上面的步骤,递减变量j。这时,我们发现i和j“碰头”了:他们都指向了下标2。于是,循环结束,把k填回下标2里,即得到结果。
如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。

 

快速排序的示例:

(a)一趟排序的过程:

 

 

(b)排序的全过程

 

算法的实现:

 

public class QuickSort {

    public static void main(String[] agrs) {
        int a[] = new int[] {49, 38, 65, 97, 76, 13, 27, 36, 91};
        System.out.println("排序之前:");
        print(a);

        System.out.println("\n开始排序:");
        sort(a, 0, a.length-1);

        System.out.println();
        System.out.println("排序之后:");
        print(a);
    }

    private  static void sort(int[] a, int l, int r) {
        if (l < r) {
            int privotLoc = partition(a, l, r);  //将表一分为二
            sort(a, l, privotLoc - 1);  //递归对左子表递归排序
            sort(a, privotLoc + 1, r);  //递归对右子表递归排序
        }
    }

    // 注意: 如果把注释的代码打开,就可以去掉这行a[left] = k;
    private static int partition(int[] a, int left, int right) {
        int k = a[left]; //基准元素
        System.out.println("left=" + left + ", right=" + right + ", k=" + k);
        while (left < right) {  //从表的两端交替地向中间扫描

            while (left < right && a[right] >= k) --right;  //从right 所指位置向前搜索,至多到left+1 位置。将比基准元素小的交换到低端
            if (left < right) {
//                int temp = a[left];
                a[left] = a[right];
//                a[right] = temp;
            }

            while (left < right && a[left] <= k) ++left;
            if (left < right) {
//                int temp = a[right];
                a[right] = a[left];
//                a[left] = temp;
            }

        }
        a[left] = k; //把k填回中间位置
        print(a);
        return left;

    }

    private static void print(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

}

 

 

 

结果输出:

 

排序之前:
49 38 65 97 76 13 27 36 91 

开始排序:
left=0, right=8, k=49
36 38 27 13 49 76 97 65 91 
left=0, right=3, k=36
13 27 36 38 49 76 97 65 91 
left=0, right=1, k=13
13 27 36 38 49 76 97 65 91 
left=5, right=8, k=76
13 27 36 38 49 65 76 97 91 
left=7, right=8, k=97
13 27 36 38 49 65 76 91 97 

排序之后:
13 27 36 38 49 65 76 91 97 

 

动画演示: http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/quick_sort.asp

 

分析:

快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

 

 

 

  • 大小: 42.8 KB
  • 大小: 24.4 KB
分享到:
评论

相关推荐

    《数据结构与算法》-李春葆 实验报告-典型排序算法实践-快速排序

    数据结构与算法 - 快速排序算法实现报告 在数据结构与算法的学习过程中,快速排序算法是一种重要的排序算法,它具有排序速度快、就地排序的优点,但也具有不稳定性。以下是快速排序算法的详细实现报告。 快速排序...

    最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构

    4.快速排序算法 快速排序算法是一种高效的排序算法,它的工作原理是通过选择一个元素作为pivot,然后将数组分为两个部分,以达到排序的目的。快速排序算法的时间复杂度为O(n log n),因此它适合大规模的数据排序。 ...

    蓝桥杯算法讲解-视频与代码

    高级排序问题3-1 归并排序法3-2 归并排序法的实现3-3 归并排序法的优化3-4 自底向上的归并排序算法3-5 快速排序法3-6 随机化快速排序法3-7 双路快速排序法3-8 三路快速排序法3-9 归并排序和快速排序的衍生问题第四章...

    (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题

    (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法...

    各类排序算法整理--C语言描述--本人编写

    各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序

    FPGA并行快速排序算法-位宽可设

    快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别...

    VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序

    本篇文章主要探讨了如何在VC++环境中利用多线程技术来实现三种经典的排序算法:冒泡排序、快速排序和归并排序,并对它们的性能进行了比较。 首先,冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次...

    算法设计与分析-1排序算法性能分析-冒泡/选择/插入/合并/快速排序-pre ppt

    本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...

    排序算法--免费

    本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...

    经典算法的C#源码实现

    经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...

    详解Java常用排序算法-快速排序

    快速排序(Quick Sort)是一种分治思想的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续进行排序,以达到...

    算法设计-快速排序

    算法设计,快速排序的C++实现代码,并测试运行时间

    matlab排序算法实现-合并排序、简单选择排序、快速排序、冒泡排序、直接插入排序

    将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。...本资源通过matlab实现合并排序、简单选择排序、快速排序、冒泡排序、直接插入排序5种常用的排序算法,并部分绘制代表算法原理的动图。

    最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构

    本文将对快速排序、归并排序、堆排序等常见排序算法进行比较和分析,探讨它们的优缺点和适用场景。 首先, let's 看一下这些排序算法的时间复杂度和空间复杂度: | 排序算法 | 平均情况 | 最好情况 | 最坏情况 | ...

    简单排序算法--类的简单使用

    4. **类的实例化与对象的使用**:在主程序中,我们可能需要创建`SortAlgorithms`和`UserInterface`的实例,通过调用类的方法来执行排序算法或控制界面。 5. **成员函数的访问控制**:根据需求,可以使用`public`、`...

    排序算法图解--Document.zip

    4. 快速排序:快速排序由C.A.R. Hoare提出,采用分治策略。选取一个基准值,将数组分成两部分,一部分的所有元素都小于基准,另一部分的元素都大于基准,然后对这两部分递归进行快速排序。快速排序在平均情况下的...

    数据结构--九种排序算法 --排序001.cpp

    此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!

    排序算法实现-支持插值排序+选择排序+冒泡排序-sort.zip

    在实际应用中,通常会选择时间复杂度更低的排序算法,如快速排序、归并排序或堆排序,它们在大多数情况下能提供更好的性能。然而,理解这些基础排序算法有助于我们更好地掌握排序的本质,以及如何根据具体需求选择...

    七大排序算法--c语言是实现

    七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...

    新的快速排序算法 Dual-Pivot QuickSort阅读笔记

    快速排序是一种常用的排序算法,它的效率在许多情况下非常高。其核心思想是选择一个"枢轴"(pivot)元素,然后将数组分为两部分:一部分包含小于枢轴的元素,另一部分包含大于枢轴的元素。递归地对这两部分继续执行...

Global site tag (gtag.js) - Google Analytics