直接插入排序与希尔排序_希尔排序一定比插入排序好吗

直接插入排序

基本思想：
   每一步将一个待排的数据插入到前面已经排好序的有序序列中，知道插完所有元素为止。
算法实现过程：

空间复杂度：
   不需要额外的存储空间，所以空间复杂度是O(1)，是个原地排序算法
稳定性判别（稳定性就是指相同的元素在排序的过程中被移动）：
   对于值相同的元素，我们可以将后面出现的元素插入到前面出现的元素后面，从而保持了原有的前后顺序不变。
时间复杂度：
   最好的情况是待排序的数组已经排好序了，所以每次比较的时候只需要比较一个元素就能确定的那个要插入的位置，这种情况下的时间复杂度是O(n),当数组的顺序刚好是倒序的情况下，那么每次插入都相当于是在数组的第一个位置插入，需要移动大量元素，此时的时间复杂度是O(n^2)

希尔排序

基本思想：：
   希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
增量序列：
   希尔排序需要定义一个增量，这里选择增量为gap=length/2，缩小增量以gap=gap/2的方式，这个增量可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列，这个增量是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
算法实现过程：
1.

   先将序列按照gap=5分组，就是将间隔为5的元素都放在一起，得到[8,3],[9,5],[1,4],[7,6],[2,0],然后对这些序列进行直接插入排序。例如：[8,3]，将首元素8暂定为有序序列，然后比较第二个元素2，发现2比8小，所以将2插入到8的前面，得到序列[2,8]，后面的类似。最后得到序列为

2

   按照序列gap=gap/2=2来分组，同样将间隔为2的元素都放在一起，得到的序列为[3,1,0,9,7],[5,6,8,4,2]，接着再对这两个序列进行插入排序，例如[3,1,0,9,7]，

后面的序列也是同理。最后得到的序列为:

3.

   按照gap=gap/2=1来分组，得到[0,2,1,4,3,5,7,6,9,8]，对这个序列进行直接插入排序，最后得到

代码 ：
c:

int shsort(int s[], int n) { /* 自定义函数 shsort()*/
	int i,j,d;
	d=n/2; /*确定固定增虽值*/
	while(d>=1) {
		for(i=d+1;i<=n;i++) { /*数组下标从d+1开始进行直接插入排序*/
			s[0]=s[i]; /*设置监视哨*/
			j=i-d; /*确定要进行比较的元素的最右边位置*/
			while((j>0)&&(s[0]<s[j])) {
				s[j+d]=s[j]; /*数据右移*/
				j=j-d; /*向左移d个位置V*/
			}
			s[j + d]=s[0]; /*在确定的位罝插入s[i]*/
		}
		d = d/2; /*增里变为原来的一半*/
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

java:

public static int[] shellSort(int[] array)
{
    if(array.length>0){
        int len=array.length;
        int gap=len/2;
        while(gap>0)
        {
            for(int i=gap;i<len;i++)
            {
                int temp=array[i];
                int index=i-gap;
                while(index>=0 && array[index]>temp){
                    array[index+gap]=array[index];
                    index-=gap;
                }
                array[index+gap]=temp;
            }
           //增量逐渐递减
            gap/=2;
        }
    }
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度： 平均时间复杂度O(nlogn)
空间复杂度： O(1)
稳定性： 不稳定 ，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但多次插入排序，相同的元素可能在各自的插入排序中移动，最后其稳定性被打乱，所以是不稳定的
性能分析：
   ① 希尔排序更加高效的原因：它权衡了子数组的规模和有序性。
   ②希尔排序和选择排序以及插入排序形成对比的是：希尔排序也可以用于大型数据，它对任意排序的数组变现很好。希尔排序比插入排序和选择排序要快的多，并且数组越大，优势越大。
优化：
   ①对增量序列优化
   ②对每一趟的插入排序进行优化