shell排序算法

排序流程如下：

1.将有n個元素的數組分成n/2個數字序列，第一個資料與n/2+1個資料為一對，......；

2.一次循環使每個序列對排好順序；

/*
希爾排序，又稱為縮小增量排序
優點：在大量資料面前，希爾排序比直接插入排序效率高很多

*/
#include<iostream>
#include<ctime>
using namespace std;
#define SIZE 5
void ShellSort(int* a, int len);
int main()
{
	int i;
	int array[1000];
	srand(time(NULL));
	for (i = 0; i < SIZE; i++)
	{
		array[i] = rand()/1000;
	}
	for (i = 0; i < SIZE; i++)
	{
		cout << array[i] <<" " ;
	}
	cout << endl;
	ShellSort(array, SIZE);
	for (i = 0; i < SIZE; i++)
	{
		cout << array[i] << " ";
	}
	return 0;
}
void ShellSort(int* a, int len)
{
	int i, j, h;//循環變量
	int r;//增量r
	int temp;
	int x = 0;//輸出每一步的時候要用到的
	/*數組長度/2獲得第一次增量,直到增量為1*/
	for (r = len / 2; r >= 1; r /= 2)
	{
		/*從增量開始*/
		for (i = r; i < len; i++)
		{
			temp = a[i];//增量元素開始
			j = i - r;//擷取j的下标
			while (j >= 0 && temp < a[j])
			{
				a[j + r] = a[j];//交換位置
				j = j - r;//判斷是否大于0
			}
			a[j + r] = temp; 
		}
		x++;
		cout << "第" << x << "步驟排序結果：";
		for (h = 0; h < len; h++)
		{
			cout << a[h] << " ";
		}
		cout << endl;
	}
}