c++希尔排序实例分析

本篇内容主要讲解“c++希尔排序实例分析”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“c++希尔排序实例分析”吧!

排序算法之希尔排序

基本思想

将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的而不是局部有序。

进一步理解：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

希尔排序算法

#include <iostream>
using namespace std; 
void shellSort(int arr[], int n)
{
    int tmp = 0;
    int step = n / 2;
    while (step)
    {
        for (int i = step; i < n; i++)
        {
            tmp = arr[i];
            int j = i;
            while (j >= step && tmp < arr[j - step])   //采用直接插入排序
            {
                arr[j] = arr[j - step];
                j -= step;
            }
 
            arr[j] = tmp;
        }
 
        step = step / 2;
    }
}
 
int main()
{
    int arr[]{ 3, 14, 25, -22, -3, 87, 126, 34, 64, -70, 15, 17, 78 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    system("pause");
    return 0;
}

复杂度分析

当增量为1（step = 1）时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)；

Hibbard增量的希尔排序的时间复杂度O(n^3/2)；

关于希尔排序的问题分析

排序算法之希尔排序及时间复杂度分析

希尔排序

算法思想：将整个待排序列分割成若干个子序列（由相隔增量个元素组成），分别进行直接插入排序，然后依次缩小增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

希尔排序的实现应该由三个循环完成

（1）第一次循环，将增量d依次折半，直到增量d=1

（2）第二三层循环，也就是直接插入排序所需要的两次循环。

算法实现：

#include <stdio.h>
#define N 9
int main(void)
{
	int arr[N] = {9,1,5,8,3,7,4,6,2};
	int d = N / 2; //增量先取一半
	int i,j,insertVal;
	//希尔排序三层循环
	while(d>=1) //当增量大于等于1,不断进行插入排序
	{
		//一下两层for循环是直接插入排序代码
		for(i=d; i<N; i++)
		{
			insertVal = arr[i];
			j = i - d;
			while(j>=0 && arr[j]>insertVal)
			{
				arr[j+d] = arr[j];
				j = j - d;
			}
			arr[j+d] = insertVal;
		}
		d = d / 2;
	}
	for(i=0; i<N; i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

由如上代码知，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个增量的记录组成一个子序列，实现跳跃式移动，使得排序的效率高。

时间复杂度

时间复杂度为O(n^1.5)，要好于直接排序的O(n ^ 2)，需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动，希尔排序并不是一种稳定的排序方法。

到此，相信大家对“c++希尔排序实例分析”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！