【数据结构】排序算法——插入排序和希尔排序

一、插入排序

1.算法思想

      要求在一个已经有序的数据序列中插入一个数据,并且插入次数据后数据序列依然有序,这时就需要用到一种新的排序方法——插入排序,其基本思想就是每步讲一个待排序的记录,按其关键码值的大小插入到前面已经排序的文件中适当的位置,直至全部插入完为止。

2.具体步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果已排序的元素大于新元素,将其移到下一位置
  4. 重复步骤3,直至找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入
  6. 重复步骤2-5

3.算法复杂度

     时间复杂度:如果将n个元素升序排列,最好的情况是已经升序,这种情况下,只需要进行(n-1)此比较即可;最坏的情况是降序排列,此时需要比较n(n-1)/2次。平均时间复杂度为o(n^2)。

     空间复杂度:o(1)

     稳定性:在插入过程中,如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,是稳定的。

void InsertSort(int* arr, size_t size)
{
	if (NULL == arr || size == 1)
		return;
	for (size_t i = 1; i < size; i++)
	{
		int key = arr[i];
		int end = i - 1;
		while (key < arr[end] && end >= 0)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
}

在插入数据过程中,比较次数可能会比较多,我们可以将直接查找的方改为折半查找,即可得到折半插入排序算法,相比于直接插入排序,有一定的优化。

void InsertSort_B(int* arr, size_t size)
{
	if (NULL == arr || size == 1)
		return;
	for (size_t i = 1; i < size; i++)
	{
		int key = arr[i];
		int left = 0;
		int right = i - 1;
		int end = i - 1;
		while (left <= right)
		{
			int mid = left + ((right - left) >> 1);
			if (key < arr[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
		while (left <= end)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
}

二、希尔排序

1.算法思想

       希尔排序又称缩小增量法,是直接插入排序的一种改进。其基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量 dt=1,即所有记录放在同一组中进行直接插入排序为止。

       该方法实质上是一种分组插入的方法。

2.具体步骤

假设有10个记录,其关键字分别是:7,5,3,1,9,4,6,2,0,8;取增量依次为3,2,1


3.算法分析

     希尔排序不需要大量的辅助空间,容易实现。相比于插入排序,效率上有所提高,其时间复杂度也有增量的选取有关。希尔排序没有快速排序快,对于规模非常大的数据排序不是最优的选择;但是希尔排序在最坏的情况下和平均情况下执行效率相差不是很大,快速排序则相差较大,因此,几乎任何排序工作在开始时都可以用希尔排序,若在实际中证明它不够快,再改成快速排序。此外,希尔排序是不稳定的。

void ShellSort(int* arr, size_t size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 4 + 1;
		for (size_t i = gap; i < size; i++)
		{
			int key = arr[i];
			int end = i - gap;
			while (key < arr[end] && end >= 0)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = key;
		}
	}
}
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院