【算法】排序(四)归并排序

上次给大家说了说简单的冒泡排序,这次我们来说一说插入排序

插入排序的做法就像是我们日常生活中玩扑克牌一样,每次抽一张牌,将扑克牌按一定顺序插入手牌中,一步步完成排序

本文将介绍以下内容

排序思想
算法实现(JAVA)
测试阶段
排序过程讲解
算法分析

排序思想

插入排序同样有内循环和外循环,外循环执行n - 1次,内循环负责比较相邻两个数的大小并交换(如果需要)。每次将未排序序列里的第一个数与后一个数比较,如果后者小,就交换二者的位置,并和以排序的序列元素依次比较并交换(如果需要)。

就如同玩扑克牌,每次抽取的一张牌都要与所有手牌一对一比较,并确定最终插入的位置。

算法实现 1. 外循环 public static void insertionSort(int[] a) { int n = a.length; for (int i = 1; i < n; i++) { } }

循环次数为n - 1,否则数组下标越界,下文会说明原因。

2. 内循环 for (int j = i; j > 0 && a[j] < a[j - 1] ; j--) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; }

交换条件为后一项小于前一项,每次都是a[j]与a[j - 1] 比较,所以只能有n - 1 次循环,否则数组下标越界。

所以,插入排序的代码块就是如此了: public static void insertionSort(int[] a) { int n = a.length; for (int i = 1; i < n; i++) { for (int j = i; j > 0 && a[j] < a[j - 1] ; j--) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } } 测试阶段

我们还是用十个随机数字来作为输入:

public static void main(String[] args){ int[] a = new int[10]; for (int i = 0; i < a.length; i++) { a[i] = (int)(Math.random()*100); System.out.print(a[i] + " "); } System.out.println(); insertionSort(a); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } }

随机选取几组结果:

result_1


result_2


result_3

排序过程讲解

我们以result_1的排序结果作为示例来解释一下排序过程:

第一步:74与11比较,交换顺序,已排序序列为[11,74]

第二步:74与99比较,不交换顺序,已排序序列为[11,74,99]

第三步:99与85比较,交换顺序,85与74比较,不交换顺序,已排序序列为[11,74,85,99]

第四步:99与14比较,交换顺序,85与14比较,交换顺序,74与14比较,交换顺序,已排序序列为[11,14,74,85,99]

第五步:99与74比较,交换顺序,85与74比较,交换顺序,74与74比较,不交换顺序,已排序序列为[11,14,74,74,85,99]

第六步:99与24比较,交换顺序,85与24比较,交换顺序,74与24比较,交换顺序,74与24比较,交换顺序,14与24比较,不交换顺序,已排序序列为[11,14,24,74,74,85,99]

第七步:99与90比较,交换顺序,85与90比较,不交换顺序,已排序序列为[11,14,24,74,74,85,90,99]

第八步:99与比54较,交换顺序,85与54比较,交换顺序,74与53比较,交换顺序,74与54比较,交换顺序,24与54比较,不交换顺序,已排序序列为[11,14,24,54,74,74,85,99]

第九步:99与82比较,交换顺序,85与82比较,交换顺序,
74与82比较,不交换顺序,已排序序列为[11,14,24,74,74,85,90,99]

n个元素的数组,经历n - 1次排序,总而言之,如果两元素比较,后者较小,就有可能多次比较,最后插入较前的位置。

算法分析 1. 特点

插入排序对于较为有序(部分有序)的数组时极为高效,因为有序的两个数不满足内循环的循环条件,所以可以直接跳过,极大增加效率。

2. 时间复杂度

最优情况:数组全部按升序排列,只需要进行n - 1次的比较就可完成,不需要交换

最差情况:数组全部按降序排列,需要进行n(n - 1) / 2次比较
(1 + 2 + 3 + ... + n - 1) = n(n - 1) / 2,需要进行n(n - 1) / 2次交换

正常来说,插入排序的时间复杂度为O(n2)

3. 空间复杂度

插入排序需要一个临时变量来交换元素,所以空间复杂度为O(1)

4. 稳定性

插入排序是稳定的,例如result_1中,排序前a[0] = a[5] = 74,且a[0]代表的74在a[5]代表的74之前。在排序过程中,两个74相遇,并没有交换位置,所以插入排序是稳定的

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpdwsj.html