数据结构与算法设计_数据结构求顺序表的长度

数据结构与算法设计_数据结构求顺序表的长度数据结构与算法系列之插入排序及优化_插入排序的算法数据结构

在这里插入图片描述

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞

什么是插入排序

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法–插入排序法
好比可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。

在这里插入图片描述

实现思想

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与
array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移。 例如:
有一个有序区间,选其中一个数插入其中,这个数依次比较如果匹配失败则,换到下一个数比较。

在这里插入图片描述

插入排序的时间复杂度

时间复杂度是O(n^2) 在最坏情况下逆序需要每个数轮流插入 根据等差数列 1+2+3+…+n-1
所以时间复杂度是O(n^2) 在最好情况下只需要轮一遍 所以时间复杂度为O(n^2)

在这里插入图片描述

插入排序的稳定性

稳定性意思是两个元素之间的相对位置没有改变 如 4444 相等, 44在左 44在右,插入排序之后
44 仍在左 44 仍在右,这两个元素的相对位置没有改变。

在这里插入图片描述

代码实现

#include <stdio.h>
void InsertSort(int* arr, int n)
{ 
   
	for (int i = 0; i < n - 1; i++)
	{ 
   
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{ 
   
			if (tmp <= arr[end])
			{ 
   
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{ 
   
				break;
			}
		}
		arr[end + 1] = tmp;
	}


}

int main()
{ 
   
	int arr[] = { 
    1,2,4,5,6,7,8,9,3 };
	int n = (sizeof(arr) / sizeof(arr[0]));
	InsertSort(arr, n);

	for (int i = 0; i < n; i++)
	{ 
   
		printf("%d ", arr[i]);
	}
	return 0;
}

插入排序的优化——希尔排序

什么是希尔排序

希尔排序又称缩小增量排序,它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
通俗大意是:把原本一组的数组间断性分为几个数组,在对已经分完的数组进行插入排序

在这里插入图片描述

希尔排序的时间复杂度及稳定性

因为希尔排序的时间复杂度不好计算,因为gap的取值 方法很多,导致很难去计算。 时间复杂度;O(logNN)或者O(log3NN)
稳定性:不稳定

实现思想

先进行预排序,让数组接近有序,等到与排序之后 数组大多是有序的状态,大致上是有序数组,可进行插入排序。

void ShellSort(int* arr, int n)
{ 
   
	int gap = n;
	while (gap > 1)
	{ 
   

		gap = gap / 3 + 1;//gap>1时是预排列 gap==1时相当有序排列


		for (int i = 0; i < n - gap; i += gap)//把间隔为gap的元素进行插入排序
		{ 
   
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{ 
   
				if (tmp < arr[end])
				{ 
   
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{ 
   
					break;
				}
			}
			arr[end + gap] = tmp;
		}

	}
}

int main()
{ 
   
	int arr[] = { 
    1,2,4,5,6,7,8,9,3 };
	int n = (sizeof(arr) / sizeof(arr[0]));
	InsertSort(arr, n);

	for (int i = 0; i < n; i++)
	{ 
   
		printf("%d ", arr[i]);
	}
	return 0;
}

在这里插入图片描述

今天的文章数据结构与算法设计_数据结构求顺序表的长度分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/81970.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注