DomBro Studio

几种基本排序

2018/03/19

前言

大二的时候,一位学长跟我说他找的实习笔试就考了几个排序。当时想,嗨一个排序有什么难的。昨个打算靠自己的记忆 “背”出几个排序,然而对着纸笔看了半天也就只有几个名词能想的起来,冒泡、插入、快排…至于怎么排的全都忘了。在嫌弃自己记忆力的同时,也知道在当初学的时候就没有好好理解每种排序的思想,这东西就不是死记硬背可以吃的透的。好好的看了一天书,总结了七中常见的排序方法,日后一定勤于钻研,每日默写2333…

约定

往下看以前约法几章

  • 下面的几种排序都是属于内部排序,即适用数据相对较小的数组。
  • 规定 N 代表数组的规模。
  • 数组的类型默认使用较好理解的整型。
  • 我不想在排序这种基本算法博客上画太多的图,除了比较难理解的排序,不会有太多图片演示。毕竟程序员还是要练习一下空间想象力的。主要也是懒..

插入排序

首先说插入排序,为什么上来说插入排序呢?因为我喜欢…
1) 插入排序是由 N-1 趟排序组成的,如果用 p 表示趟数,则一共从 p=1 趟到 p = N-1 趟。
2) 插入排序每要做的就是,在第 p 趟,将位置 p 上的元素向左移动(你也可以理解为向左插入),直到前 p+1 个元素是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**插入排序算法思想:
/1.要进行N-1(N为数组规模)趟排序排序 。
/2.对于 p=1 到 p = N-1趟,每趟排序要确保 array[0] 到 array[p] 变为有序。(p为元素位置索引)
/3.每趟排序从位置 p 开始,将array[p]向左移动,直到寻找 array[p] 的合适位置,即前 p+1 个元素为有序的。
*/
public static void insertionSort(int[] array){
int j;
//要有
for (int p = 1; p < array.length; p++){
//temp 用来保存 array[p] 的值
int temp = array[p];
//每一趟的排序算法
for (j = p; j > 0 && temp < array[j-1];j--){
array[j] = array[j-1];
}
array[j] = temp;
}
}

该算法之所以可行,是因为下一趟趟排序前,前面的元素都已经有序,你只需要在每趟排序为 位置p 上的元素找到合适位置即可,就像将该元素插入到前 p+1 个元素中。插入已排序的平均时间复杂度是 O(N2)。

冒泡排序

