【直接插入排序】&&【希尔排序】
【直接插入排序】
> 基本思想：
将待排序的数据，按照要求(升序还是降序)逐个插入到一个已经排好序的有序序列中，直到所有-的数据插入完为止，就得到一个新的有序序列。
生活中的打扑克牌，就是用了插入排序的思想
1.排序
当插入到第a[i]个元素时，前面的第a[0],a[1]s……a[i-1]d都已经排序好了，这时要想将a[i]插入进去变成有序，就要与a[i-1],a[i-2]……进行比较，如果满足条件就插入进去，让原来位置上的元素往后移动。
在数组中默认第一个位置已经插入进去，也就是相当于有序了，当数组第二个要插入进去时就要与第一个元素比较，如果要插入的元素小于第一个元素，那第一个元素只能往后移动，插入的元素进入第一个位置。然后数组第三个元素又相当于是要插入的元素，而前面两个数据已经有序，要想将这个元素插入进去，还是要与第一个第二个元素比较，当小于第二个元素时，第二个元素往后移动，第二个位置就空出来，但是不一定就是给要插入元素空的，插入的元素需要与前面有序序列中的所有序列都比较一下才能确定位置，如果它比第一个元素还小，那第一个元素就要往后挪动，进入到第二个元素的位置上去，而第一个位置就空着了，所以插入到第一个元素位置上去，后面的数据以此类推。
而我们写排序时，最好是先写一趟排序效果，再写总体排序。这样容易理解排序是如何排的。
//先写一趟排序-- int end;//表示最后一个元素的下标 int tmp;//表示要插入的数据 while (end >= 0)//这里插入数据要与前面已经排好序的数据全部比较完才可以确定位置 { if (a[end] > tmp)//当插入的元素比最后一个元素要小时 { a[end + 1] = a[end];//最后一个元素就要往后挪动，该位置空着 end--;//表示插入元素要和倒数第二，倒数第三个……比较 } else { //这里表明要插入的数据终于大于a[end]，但要注意的是哪里才是空的位置 break; } } //走到这里有两种可能，一种是a[end]比tmp小，循环停止break跳出来了，另一种就是循环一直走，直到结束 //也就是数组里每个元素都比要插入的元素要大那end就跑到-1去了 //最后tmp总归要去end+1的位置上去的 a[end + 1] = tmp;//这是一趟 }
插入元素要插入的位置总是a[end+1]
写完单趟后，我们就可以写总体的了
我们想，要让一个数组排序，利用插入排序算法，首先将数组第一个元素看成已经有序，从第二个元素开始插入。
//插入排序 void Insert(int* a,int n) { for (int i = 1; i < n; i++)//这里从从数组第二个元素开始往后插入，默认数组第一个元素就插入进去 { int end=i-1;//表示最后一个元素的下标----第一个元素位置下标为0 int tmp=a[i];//表示要插入的数据---从第二个元素开始插入，第二个元素位置是i while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { //这里表明a[end]比tmp要小了,但end+1上才是空位 break; } } //最后tmp总归要去end+1的位置上去的 a[end + 1] = tmp;//这是一趟 } }
插入排序就写完啦，简简单单，轻轻松松。
让我们试一试效果。
int main() { int a[] = { 9,8,7,6,5,4,3,2,1,0 }; Insert(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0; }
对插入排序进行测试效率如何：随机生成10000个数，利用插入排序算法看运行的时间如何。
#include <stdlib.h> #include <time.h> void InsertTest() { srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); } int begin1 = clock(); Insert(a1, N); int end1 = clock(); printf("InsertSort:%d\n", end1 - begin1); free(a1); }
2.特性总结
1.元素集合越接近有序时，直接插入排序算法时间效率很块
2.时间复杂度为:O(N^2)
最坏情况下完全逆序，时间复杂度为O(N^2)
最好情况下完全有序，时间复杂度为O(N)
3.空间复杂度：O(1),它是一种稳定的排序算法
4.稳定性：稳定
【希尔排序】
1.排序
> 基本思想：
希尔排序法又称为缩小增量法。
总过程可分为–>预排序–>排序
先选定一个整数gap，把待排数据分成gap组。所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序，然后，不断的选取gap，重复上述分组和排序的工作。当gap到达1时，也就是真正的排序，这时，所有数据将统一组内排好序。
希尔排序其实本质是对插入排序的优化，希尔想着插入排序效率有点低哎，但又分析发现当数据接近有序的时候，插入排序的时间效率就很快，希尔就想着能不能先让一组数据先趋于有序，然后再使用直接插入排序，那样效率就嘎嘎快了。
所有希尔就将排序分成预排序，这个预排序的作用就是为了让数据趋于有序，那怎么使数据趋于有序呢？
分组预排：让大的数更快跳到后面，让小的数更快的跳到前面。经过多组的分组预排，这个组就越分越有序了。间距越来越小，组分的数据就越大。
最后一次gap一定要是1.
希尔将数据分成gap组，每距离gap个距离个元素就分成一组，然后对每一组都使用插入排序算法，使它们在各自的组里有序，那最后所有的数据肯定比开始是区域有序的，为什么呢？
设置gap其实是提高了数据交换的速度，原来很大的数据可能要挪动n-1次，但是设置了gap那很大的数据就可能一次挪动gap步，当gap越大时，数据交换越快。
我们先写单趟排序–比如红色一组排序
//希尔排序的特点就是分成gap区间 假设gap为3的话，就分成3部分 for (int i = 0; i < n - gap; i += gap) { //先写一趟--也就是红色一组 int end = i; int tmp = a[i + gap];//距离gap才为一组，所以下一个要插入的元素在i+gap处 while (end >= 0) { if (a[end] > tmp) { //往前移动gap位置，end每次移动gap a[end + gap] = a[end]; end -= gap; } else { break; } } //tmp总归要插入到a[end+gap]位置上去的 a[end + gap] = tmp; }
写完一趟后，下面就简单了，因为数组被分成了3组，红色一组，蓝色一组，紫色一组，而每一组的操作都是一样的。
所以在单趟的基础上，循环三次，将红色，蓝色紫色都进行一遍。
for (int j = 0; j < gap; j++)//因为数组被分成gap组，每一组的操作都类似，所以循环gap次 { //希尔排序的特点就是分成gap区间 假设gap为3的话，就分成3部分 for (int i = j; i < n - gap; i += gap) { //先写一趟--也就是红色 int end = i; int tmp = a[i + gap]; while (end >= 0) { if (a[end] > tmp) { //往前移动gap位置，end每次移动gap a[end + gap] = a[end]; end -= gap; } else { break; } } //tmp总归要插入到a[end+gap]位置上去的 a[end + gap] = tmp; } }
不过到这里希尔排序还未完成，我们这里只是假设gap为3，而真正的gap是多少呢？
其实gap的值是不断变化的，但有一点是确定的，gap的值最后必须要等于1.
当gap为1时，就是插入排序了，希尔就是像通过预排序使数据变得有序起来，然后再使用插入排序提高效率，所以最后gap的值必须为1.
如何使gap最后为1呢？
1.一开始gap通常为n，让gap每次除2，最后gap一定会等于1的。
2.或者让gap每次除3再加1，最后gap的值也会等于1的。
void Shellsort(int *a,int n) { int gap = n; while (gap) { gap/=2;//gap每次都除以2，最终gap的值一定会等于1 for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { //先写一趟--也就是红色 int end = i; int tmp = a[i + gap]; while (end >= 0) { if (a[end] > tmp) { //往前移动gap位置，end每次移动gap a[end + gap] = a[end]; end -= gap; } else { break; } } //tmp总归要插入到a[end+gap]位置上去的 a[end + gap] = tmp; } } } }
这里我们来测试希尔排序的效率如何：
void ShellTest() { srand(time(0)); const int N = 100000; int* a2 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a2[i] = rand(); } int begin1 = clock(); Shellsort(a2, N); int end1 = clock(); printf("Shellsort:%d\n", end1 - begin1); free(a2); }
我们再看看插入排序和希尔排序同时处理相同的数据时效率如何：
我们分析发现与插入排序相比，希尔排序将效率大大提高了。
2.特性总结
1.希尔排序是对直接插入排序的优化
2.当gap>1时都是预排序，目的是为让数组更接近有序。当gap==1时，数组已经接近有序了，这样再使用插入排序就很快。从而达到优化效果。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法有多种，导致很难去计算。所以希尔排序的时间复杂度没有一个固定的值。
但普遍认为希尔排序的时间复杂度是在O(n^1.3)
是和O(o*logn)一个量级的。
4.稳定性：不稳定。
