日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

c++實現排序算法之希爾排序方式_C 語言

作者：卻道天涼_好個秋 ? 更新時間： 2022-09-13 編程語言

排序算法之希爾排序

基本思想

將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內分別進行直接插入排序后得到的結果是基本有序的而不是局部有序。

進一步理解：

先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。

希爾排序算法

#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(N2)；

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.另外由于記錄跳躍式的移動，希爾排序并不是一種穩定的排序方法。

原文鏈接：https://blog.csdn.net/www_dong/article/details/110727189

欄目分類
最近更新