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++希爾排序實例分析”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！