排序高级之交换排序_快速排序

2024-08-22 23:32
文章标签 快速 排序 交换 高级

本文主要是介绍排序高级之交换排序_快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。


快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

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

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。


优化的排序算法

快速排序是二叉查找树(二叉查找树)的一个空间优化版本。不是循序地把数据项插入到一个明确的树中,而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数,但是顺序不同。对于排序算法的稳定性指标,原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。

快速排序的最直接竞争者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快,除了introsort变化版本外,仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的,那么直接地使用堆排序比等待 introsort 再切换到它还要快。堆排序也拥有重要的特点,仅使用固定额外的空间(堆排序是原地排序),而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而,堆排序需要有效率的随机存取才能变成可行。

快速排序也与归并排序(Mergesort)竞争,这是另外一种递归排序算法,但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序,归并排序是一个稳定排序,且可以轻易地被采用在链表(linked list)和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串行上,但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点,是在最佳情况下需要Ω(n)额外的空间。


正规的分析

从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算,数组的元素都会在每次循环中走访过一次,使用O(n)的时间。在使用结合(concatenation)的版本中,这项运算也是O(n)。

在最好的情况,每次我们运行一次分区,我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此,在到达大小为一的数列前,我们只要作 log n 次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中,不会处理到原来数列的相同部份;因此,程序调用的每一层次结构总共全部仅需要O(n)的时间(每个调用有某些共同的额外耗费,但是因为在每一层次结构仅仅只有O(n)个调用,这些被归纳在O(n)系数中)。结果是这个算法仅需使用O(n log n)时间。

另外一个方法是为T(n)设立一个递归关系式,也就是需要排序大小为n的数列所需要的时间。在最好的情况下,因为一个单独的快速排序调用牵涉了O(n)的工作,加上对n/2大小之数列的两个递归调用,这个关系式可以是:

T( n) = O( n) + 2T( n/2)

解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。

事实上,并不需要把数列如此精确地分区;即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边,调用的深度仍然限制在 100log n,所以全部运行时间依然是O(n log n)。

然而,在最坏的情况是,两子数列拥有大各为 1 和 n-1,且调用树(call tree)变成为一个 n 个嵌套(nested)调用的线性连串(chain)。第 i 次调用作了O(n-i)的工作量,且\sum_{i=0}^n (n-i) = O(n^2)递归关系式为:

T( n) = O( n) + T(1) + T( n - 1) = O( n) + T( n - 1)

这与插入排序和选择排序有相同的关系式,以及它被解为T(n) = O(n2)。


乱数快速排序的期望复杂度

乱数快速排序有一个值得注意的特性,在任意输入数据的状况下,它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择?

假设我们排序一个数列,然后把它分为四个部份。在中央的两个部份将会包含最好的基准值;他们的每一个至少都会比25%的元素大,且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素,在到达大小为1的数列前,我们可能最多仅需要把数列分区2log2 n次,产生一个 O(nlogn)算法。

不幸地,乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币,一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间,平均来说只需要 2k 次翻动。且在 100k 次翻动中得不到 k 次人头那面的机会,是像天文数字一样的非常小。借由同样的论证,快速排序的递归平均只要2(2log2 n)的调用深度就会终止。但是如果它的平均调用深度是O(log n)且每一阶的调用树状过程最多有 n 个元素,则全部完成的工作量平均上是乘积,也就是 O(n log n)。

平均复杂度

即使如果我们无法随机地选择基准数值,对于它的输入之所有可能排列,快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来,除以n这个因子,相当于从输入之中选择一个随机的排列。当我们这样作,基准值本质上就是随机的,导致这个算法与乱数快速排序有一样的运行时间。

更精确地说,对于输入顺序之所有排列情形的平均比较次数,可以借由解出这个递归关系式可以精确地算出来。

C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = 2n \ln n = 1.39n \log_2 n.

在这里,n-1 是分区所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方,总和就是所有可能分区的平均。

这个意思是,平均上快速排序比理想的比较次数,也就是最好情况下,只大约比较糟39%。这意味着,它比最坏情况较接近最好情况。这个快速的平均运行时间,是快速排序比其他排序算法有实际的优势之另一个原因。

空间复杂度

被快速排序所使用的空间,依照使用的版本而定。使用原地(in-place)分区的快速排序版本,在任何递归调用前,仅会使用固定的額外空間。然而,如果需要产生O(log n)嵌套递归调用,它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用,所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用,因此需要O(n)的空间。

然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列,我们必须要记住我们的变量像是leftright,不再被认为是占据固定的空间;也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量,实际上快速排序在最好跟平均的情况下,需要O(log2 n)空间的比特数,以及最坏情况下O(n log n)的空间。然而,这并不会太可怕,因为如果一个数列大部份都是不同的元素,那么数列本身也会占据O(n log n)的空间字节。

非原地版本的快速排序,在它的任何递归调用前需要使用O(n)空间。在最好的情况下,它的空间仍然限制在O(n),因为递归的每一阶中,使用与上一次所使用最多空间的一半,且

\sum_{i=0}^{\infty} \frac{n}{2^i} = 2n.

它的最坏情况是很恐怖的,需要

\sum_{i=0}^n (n-i+1) = \Theta (n^2)

空间,远比数列本身还多。如果这些数列元素本身自己不是固定的大小,这个问题会变得更大;举例来说,如果数列元素的大部份都是不同的,每一个将会需要大约O(log n)为原来存储,导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。


最差时间复杂度\Theta(n^2)
最优时间复杂度\Theta(n\log n)
平均时间复杂度\Theta(n\log n)
最差空间复杂度根据实现的方式不同而不同


快速排序动态图:



实现代码:

package com.baobaotao.test;
/*** 排序研究* @author benjamin(吴海旭)* @email benjaminwhx@sina.com / 449261417@qq.com**/
public class Sort {/*** 快速排序实现* @param array* @param low* @param high*/public static void quickSort(int[] array, int low, int high) {if(low < high) {int pivot = partition(array, low, high);quickSort(array, low, pivot - 1);quickSort(array, pivot + 1, high);}}/*** 根据传入的最低位和最高位分割数组* @param array 待排序数组* @param low	数组下标下界* @param high	数组上标上界* @return pivot*/public static int partition(int[] array, int low, int high) {//第一个元素所在位置int p_pos = low ;//采用第一个元素为轴int pivot = array[p_pos] ;for (int i = low + 1; i <= high; i++) {if (array[i] < pivot) {            p_pos++;swap(array, p_pos, i); }}swap(array, low, p_pos);return p_pos;}/*** 按从小到大的顺序交换数组* @param a 传入的数组* @param b 传入的要交换的数b* @param c	传入的要交换的数c*/public static void swap(int[] a, int b, int c) {if(b == c) return ;int temp = a[b] ;a[b] = a[c] ;a[c] = temp ; }/*** 打印数组* @param array*/public static void printArr(int[] array) {for(int c : array) {System.out.print(c + " ");}System.out.println();}public static void main(String[] args) {int[] number={11,95,45,15,78,84,51,24,12} ;quickSort(number, 0, number.length-1) ;printArr(number) ;}
}

转载请标注:http://blog.csdn.net/benjamin_whx/article/details/42460883

这篇关于排序高级之交换排序_快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1097713

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图