算法描述

希尔排序是基于插入排序的思想，又被称为缩小增量排序。把数组按一定增量d分组，对每组记录采用直接插入排序方法进行排序，随着增量逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成一组有序的序列。

算法执行过程

1.将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一组，第2个数据和第n/2+2个数据为一组… 2.一次循环使每一组序列排好顺序。 3.将n个元素的数组分为n/4个数字序列，再次排序。 4.不断重复，当序列变为一组时，完成排序。

C++代码

#include <iostream>
using namespace std;
#define SIZE 10
void shellSort(int arr[], int len)
{
          
   
	int i, j, h, r, temp;
	int x = 0;
	cout << "排序之前数组序列为: ";
	for (i = 0; i < len; i++)
	{
          
   
		cout << arr[i] << " ";
	}
	cout << endl<<endl<<endl;
	for (r = len / 2; r >= 1; r /= 2)
	{
          
   
		for (i = r; i < len; i++)
		{
          
   
			temp = arr[i];
			j = i - r;
			while (j >= 0 && temp < arr[j])
			{
          
   
				arr[j + r] = arr[j];
				j -= r;
			}
			arr[j + r] = temp;
		}
		x++;
		cout << "第" << x << "步的排序结果: ";
		for (h = 0; h < len; h++)
		{
          
   
			cout << arr[h] << " ";
		}
		cout << endl<<endl<<endl;
	}
	cout << "最终的序列为: ";
	for (h = 0; h < len; h++)
	{
          
   
		cout << arr[h] << " ";
	}
	cout << endl;
}
int main()
{
          
   
	int arr[SIZE] = {
          
    4,6,2,8,1,2,9,7,3,5 };
	shellSort(arr, SIZE);
	system("pause");
	return 0x0;
}

执行过程

算法性能分析

参考

Algorithms (Fourth Edition) [美] Robert Sedgewick