插入排序包括: 直接插入排序,希尔排序
1. 直接插入排序
原理:
依次取带排列数组的元素,将其插入到前面有序的数组中。
插入过程:
待插入关键字与有序数组最后一位比较,如果小于则将数组最后一位右移,直到关键字小于数组元素时,将关键字放置在当前空的位置,则新的数组有序。
实现:
public static void insertSort(int[] array)
{
int n = array.length;
for( int i = 1; i < n; i++)
insert(array, i - 1, array[i]);
}
public static void insert(int[] array, int i, int x)
{
while( i >= 0 && x < array[i])
{
array[i + 1] = array[i];
i--;
}
array[i + 1] = x;
}
算法复杂度分析:
时间复杂度:
初始文件状态
|
正序
|
反序
|
无序
|
第i趟比较次数
|
1
|
i + 1
|
( i + 1) / 2
|
总关键字比较次数
|
n -1
|
n2 /2
|
n2 /4
|
第i趟移动次数
|
0
|
i
|
i / 2
|
总关键字移动次数
|
0
|
n2 /2
|
n2 /4
|
时间复杂度
|
O(n)
|
O(n2)
|
O(n2)
|
空间复杂度: O(1)
直接插入排序为稳定排序
希尔排序:
基本思想:
先取一个小于n的整数d
1作为第一个增量,把文件的全部记录分成d
1个组。所有距离为d
l的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d
2<d
1重复上述的分组和排序,直至所取的增量d
t=1(d
t<d
t-l<…<d
2<d
1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
实现:
private static void shellPass(int[] array, int d)
{
int n = array.length;
for( int i = d; i < n; i++)
{
int j = i - d;
int x = array[i];
while( j >= 0 && x < array[j] )
{
array[j + d] = array[j];
j = j - d;
}
array[j + d] = x;
}
}
public static void shellSort(int[] array)
{
int n = array.length;
int d = n / 2;
while( d >= 1 )
{
shellPass(array, d);
d = d / 2;
}
}
算法复杂度分析:
当n较大时,比较和移动的次数约在n
l.25到1.6n
1.25之间
介于O(nlogn)和 O(n^2)之间
Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n
2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n
2)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量d
i逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按d
i-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
稳定性
希尔排序是不稳定的
分享到:
相关推荐
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
3个经典排序源代码,分别是插入排序,选择排序,冒泡排序,按数据结构里最经典的思想实现,代码绝对简洁易懂,并附有详细注释
排序-按键精灵-冒泡排序
典型排序算法的c语言实现
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
冒泡排序---选择,插入和快速排序 简单实用,非常棒的一个java工具类.
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构第23讲-插入排序2和交换排序-CPPT课件.ppt
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
交换排序 选择排序 冒泡排序 插入排序
冒泡-选择-插入 排序冒泡-选择-插入 排序冒泡-选择-插入 排序
直接插入排序、折半插入排序、希尔排列
算法-理论基础- 排序- 直接插入排序(包含源程序).rar
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
排序算法-----插入算法
二分插入排序-易语言.zip
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
binary sort,二分法查找,binary search, 二分法排序,merge sort 混合排序,shell sort 希尔排序,insertion sort 插入排序。数据结构 data structure
详解Java常用排序算法-插入排序