基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
- 初始状态:无序区为R[1..n],有序区为空。
- 第1趟排序:在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1] 交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
- ……
- 第i趟排序:第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
//Java 代码public class StraightInsertionSorter{ public void sort(int[] arr) { int tmp; for(int i=1;i=0 && tmp =左侧有序区最大的arr[i-1],或者经过扫描移动后,找到一个比arr[i]小的元素 // 将右侧无序区第一个元素tmp = arr[i]放到正确的位置上 arr[j+1]=tmp; } } }}
排序过程
直接插入排序的执行过程,如下所示:
- 初始化无序区和有序区:数组第一个元素为有序区,其余的元素作为无序区。
- 遍历无序区,将无序区的每一个元素插入到有序区正确的位置上。具体执行过程为: 每次取出无序区的第一个元素,如果该元素tmp大于有序区最后一个元素,不做任何操作; 如果tmp小于有序区最后一个元素,说明需要插入到有序区最后一个元素前面的某个位置,从后往前扫描有序区,如果有序区元素大于tmp,将有序区元素后移 (第一次后移:tmp小于有序区最大的元素,有序区最大的元素后移覆盖无序区第一个元素,而无序区第一个元素的已经拷贝到tmp中;第二次后移:tmp小 于有序区从后向前第二个的元素,有序区从后向前第二个元素后移覆盖有序区最大元素的位置,而有序区最后一个元素已经拷贝到无序区第一个元素的位置上;以此 类推),直到找到一个元素比tmp小的元素(如果没有找到,就插入到有序区首位置),有序区后移操作停止。
- 接着,将tmp插入到:从有序区由前至后找到的第一个比tmp小的元素的后面即可。此时,有序区增加一个元素,无序区减少一个元素,直到无序区元素个数为0,排序结束。
下面,通过实例来演示执行直接插入排序的过程,假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20,则执行排序过程如下所示:
初始有序区为{94},无序区为{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。
对于array[1] = 12(无序区第一个元素):临时拷贝tmp = array[1] = 12,tmp = 12小于有序区{94}最后一个元素(94),因为有序区只有一个元素,所以将tmp插入到有序区首位置,此时,有序区为{12,94},无序区为{34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。 对于array[2] = 34(无序区第一个元素):临时拷贝tmp = array[2] = 34,tmp = 34小于有序区{12,94}最后一个元素(94),将94后移覆盖array[2],亦即:array[2] = 94;继续将tmp = 34与有序区{12,94}从后向前第二个元素比较,tmp = 34 > 12,则直接将tmp = 34插入到12后面的位置。此时,有序区为{12,34,94},无序区为{76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。 对于array[3] = 76(无序区第一个元素):临时拷贝tmp = array[3] = 76,tmp = 76小于有序区{12,34,94}最后一个元素(94),将94后移覆盖array[3],亦即:array[3] = 94;继续将tmp = 76与有序区{12,34,94}从后向前第二个元素比较,tmp = 76 > 34,则直接将tmp = 76插入到34后面的位置。此时,有序区为{12,34,76,94},无序区为{26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。……
依此类推执行,直到无序区没有元素为止,则有序区即为排序后的数组。算法分析
时间复杂度
最好情况:有序
通过直接插入排序的执行过程可以看到,如果待排序数组恰好为有序,则每次从大小为n-1的无序区数组取出一个元素,和有序区最后一个元素比较,一定是比最后一个元素大,需要插入到有序区最后一个元素的后面,也就是原地插入。
可见,比较次数为n-1次,数组元素移动次数为0次。 最坏情况:逆序每次从无序区取出第一个元素,首先需要与有序区最后一个元素比较一次,然后继续从有序区的最后一个元素比较,直到比较到有序区第一个元素,然后插入到有序区首位置。
每次从无序区取出第一个元素,移动放到拷贝tmp中,然后再将tmp与有序区元素比较,这个比较过程一共移动的次数为:有序区数组大小,最后还要将拷贝tmp移动插入到有序区的位置上。 在这个过程中: 有序区数组大小为1时,比较2次,移动3次; 有序区数组大小为2时,比较3次,移动4次; …… 有序区数组大小为n-1时,比较n次,移动n+1次。 可见: 比较的次数为:2+3+……+n = (n+2)(n-1)/2 移动的此时为:3+4+……+n+1 = (n+4)(n-1)/2通过上面两种情况的分析,直接插入排序的时间复杂度为O(n2)。
空间复杂度
在直接插入排序的过程中,只用到一个tmp临时存放待插入元素,因此空间复杂度为O(1)。
排序稳定性
通过上面的例子来看:
当有序区为{0,9,12,26,34,37,55,76,94},无序区为{76,37,5,68,83,90,37,12,65,76,49}的时候,执行下一趟直接插入排序: 对于array[9] = 76(无序区第一个元素): 临时拷贝tmp = array[9] = 76,tmp = 76小于有序区{0,9,12,26,34,37,55,76,94}最后一个元素(94),将94后移覆盖array[9],亦即:array[9] = 94;继续将tmp = 76与有序区{0,9,12,26,34,37,55,76,94}从后向前第二个元素(76)比较,tmp = 76 = 76,则直接将tmp = 76插入到有序区数组元素76后面的位置。此时,有序区为{0,9,12,26,34,37,55,76,76,94},无序区为{37,5,68,83,90,37,12,65,76,49}。 继续执行直至完成的过程中,对于两个相等的数组元素,原始为排序数组中索引位置的大小关系并没有发生改变,也就是说,对于值相等的元素e,存在ei1,ei2,……eik,其中i1,i2……ik是数组元素e在为排序数组中的索引位置,排序前有i1<i2<……<ik,排序后仍然有j1<j2<……<jk,其中j1<j2<……<jk为排序后值相等的元素e的索引。 可见,直接插入排序是稳定的。