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.另外由于记录跳跃式的移动，希尔排序并不是一种稳定的排序方法。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持自由互联。