排序--快速排序

1.hoare版本快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程实际上就是走递归实现直到所有元素都排列在相应位置上为止。1.1 初始版本排序我们都通常先实现单趟再实现整体。单趟实现逻辑对上图中给定数组int a[ ]假设数组元素个数为N我们始终假设选择最左侧的值1为key值即基准值那么我们接下来要实现什么根据hoare版本的思想我们要让key左侧的值都是小于a[key],key右侧的值都大于a[key].我们可以这样走定义两个变量int left 0int right N-1由于我们假设最左边为key那么我们就必须让right先走后续给出解释先跟着逻辑顺下去我们让right去找比key值小的数找到就停下来然后left去找比key大的数找到也停下来然后交换交换后继续right先走去找比key小的数找到就停下来找不到就继续往前走left去找比key大的数同理找到就停下来然后与right交换继续重复下去最终right和left相遇且相遇的位置的值一定是比key小的(后续讲解逻辑先关注整体逻辑。相遇后再交换 a[key] 和 a[right],最终 key值左边就是比他小的值右边就是比他大的值代码展示:1.11 要点讲解1.首先是为什么不直接用left 和 right 去移动因为如果直接用它们去移动后续 分左右区间走递归时区间不好分所以用begin和end去移动更优。2.选择左边作为keyi时我们要让end先走那么当右边找小时如图217行如果不加 begin end ,end如果一直找不到比keyi位置上的值小的时end 就会小于begin 这时就不会与begin相遇同理begin向右走时也是这个道理3.递归的结束条件当只有一个数时即begin end时区间为0我们就不需要排序了或者当begin end时即区间不存在时这就是结束条件。1.12 缺陷1.由上可知这种hoare排序的版本其递归思路类似于二叉树的结构。那么就可以联想我们已经学习过的完全二叉树假设数据个数为N可以得出递归的深度大概为 log2N 1), 而每一次递归调用时end和begin 都会相遇那他们递归一次移动次数总和为N故时间复杂度为O(N*logN) -- 一般情况最坏情况那么不妨设想当我们要排升序时给我们一个逆序序列的序列那么这时递归的深度就为N.比如 序列 9 8 7 6 5 4 3 2 1 0 keyi指向9end指向0因为0小于9故end停止begin找大一直找到0即与end相遇然后交换9和0然后 keyi begin 得到 0 8 7 6 5 4 3 2 1 9这时第一趟那此时keyi指向9那么就可以得到区间 下标 [0,8]keyi 9 [10,9],右边区间不存在左边区间继续递归直到[0,0] keyi 1,[2,1];所以递归的深度就为数据个数N。那么这种最坏情况下时间复杂度为O(N^2)2.就是当待排序数量比较少时比如说排序5个数那么需要递归调用5次那么这时用hoare排序其实是不划算的所以我们规定一个最小子区间当排序个数小于这个区间时我们就不用hoare排序而是选择别的排序那么我们可以选择插入排序来解决这种情况1.13 解决办法1.通过上述可知是因为keyi一直选最左边的数导致递归逆序时递归深度为N那我们就可以着手从keyi的取法上来优化快速排序有一种方法叫做三数取中通过三数取中使我们得到的keyi既不是最左边也不是最右边至少是偏向中间的。这样就可以提升效率应对最坏情况的快速排序-----三数取中应对逆序时效率退化为ON^2)的情况代码:2. 小区间优化就是区间比较小时不再递归分割区间排序减少递归。而是选取别的排序方法排序这里我们选取插入排序是最优的插入排序代码1.131 最终优化版本快速排序代码演示1.14 测试效率的代码测试给1000000个数排升序所需要的时间单位为ms毫秒srand函数用于改变种子防止产生假随机数clock函数用于记录调用排序前的时刻和调用排序后的时刻两个时刻相减即得到调用排序消耗的时间