排序算法——直接插入排序和希尔排序

1直接插入排序

1.1直接插入排序的思想

• 每一趟将待续序列中的第一个值，插入到已经排列好的序列中，从而得到一个元素个数加一的新有序序列，就像打牌摸牌时候将新揭来的牌排序一样，按顺序插入到合适位置即可。
  
• 如果是降序排列：对于已经排列好的有序序列来说，从右往左，依次将值和待插入值进行比较，如果小于待排序值，就向右挪动一位，接着进行比较，直到找到一个大于或等于待插入值的数值或者触底，这时将待排序数值插入进来即可。
• 

1.2 排序过程

1.3 源代码

void Insert_Sort(int *arr, int len)
{ 
   
	//for(int i=0; i<len-1; i++)
	for(int i=1; i<len; i++)//控制需要跑多少趟len-1 
	{ 
   
		int tmp = arr[i];
		int j;
		for(j=i-1; j>=0; j--)//控制在已排序好序列中，找到待排序值 可以插入的合适的位置
		{ 
   
			if(arr[j] > tmp)
			{ 
   
				arr[j+1] = arr[j];
			}
			else//arr[j] <= tmp
			{ 
   
				//arr[j+1] = tmp; //找到一个小于或者等于tmp的值
				break;
			}
		}
		arr[j+1] = tmp; //触底之后的处理规则
	}
}

1.4直接插入法性能分析

• 时间复杂度：O(n^2)
• 空间复杂度O(1)
• 稳定性：稳定
  

1.5 直接插入法的优缺点

• 优点：
  1.如果n较小，那么n^2也不会太大（当数据量较小时，可以直接使用直接插入法）
  2.较为稳定
• 缺点
  时间复杂度过高（n^2）

1.6 思考（直接插入法的优化）

• 如果数据量特别少，或者数据量较为有序，直接插入法效率极高，关键点就是如何让待排序列数量降低
• 下面的希尔排序就是直接插入法的优化

2.希尔排序

• 希尔排序是第一个时间复杂度打破n^2的算法

2.1希尔排序的思想

关键点就是如何让待排序序列数量降低

• 解决方案：分割待排序序列，将其分割成很多子序列

假设有15个数字

分割方法1：从前向后33均分成5组（没有变的更加有序）

分割方法2：跳跃分割，分割成5组，一个组三个数，每个值之间距离三个数

2.2希尔排序的增量数组

希尔排序也叫最小增量排序，有一个最重要的标志——增量数组

• 增量数组一般取 [5,3,1],数组数据从小到大排列，尽可能里面的值互素，并且==最后一个增量一定是1 ==（只有最后以增量为1排序一次，才能保证数据全部有序）
  
  

2.3 希尔排序的过程

2.4 希尔排序的性能分析

• 希尔排序是基于直接插入排序的优点进行优化的

• 时间复杂度：可以认为O(n^1.3 ~ n^1.7)，比较有争议没有明确的答案，一般认为在n ^ 1.6左右
• 空间复杂度：O(1)
• 稳定性：不稳定
• 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

2.5 希尔排序源代码

void Shell(int *arr, int len, int gap)
{ 
   
	//假设gap=5，则认为前5个值已经有序，则让i直接指向第一个组的第二个值下标
	for(int i=gap; i<len; i++)//这里修改了
	{ 
   
		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; //这里修改了
	}
}

//希尔排序 时间复杂度可以认为O(n^1.3 ~ n^1.7) 空间复杂度O(1) 稳定性：不稳定
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]);
	}
}

3.测试结果

int main()
{ 
   
	int arr[] = { 
    -43,57,-71,47,3,30,-85,6,60,-59,0,-46,-40,-73,53,68,-82,-54,88,73,20,-89,-22,39,55,-26,95,-87,-57,-86,28,-37,43,-27,-24,-88,-35,82,-3,39,-85,-46,37,45,-24,35,-49,-27,-96,89,87,-62,85,-44,64,78,14,59,-55,-10,0,98,50,-75,11,97,-72,85,-68,-76,44,-12,76,76,8,-75,-64,-57,29,-24,27,-3,-45,-87,48,10,-13,17,94,-85,11,-42,-98,89,97,-66,66,88,-89,90,-68,-62,-21,2,37,-15,-13,-24,-23,3,-58,-9,-71,0,37,-28,22,52,-34,24,-8,-20,29,-98,55,4,36,-3,-9,98,-26,17,82,23,56,54,53,51,-50,0,-15,-50,84,-90,90,72,-46,-96,-56,-76,-32,-8,-69,-32,-41,-56,69,-40,-25,-44,49,-62,36,-55,41,36,-60,90,37,13,87,66,-40,40,-35,-11,31,-45,-62,92,96,8,-4,-50,87,-17,-64,95,-89,68,-51,-40,-85,15,50,-15,0,-67,-55,45,11,-80,-45,-10,-8,90,-23,-41,80,19,29,7 };
	Insert_sort(arr, sizeof(arr) / sizeof(int));
	shell_sort(arr, sizeof(arr) / sizeof(int));
	show(arr, sizeof(arr) / sizeof(int));
	return 0;
}

运行结果如下：

4.总结

希尔排序是直接插入排序的优化，两者关系十分密切，但是要记住希尔排序不稳定，直接插入排序是稳定的

• ✨ 原 创 不 易 ， 还 希 望 各 位 大 佬 支 持 一 下
• 👍 点 赞 ， 你 的 认 可 是 我 创 作 的 动 力 ！
• ⭐️ 收 藏 ， 你 的 青 睐 是 我 努 力 的 方 向 ！
• ✏️ 评 论 ， 你 的 意 见 是 我 进 步 的 财 富 ！

今天的文章排序算法——直接插入排序和希尔排序分享到此就结束了，感谢您的阅读。