简单排序我们知道,随着输入规模的增大,时间成本将急剧上 升,所以这些基本排序方法不能处理更大规模的问题,接下来我们学习一些高级的排序算法,争取降低算法的时间 复杂度最高阶次幂。
希尔排序
希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为{2,5,7,9,10},未排序的分组 元素为{1,8},那么下一个待插入元素为1,我们需要拿着1从后往前,依次和10,9,7,5,2进行交换位置,才能完成真 正的插入,每次交换只能和相邻的元素交换位置。那如果我们要提高效率,直观的想法就是一次交换,能把1放到 更前面的位置,比如一次交换就能把1插到2和5之间,这样一次交换1就向前走了5个位置,可以减少交换的次数, 这样的需求如何实现呢?接下来我们来看看希尔排序的原理。
需求:
排序前:{9,1,2,5,7,4,8,6,3,5}
排序后:{1,2,3,4,5,5,6,7,8,9}
希尔排序原理
1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组;
2.对分好组的每一组数据完成插入排序;
3.减小增长量,最小减为1,重复第二步操作。
增长量h的确定:增长量h的值每一固定的规则,我们这里采用以下规则(上面的例子只是为了更好的展示而已):
1 | int h = 1; |
希尔排序Api设计
类名 | Shell |
---|---|
构造方法 | Shell():创建Shell对象 |
成员方法 | 1.public static void sort(Comparable[] a):对数组内的元素进行排 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void swap(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值 |
希尔排序代码实现
1 | package com.bestrookie.sort; |
希尔排序时间复杂度分析
因为增长量h并没有固定的规则,所以无法准确的,所以就不分析了,一般采用事后分析法,对于大数据量的处理往往是选择这种高级排序
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序 表,称为二路归并。
需求:
排序前:{8,4,5,7,1,3,6,2}
排序后:{1,2,3,4,5,6,7,8}
归并排序原理
1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是 1为止。
2.将相邻的两个子组进行合并成一个有序的大组;(归并的时候进行排序)
3.不断的重复步骤2,直到最终只有一个组为止。
归并排序Api设计
类名 | Merge |
---|---|
构 造 方 法 | Merge():创建Merge对象 |
成 员 方 法 | 1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static void sort(Comparable[] a, int lo, int hi):对数组a中从索引lo到索引hi之间的元素进 行排序 3.private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到所以mid为一个子 组,从索引mid+1到索引hi为另一个子组,把数组a中的这两个子组的数据合并成一个有序的大组(从 索引lo到索引hi) 4.private static boolean less(Comparable v,Comparable w):判断v是否小于w 5.private static void swap(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值 |
成 员 变 量 | 1.private static Comparable[] assist:完成归并操作需要的辅助数组 |
代码实现
1 | package com.bestrookie.sort; |
归并原理
归并排序时间复杂度分析:
归并排序是分治思想的最典型的例子,上面的算法中,对a[lo…hi]进行排序,先将它分为a[lo…mid]和a[mid+1…hi] 两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果 一个数组不能再被分为两个子数组,那么就会执行merge进行归并,在归并的时候判断元素的大小进行排序。
用树状图来描述归并,如果一个数组有8个元素,那么它将每次除以2来找最小的子数组,共拆log8次,值为3,所以树共有3层那么自顶向下第k层有2^k个子数组,每个数组的长度为2^(3-k),归并最多需要2^(3-k)次比较。因此每层 的比较次数为 2^k * 2^(3-k)=2^3,那么3层总共为 3*2^3。
假设元素的个数为n,那么使用归并排序拆分的次数为log2(n),所以共log2(n)层,那么使用log2(n)替换上面3*2^3中 的3这个层数
最终得出的归并排序的时间复杂度为:log2(n)2^(log2(n))=log2(n)n,根据大O推导法则,忽略底 数,最终归并排序的时间复杂度为O(nlogn)
归并排序的缺点:
需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作。