冒泡排序真的不想再多说了,冒泡排序一共要进行 N 趟排序,每趟排序会把本趟找到的最大的值放到数组的末尾。就像气泡上升一样一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 冒泡排序算法思路
* 1.是很简单且效率很低的排序
* 2.一共要进行N趟排序
* 3.每趟排序比较相邻元素大小,发现前一个数毕后一个数大交换,确保每趟排序将最大值放至末尾
*/
public static void bubbleSort(int[] array){
//一共进行N趟排序
for (int i = 0;i < array.length-1;i++){
//内层循环同时决定了比较的下界,即每趟排序的最大值会是上一趟排序最大值的上一个元素
for (int j = 0;j < array.length - i;j++){
//发现逆序就交换
if (j+1 < array.length && array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}

很明显冒泡排序的平均时间复杂度是 O(N2)。

选择排序

选择排序也要进行 N 趟排序,思路是每趟排序从数组中随机找一个元素chosen和其他元素比较,找出比chosen元素小的就用该较小值代替,这样每趟排序都会找出该趟的最小值,放到前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 选择排序算法思想:
* 1.该算需要进行N趟排序
* 2.每趟排序选择出一个元素,比较数组中比该元素小且最小的元素,
* 即每趟选择都会挑选出剩余元素中最小的。这点和冒泡排序正好相反。
*/
public static void selectionSort(int[] array){

for (int i = 0; i < array.length; i++) {
int chosen = i;
for (int j = i+1;j < array.length;j++){
if (array[j] < array[chosen]){
chosen = j;
}
}
if (i != chosen){
int temp = array[chosen];
array[chosen] = array[i];
array[i] = temp;
}
}
}

很明显选择排序的平均时间复杂度是 O(N2)。

小结

我们看到无论插入排序、选择排序、冒泡排序的时间复杂度都是可怕的 O(N2) 。这是为什么呢?答案很简单上面的三种排序都交换了相邻元素。

定理:通过交换相邻元素进行排序的人和算法平均时间都需要 Ω(N2)。

由此需要找到另外的排序方案,即可以对相对距离较远的元素进行比较的排序。

希尔排序

希尔排序通过比较一定间隔的元素来工作,各趟比较所用的距离随算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。

  • 增量序列

希尔排序是使用一个增量序列 h1,h2 h3…hk 叫做增量序列。只要 h1 = 1 ,任何增量序列都是可行的,不过合理的选择增量序列会影响希尔排序的效率。

希尔排序比较的趟数取决于增量序列,有几个增量就会比较几趟,在使用增量 hk 的一趟排序后,对于每一个i都会有a[i] <= a[i+hk]。这句话的意思是数组中只要相隔 hk 的元素就会被比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 希尔排序算法思想:
* 1.通过比较一定间隔的元素进行工作。
* 2.比较的间隔按照一定增量序列 h1,h2...ht 决定。
* 3.各趟比较的间隔随算法的进行而减小,直到只比较相邻元素的最后一趟(即增量为1)。
* 4.每趟比较下来,都会得到 a[i] <= a[i+ht]。
* 5.希尔排序的效率和增量的选择有很大的关系
*/
public static void hellSort(int[] array){
int j;
int gap;
//gap即增量,这里定义增量
for (gap = array.length/2; gap > 0;gap /= 2 );
//每一趟的排序算法
for (int i = gap; i < array.length; i++){
int temp = array[i];
//比较增量内的两个元素,必要时交换
for (j = i; j >= gap && temp < array[j - gap] ;j -= gap){
array[j] = array[j-gap];
}
array[j] = temp;
}
}

你会注意到增量的选择是取 length/2 ,而后的增量则是上一增量 除2 得到,这样选是一个比较这种的办法,也是算法发明者希尔他老人家推荐的。希尔排序的最差效率是O(N2),但其平均效率性能在实践中是完全可以接受的。

堆排序

堆排序是一个很有意思的排序,它用到了所谓的变治法,给出了目前为止最佳大O时间,O (NlogN)。那么它是如何变治的呢?这是我非常喜欢的一个算法。由于之前写过一个关于变治法堆排序的博客,不过我真的是太喜欢这个算法了,再唠叨一遍。

  • 堆与大顶堆

堆 : 就是逻辑上的二叉树,就是把一个数组想象成二叉树,但数据结构还是线性的。索引为 i 的父节点元素的左孩子和右孩子分别是索引为 2i+1 和 2i+2 索引的元素。
大顶堆 : 大顶堆就是堆中的节点都不小于其孩子节点,也就是说大顶堆中的根节点(索引为0的元素)是最大的。

  • 算法思路

根据上面所说大顶堆的根节点是最大的,如果我们每次都能取到大顶堆的最大元素…整个排序就迎刃而解了!
1.首先将数组初始化成堆,这样数组的首元素就变成了最大的。
2.将数组首元素和尾元素交换位置。
3.将除目前尾元素的数组堆化(即不在考虑当前堆中最后一个元素),重复 2 、 3 步骤,知道堆中只剩下一个元素。

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
/**
* 堆排序算法思想
* 1.首先将规模为 n的数组 array 变成大顶推。
* 2.其次将该大顶堆中最后一个元素 array[n-1] 与一个元素 array[0] 交换位置,得到的 array[n-1] 便是最大元素。
* 3.在调整剩余元素为大顶堆,再将剩余元素最后一个与第一个元素交换,直到堆的大小为 1 时。
*/
public static void heapsort(int[] array) {
for (int i = array.length / 2; i > 0; i--) {
buildHeap(array, i, array.length);
}
for (int i = array.length - 1; i > 0; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
buildHeap(array, 0, i);
}
}

/**
* 堆排序的堆化函数
*
* @param array
* @param parent
* @param length
*/
public static void buildHeap(int[] array, int parent, int length) {
int child;
int temp;
for (temp = array[parent]; liftChild(parent) < length; parent = child) {
System.out.println(temp + ",");
child = liftChild(parent);
//挑选其右孩子
if (child != length - 1 && array[child + 1] > array[child]) {
child = child + 1;
}
if (temp < array[child]) {
array[parent] = array[child];
} else {
break;
}
}
array[parent] = temp;
}

/**
* 堆排序获取一个节点的左孩子在数组中的位置
*/
public static int liftChild(int parent) {
return 2 * parent + 1;
}

归并排序

归并排序也是一个很好玩的排序,使用了递归的方式。归并排序最有特点的就是使用了分治法种思想,将原数组进行合并排序,很多递归程序都使用了

  • 合并排序

合并排序就是将两个有序数组进行排序。排序的方式很简单,需要利用一个中间数组。
1.将两个有序数组A、B的中的元素进行比较,若 A[0] < B[0] 则把 A[0] 放入 中间数组中,比较 A[1] 和 B[0],如果一个数组比较完后另一个数组还有剩余则将该数组剩余元素放入中间数组中,这样中间数组就是一个有序的数组啦。

由上面的图可以看到,合并两个有序的数组时间是线性的,因为最多进行 N-1 次比较。

  • 算法思路

根据合并排序,使原数组变为有序的方法就是 原数组变为两个有序数组,在使用合并排序,可是要怎样使两个数组变为有序呢?你既然可以想出原数组变为有序的方法,那一半的怎么可能不会?递归呀!!

1.递归求得前后两部分元素的有序数组。
2.前后两部分数组进行合并排序。就是这么简单。

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
/**
* 归并排序算法思想:
* 1.利用递归将数组前半部分和后半部分数据各自归并排序。
* 2.再将排好序的两部分数组合并排序。
* 3.算法属于分治策略,他将问题分成小为题然后递归求解。
* 4.归并排序是所有流行比较里面比较次数最少的。
*/
/**
* @param array 传入数组
*/
public static void mergeShort(int[] array) {
int[] tempArray = new int[array.length];
mergeShort(array, tempArray, 0, array.length - 1);
}

/**
* @param array 传入要排序的数组
* @param tempArray 用来保存将前后两部分数组合并后的数组
* @param left array 数组的首个元素索引
* @param right array 数组最后一个元素索引
*/
public static void mergeShort(int[] array, int[] tempArray, int left, int right) {
//递归的出口是数组元素大于一
if (left < right) {
int center = (left + right) / 2;
//首先对前后两半数组分别排序,使其成为
mergeShort(array, tempArray, left, center);
mergeShort(array, tempArray, center + 1, right);
merge(array, tempArray, left, center + 1, right);
}
}

/**
* 该方法为合并排序,合并排序用来对两个有序数组进行排序,本例子中该有序数组是传入数组的前后两半部分。
*
* @param array 传入的要合并排序的数组
* @param tempArray 用来保存两数组排序后元素的数组
* @param leftPos 记录前一半数组元素首个元素位置
* @param rightPos 记录后一半数组元素首个元素位置
* @param rightEnd 后一半数组最后元素索引
*/
public static void merge(int[] array, int[] tempArray, int leftPos, int rightPos, int rightEnd) {

int liftEnd = rightPos - 1;
//tempArray首个元素索引,用于记录当前位置索引
int tempPos = leftPos;
//比较两半部分数组中元素大小,将小的放入tempArray数组中,直到其中一个数组元素都比较完毕
while (leftPos <= liftEnd && rightPos <= rightEnd) {
if (array[leftPos] <= array[rightPos]) {
tempArray[tempPos++] = array[leftPos++];
} else {
tempArray[tempPos++] = array[rightPos++];
}
}
//当发现数组没有比较完,说明该数组剩下元素可以直接放入tempArray中
while (leftPos <= liftEnd) {
tempArray[tempPos++] = array[leftPos++];
}
while (rightPos <= rightEnd) {
tempArray[tempPos++] = array[rightPos++];
}
//将排序结果放回到原数组中
for (int i = 0; i < array.length; i++, rightEnd--) {
array[rightEnd] = tempArray[rightEnd];
}
}
  • 算法效率

归并排序的运行时间是 O(NlogN),但他有一个明显的问题,即合并两个已排序表用到的附加线性内存。但是归并排序是流行的排序算法中最少比较次数的,因此是使用 Java 语言通用的排序算法中上好的选择。事实上,他就是标准Java类库泛型排序使用的默认排序。

快速排序

快速排序同样用到了递归,我认为他是对归并排序的一种改进,因为归并排序用到了中间数组,产生了多余的空间。快速排序并没有用到中间数组,他的思路同样清晰:

1.在一个数组中选择一个元素叫他枢纽,对数组元素进行比较,前面的元素都比枢纽小,后面的元素都比枢纽大。
2.这样数组就变成了三部分,大数集,小数集,还有枢纽。
3.对大数集和小数集递归使用快速排序。

  • 枢纽元素的选取

通过图片你会发现枢纽的选取是一门学问。虽然快速排序中选取那个元素作为枢纽都会完成工作,但是很明显有些选择更优。推荐一种选取枢纽的方法 —— 三数中值分割法。这里说的三数分别是数组首元素 array[0] 、中间元素 array[length/2]、数组尾元素 array[length-1] 的中值。

  • 分割策略

快速排序再找到枢纽后会对数组作一个分割。分割要做的就是把所有小的元素移到数组的左边而把所有大的元素移到数组的右边。当然小和大是相对于枢纽而言。
1.首先要将枢纽选取时的三个元素放在合适位置,最大的放在数组末尾,最小的放在数组开头,而枢纽则放在尾元素的前一位(这样保证比枢纽大的元素在枢纽右侧)。
2.有两个指针i、j,i 从首元素下一元素开始,只要array[i] < 枢纽则 i 向右移 ; j 从枢纽前一个元素开始,只要array[j] > 枢纽则 j 向左移,移动直到 i 和 j 交错,即 j < i 指针移动停止。

这个例子举得不是特别好…有意思的是快速排序平均效率虽然为O(NlogN),但如果数组规模不到20,那么它的效率还没有插入排序好,所以快速排序对规模较大的数组有较好的效率。

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
/**
* 快速排序算法思想(较难理解):
* 1.在传入数组中找出一个枢纽元素(利用三数中值法),使用分割法将数组分为两部分,比该枢纽大的元素部分,个比该枢纽元素小的部分。
* 2.在对 1 中两个部分数组进行递归的快排序。
* 3.对数组不足20的数组使用插入排序,因为数组规模较小时使用插入排序效率更高。
*/
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}

/**
* @param array 传入数组
* @param left 首元素索引
* @param right 尾元素素银
*/
private static void quickSort(int[] array, int left, int right) {

if (right - left > 20) {
//获取枢纽元素
int pivot = median3(array, left, right);
int i = left + 1;
int j = right - 2;
//使用分割法
//1.i 从 第二个元素 开始向右移,j 从 枢纽元素前一个元素向左移,当 i 指向的元素比枢纽元素大时 i 停止移动;
//当 j 指向的元素比枢纽元素小时 j 停止移动,
//2.当 i 和 j都停止移动时交换 i 和 j 所 对指向的元素。该过程直到 i 大于 j 为止,此时保证所有比枢纽元素小的元素都在 i 的左边。
//3.最后一步将枢纽元素和i所指的元素交换
for (; ; ) {
while (array[i] < array[pivot]) i++;
while (array[j] > array[pivot]) j--;
if (i < j) {
swapReferences(array, i, j);
} else {
break;
}
}
swapReferences(array, i, right - 1);
//递归的将比枢纽元素小的数组和比枢纽元素大的数组进 快速排序
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
} else {
//如果数组规模较小则使用插入排序
insertionSort(array);
}
}

//交换数组中两元素位置方法,没什么技高含量
private static void swapReferences(int[] array, int item1, int item2) {
int temp = array[item1];
array[item1] = array[item2];
array[item2] = temp;
}
  • 算法效率

上面是介绍了快速排序的平均大O时间是 O(NlogN) ,但是当数组规模不大时,建议使用插入排序。实际上该算法之所以快是因为非常精炼和高度优化的内部循环。在Java和C++中快速排序是基本类型的标准库排序。

总结

事实上每种排序都有自己的合适使用场景,比如归并并排序不适合规模较大的数组排序,而给出的时间复杂度也只是一个平均值。算法这东西重在理解和自身的感受,我觉得写完这篇笔记后对这几种简单排序又有了新的理解。

CATALOG
  1. 1. 前言
  2. 2. 约定
  3. 3. 插入排序
  4. 4. 冒泡排序
  5. 5. 选择排序
  6. 6. 小结
  7. 7. 希尔排序
  8. 8. 堆排序
  9. 9. 归并排序
  10. 10. 快速排序
  11. 11. 总结