Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

简单排序我们知道,随着输入规模的增大,时间成本将急剧上 升,所以这些基本排序方法不能处理更大规模的问题,接下来我们学习一些高级的排序算法,争取降低算法的时间 复杂度最高阶次幂。

希尔排序

希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为{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
2
3
4
5
6
int h = 1;
//找到分组的步长 数组的长度
while (h < a.length/2){
h = 2 * h + 1;
}
h = h/2;//这是h减少的规则

希尔排序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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package com.bestrookie.sort;

/**
* @author : bestrookie
* @date : 21:47 2021/5/12
*/
public class Shell {
public static void sort(Comparable[] a){
int h = 1;
//找到分组的步长
while (h < a.length/2){
h = 2 * h + 1;
}
while (h >= 1){
//找到待插入元素
for (int i = h; i < a.length; i++) {
//将待插入元素插入到有序数组当中
for (int j = i; j >=h ; j-=h) {
if (generate(a[j-h],a[j])){
swap(a,j-h,j);
}else {
break;
}
}
}
h = h/2;
}

}
public static boolean generate(Comparable v, Comparable w){
return v.compareTo(w) > 0;
}
public static void swap(Comparable[]a ,int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

希尔排序时间复杂度分析

因为增长量h并没有固定的规则,所以无法准确的,所以就不分析了,一般采用事后分析法,对于大数据量的处理往往是选择这种高级排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序 表,称为二路归并。

需求:

排序前:{8,4,5,7,1,3,6,2}

排序后:{1,2,3,4,5,6,7,8}

归并排序原理

1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是 1为止。

2.将相邻的两个子组进行合并成一个有序的大组;(归并的时候进行排序)

3.不断的重复步骤2,直到最终只有一个组为止。

image-20210518213246273

归并排序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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package com.bestrookie.sort;
import java.util.Comparator;

/** 归并排序
* @author : bestrookie
* @date : 11:15 2021/5/18
*/
public class Merge {
/**
* 归并排序所需要的辅助数组
*/
private static Comparable[] assist;
/**
* 对数组a进行排序
* @param a 数组a
*/
public static void sort(Comparable[] a){
//1.初始化辅助数组assist
assist = new Comparable[a.length];
//2.定义一个lo变量和hi变量,分别记录数组中最小的索引和最大的索引
int lo = 0;
int hi = a.length-1;
//3.调用sort的重载方法,对索引lo到索引hi的元素进行排序
sort(a,lo,hi);
}
private static void sort(Comparable[] a ,int lo,int hi){
//先做安全性的检查
if(hi <= lo){
return;
}
//对lo到hi之间的元素进行分组 分为两个组
int mid = lo +(hi-lo)/2;
//分别对每一组进行排序
sort(a, lo, mid);
sort(a,mid+1, hi);
//再把两个组中的数据合并
merge(a, lo, mid, hi);
}

/**
* 归并数组 并在归并的过程中排序
* @param a 数组
* @param lo 最小索引
* @param mid 中间值
* @param hi 最大索引
*/
private static void merge(Comparable[]a,int lo,int mid,int hi){
//1.定义三个指针
int i = lo;
int p1 = lo;
int p2 = mid+1;
//遍历,移动p1指针和p2指针,比较对应索引处的值,找出小的那个,放到辅助数组对应索引处
while (p1 <= mid && p2<=hi){
if (less(a[p1],a[p2])){
assist[i++] = a[p1++];
}else {
assist[i++] = a[p2++];
}
}
//遍历,如果P1处的指针没有走完,那么顺序移动P1指针,把对应元素放到辅助数组对应索引处
while (p1 <= mid){
assist[i++] = a[p1++];
}
//遍历,如果P2处的指针没有走完,那么顺序移动P2指针,把对应元素放到辅助数组对应索引处
while (p2 <= hi){
assist[i++] = a[p2++];
}
//将辅助数组中的元素拷贝到原数组中
for (int index = lo; index<= hi; index++){
a[index] = assist[index];
}

}
private static boolean less(Comparable v , Comparable w){
return v.compareTo(w) < 0;
}
private static void swap(Comparable[]a,int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}

}

归并原理

image-20210518222403512

归并排序时间复杂度分析:

归并排序是分治思想的最典型的例子,上面的算法中,对a[lo…hi]进行排序,先将它分为a[lo…mid]和a[mid+1…hi] 两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果 一个数组不能再被分为两个子数组,那么就会执行merge进行归并,在归并的时候判断元素的大小进行排序。

image-20210518222539217

用树状图来描述归并,如果一个数组有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)

归并排序的缺点:

需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作。

评论