排序算法-插入/希尔排序

1 插入排序

1.1基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

1.2直接插入排序：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

直接插入排序的特性总结： 1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定

 写排序算法的一种好习惯就是先写一个单趟排序，再使用循环来实现整体。假设实现一个升序，首先创建一个变量end=0，然后tmp保存a[end+1]的值，写一个while循环，结束条件是end=a[end]，直接退出循环。然后将tmp的值插入到a[end+1]这个位置。然后最外层套一层循环，每次单趟结束后end++。

// 插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i = 0)
		{
			if (tmp  
2.希尔排序( 缩小增量排序 )
 
 
 希尔排序法又称缩小增量法。希尔排序法的基本思想是： 
 先选定一个整数，把待排序文件中所有记录分成个 
 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工 
 作。当到达 
 =1 
 时，所有记录在统一组内排好序 
 。  
 
 
 
 假设将下列数组分为gap=3组，先完成单趟，将end=0，tmp保存a[end+gap]这个位置的值，进行比较，tmp大则将a[end]覆盖到[end+gap]这个位置，然后end-gap,退出循环，将tmp插入到a[end+gap]这个位置，也就是a[0]这个位置。然后写一个循环控制end的位置，每次end+gap。到这里就完成了黑色的这一组数据，此时可以再套一层循环控制住红色和蓝色的这两组数据。 
 
 
 
 
void ShellSort1(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j = 0)
				{
					if (tmp  
 
当然也可以在单趟外只套一层循环，巧妙地控制i。
 
 
void ShellSort2(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;
		for (int i = 0; i = 0)
			{
				if (tmp  
  
  希尔排序的特性总结：  
  
  
  
   
   1.  
   希尔排序是对直接插入排序的优化。  
   
   
   2.  
   当 
   gap > 1 
   时都是预排序，目的是让数组更接近于有序。当 
   gap == 1 
   时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。  
   
   
   3.  
   希尔排序的时间复杂度不好计算，因为 
   gap 
   的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定。 
   
  
 
 
4. 稳定性：不稳定  。
（图片来源网络，侵删）
 
今天的分享到这里就结束了，感谢大家的阅读！
（图片来源网络，侵删）

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。