c++實(shí)現(xiàn)排序算法之希爾排序方式

更新時(shí)間：2022年07月20日 10:56:59 作者：卻道天涼_好個(gè)秋

這篇文章主要介紹了c++實(shí)現(xiàn)排序算法之希爾排序方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

排序算法之希爾排序

基本思想

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

進(jìn)一步理解：

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

希爾排序算法

#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;
}

復(fù)雜度分析

當(dāng)增量為1（step = 1）時(shí)，希爾排序退化成了直接插入排序，此時(shí)的時(shí)間復(fù)雜度為O(N²)；

Hibbard增量的希爾排序的時(shí)間復(fù)雜度O(n^3/2)；

關(guān)于希爾排序的問(wèn)題分析

排序算法之希爾排序及時(shí)間復(fù)雜度分析

希爾排序

算法思想：將整個(gè)待排序列分割成若干個(gè)子序列（由相隔增量個(gè)元素組成），分別進(jìn)行直接插入排序，然后依次縮小增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。

希爾排序的實(shí)現(xiàn)應(yīng)該由三個(gè)循環(huán)完成

（1）第一次循環(huán)，將增量d依次折半，直到增量d=1

（2）第二三層循環(huán)，也就是直接插入排序所需要的兩次循環(huán)。

算法實(shí)現(xiàn)：

#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;
	//希爾排序三層循環(huán)
	while(d>=1) //當(dāng)增量大于等于1,不斷進(jìn)行插入排序
	{
		//一下兩層for循環(huán)是直接插入排序代碼
		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;
}

由如上代碼知，希爾排序的關(guān)鍵并不是隨便分組后各自排序，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列，實(shí)現(xiàn)跳躍式移動(dòng)，使得排序的效率高。