八大排序：直接插入排序和希尔排序

补充：稳定下：如果相同的两个值，A和A~ 如果排序前A在A~之前，排序后还能保证A再A~之前，则这个算法稳定，不然不稳定
简单方法看是否稳定：检查是否存在跳跃交换

直接插入排序其时间复杂度为O(n^2) 空间复杂度为O(1)

优点：实现简单 如果n小，n^2也就比较小   适用于n小的时候

接下来画图理解一下：

如图，第一个数据已经是有序的 所以是从第二个数开始向前比较，排序共五次。

代码实现如下：

#include 
#include 
#include 
//直接插入排序
void intersect(int *arr,int len){
for(int i=1;i=0;j--){
      if(arr[j]>tmp){
         arr[j+1]=arr[j];
      }
  else if{
       break;
      }
  arr[j+1]=tmp;
 }
}

void show(int*arr,int len){
for(int i=0;i 
2.希尔排序：（Shell）最小增量排序，是对于直接插入排序的优化 
时间复杂度O（1.5~1.7）  空间复杂度O（1）   稳定性：不稳定 
希尔排序是按照最小增量进行排序，这里提到一个最小增量组，最小增量组中全是质数，且最后一个必须是1，最小增量组不确定。在这里我们按照【5,3,1】来看。
 
假设原有数据为12,9,18,20,5,10,28,32,1,4,80,91,2,88,66，整体逻辑如下：
 
（1）先按照增量5进行排序：
 
 
增量为5 可以划分为5组  每组内进行排序，这里的排序方法和直接排序是一样的
 
（2）接下来按增量3进行排序：
 
 
 
（3）继续按照1进行排序：
 
 
 为什么说希尔排序是对直接插入的优化呢？让我们来分析一下：
 
假设有1W个数据，直接插入的时间复杂度为10000 0000
 
对于希尔：
 
增量为5的时候，每组2000个数据，时间复杂度为（2000^2）*5=20000000
 
增量为3    ，每组大概3333个数据，但经过上次排序已经变得稍微有序一些，所以每组不需要比对n^2，大概按照^1.7算      时间复杂度为（3000^1.7）*3=3000000
 
增量为1，时间复杂度为（10000^1.5）*1=1000000
 
总执行次数大概是2400 0000次<10000 0000   
 
所以说希尔排序是对直接插入的优化。
 
 
代码设计：按照我们的思路，应该是分好的组内进行比较，即：
 
 
这样来比较，代码就比较复杂。
 
为了把代码能写到一个for循环中去，正确的处理顺序应该如下：
 
 
注意只是代码这样设计，但其实实际实现中还是比较同组内的值进行排序。以下为代码，请对比图进行理解。 
 
 
 
 
void Shell(int* arr, int len, int gap)
{
	for (int i = gap; i < len; i++)//这里的i从gap开始，因为每组的第一个数字都是有序的，所以其实应该是从第一组第二个值开始向后遍历，这时下标刚好是gap。并且这里i++，不是i+gap，注意理解
	{
		int tmp = arr[i];
		int j;
		for (j = i - gap; j >= 0; j = j - gap)
		{
			if (arr[j] > tmp)
			{
				arr[j + gap] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + gap] = tmp;
	}
}

void Shell_Sort(int* arr, int len)
{
	int gap[] = { 5,3,1 };//最小增量数组

	for (int i = 0; i < sizeof(gap) / sizeof(gap[0]); i++)
	{
		Shell(arr, len, gap[i]);//注意这里调用shell
	}
}*/
void Show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
}

int main()
{
	int arr[] = { 11, 2, 9, 7, 6, 3, 1,24,12,3,1,2,5,4,1,34 };
    int len=sizeof(arr) / sizeof(arr[0]);
	Shell_Sort(arr, len);
	Show(arr,len);
	exit(0);
}
 
 总结：希尔排序和直接插入排序代码上其实是相似的，而希尔是不稳定排序，因为它存在跳跃交换，而直接插入排序则是稳定排序。在这里我们讲了八大排序中的两种，十分重要，一定要结合图理解。