本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及trace图解进行了全面的说明。最后对几种排序算法进行了比较和总结。 写在前面本文所有图片均截图自coursera上普林斯顿的课程 《Algorithms, Part I》 中的Slides 相关命题的证明可参考 《算法(第4版)》 源码可在 官网 下载,也可以在我的github仓库 algorithms-learning 下载,已经使用maven构建 仓库下载: git clone git@github.com:brianway/algorithms-learning.git 基础介绍java: Interface Comparable Java中很多类已经实现了 Comparable total order: Antisymmetry(反对称性): if v ≤ w and w ≤ v, then v = w. Transitivity(传递性): if v ≤ w and w ≤ x, then v ≤ x. Totality: either v ≤ w or w ≤ v or both. 注意: The <= operator for double is not a total order ,violates totality: (Double.NaN <= Double.NaN) is false 通用代码:
思路: 在第i次迭代中,在剩下的(即未排序的)元素中找到最小的元素 将第i个元素与最小的元素交换位置 现象: 设已排序的和未排序的交界处为 ↑,则每次循环, ↑ 从左往右移动一个位置 ↑ 左边的元素(包括↑)固定了,且升序 ↑ 右边的任一元素全部比左边的所有元素都大 步骤: move the pointer to the right indentify index of minimun entry on right exchange into positon java实现:
特点: 运行时间和输入无关,无论输入是已排序,时间复杂度都是O(n^2) 数据移动最少,交换的次数和数组大小是线性关系 insertion sort(插入排序)思路: 在第i次迭代中,将第i个元素与每一个它左边且比它大的的元素交换位置 现象: 设已排序的和未排序的交界处为 ↑,则每次循环, ↑ 从左往右移动一个位置 ↑ 左边的元素(包括↑)且升序,但位置不固定(因为后续可能会因插入而移动) ↑ 右边的元素还不可见 步骤: Move the pointer to the right. Moving from right to left, exchange a with each larger entry to its left. java实现:
inversion(倒置):An inversion is a pair of keys that are out of order 部分有序:An array is partially sorted if the number of inversions is ≤ c N. 特点: 运行时间和输入有关,当输入已排序时,时间复杂度是O(n); For partially-sorted arrays, insertion sort runs in linear time.(交换的次数等于输入中倒置(inversion)的个数) 插入排序适合部分有序数组,也适合小规模数组 ShellSort(希尔排序)希尔排序是基于插入排序的。 思路: Move entries more than one position at a time by h-sorting the array 按照h的步长进行插入排序 现象: 数组中任意间隔为h的元素都是有序的 A g-sorted array remains g-sorted after h-sorting it. 性质: 递增数列一般采用3x+1:1,4,13,40,121,364.....,使用这种递增数列的希尔排序所需的比较次数不会超过N的若干倍乘以递增数列的长度。 最坏情况下,使用3x+1递增数列的希尔排序的比较次数是O(N^(3/2)) java实现:
目标:Rearrange array so that result is a uniformly random permutation shuffle sort思路 为数组的每一个位置生成一个随机实数 排序这个生成的数组 Knuth shuffle demo In iteration i, pick integer r between 0 and i uniformly at random. Swap a and a[r] . correct variant: between i and N – 1 Mergesort--Java sort for objects. Quicksort--Java sort for primitive types. 下面看看这两种排序算法 merge sort(归并排序)思路: Divide array into two halves. Recursivelysort each half. Merge two halves. Abstract in-place merge(原地归并的抽象方法)Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi],replace with sorted subarray a[lo] to a[hi] 步骤: 先将所有元素复制到 aux[] 中,再归并回 a[] 中。 归并时的四个判断: 左半边用尽(取右半边元素) 右半边用尽(取左半边元素) 右半边的当前元素 小于 左半边的当前元素(取右半边的元素) 右半边的当前元素 大于/等于 左半边的当前元素(取左半边的元素) merging java实现:
mergesort java实现:
自顶向下的归并排序的轨迹图 由图可知,原地归并排序的大致趋势是,先局部排序,再扩大规模;先左边排序,再右边排序;每次都是左边一半局部排完且merge了,右边一半才开始从最局部的地方开始排序。 改进 对小规模子数组使用插入排序 测试数组是否已经有序(左边最大<右边最小时,直接返回) 不将元素复制到辅助数组(节省时间而非空间) Bottom-up mergesort(自底向上的归并排序)思路: 先归并微型数组,从两两归并开始(每个元素理解为大小为1的数组) 重复上述步骤,逐步扩大归并的规模,2,4,8..... java实现:
自底向上的归并排序的轨迹图 由图可知,自底向上归并排序的大致趋势是,先局部排序,逐步扩大到全局排序;步调均匀,稳步扩大 quicksort思路: Shufflethe array. Partition(切分)so that, for some j entry a[j] is in place no larger entry to the left of j no smaller entry to the right of j Sorteach piece recursively. 其中很重要的一步就是 Partition(切分) ,这个过程使得满足以下三个条件: 对于某个j,a[j]已经排定; a[lo]到a[j-1]中的所有元素都不大于a[j]; a[j+1]到a[hi]中的所有元素都不小于a[j]; partition java实现
快排java实现:
快排的轨迹图 由图可知,和归并排序不同,快排的大致趋势是,先全局大体有个走势——左边比右边小,逐步细化到局部;也是先左后右;局部完成时全部排序也就完成了。 一些实现的细节: 原地切分:不使用辅助数组 别越界:测试条件(j == lo)是冗余的(a[lo]不可能比自己小); 保持随机性:初始时的随机打乱跟重要 终止循环 处理切分元素值有重复的情况:这里可能出问题 性质: 快排是in-place的 快排不稳定 改进 对小规模子数组使用插入排序 三取样切分 三向切分的快速排序思路: Let v be partitioning item a[lo]. Scan i from left to right. (a < v): exchange a[lt] with a; increment both lt and i (a > v): exchange a[gt] with a; decrement gt (a == v): increment i 主要是通过增加一个指针来实现的。普通的快拍只有lo和high两个指针,故只能记录 大于 (high右边)和 小于 (lo左边)两个区间, 等于 只能并入其中一个;这里增加了使用了lt,i,gt三个指针,从而达到记录 大于 (gt右边)、 小于 (lt左边)和 等于 (lt和i之间)三个区间。 三切分的示意图 三向切分的java实现:
思路: Create max-heap with all N keys. Repeatedly remove the maximum key. swim:由下至上的堆有序化 sink:由上至下的对有序化 堆排序主要分为两个阶段: 堆的构造 下沉排序 java实现如下:
堆排序的轨迹图 由图看出,堆排序的趋势是,堆构造阶段,大致是降序的走势,到了下沉阶段,从右到左(或者说从后往前)逐步有序 Significance: In-place sorting algorithm with N log N worst-case. Mergesort: no, linear extra space. Quicksort: no, quadratic time in worst case 缺点 Inner loop longer than quicksort’s. Makes poor use of cache memory. Not stable(不稳定) 总结和比较排序算法总结表 最好情况和最坏情况:参见上面的表格 关于稳定性: 稳定性,插入排序,归并排序 不稳定:选择排序,快排,希尔排序,堆排序 原因: Long-distance exchange 关于额外空间:除了归并排序需要线性的额外空间,其他都是in-place的 命题对于长度为N的数组,选择排序需要N^2/2次比较和N次交换(pf见P156) 对于随机排列的长度为N的且主键不重复的数组(pf见P157) 平均情况下插入排序需要~N^2/4次比较和~N^2/4次交换 最坏情况下需要~N^2/2次比较和~N^2/2次交换, 最好情况下需要N-1次比较和0次交换。 Mergesort uses at most N lg N compares and 6 N lg N array accesses to sort any array of size N. (pf见P173) Mergesort uses extra space proportional to N.(The array aux[] needs to be of size N for the last merge.) Any compare-based sorting algorithm must use at least lg ( N ! ) ~ N lg N compares in the worst-case.(pf见P177) 长度为N的无重复数组排序,快速排序平均需要~2N ln N 次比较(以及1/6即1/3 N ln N的交换) 最多需要约N^2/2次比较 最少需要~N lg N 次比较 用下沉操作由N个元素构造堆只需少于2N次比较以及少于N次交换(pf见P206) 将N个元素排序,堆排序只需少于(2NlgN+2N)次比较以及一半次数的交换(pf见P208) |
|
来自: melodyjian > 《java》