[算法] 希尔排序
插入排序速度慢，因为它进行的唯一交换涉及到邻接项，因此，在数组中，项只能一次移动一个位置。例如，如果最小键刚好就在数组的末端，则需要N步将它移到位。希尔排序（Shellsort）是插入排序的简单扩展，它允许离得很远的元素进行交换，所以提高了速度。希尔排序的思想是，重排文件后让它具有以下性质：每隔h取一个元素（从任意处开始），得到一个有序文件。这种文件称做h-有序（h-sorted）。换一个角度看，一个h有序文件是h个独立的有序文件，它们交叉排列在一起。当h较大时，通过h排序，我们可以在数组中长距离移动元素，因此，使得对于更小的h，更容易进行h-排序。对于任意的h值序列（以1结尾），使用这样的过程都生成一个有序文件。这就是希尔排序的实质。
一种实现希尔排序的方式是，对每个h分别使用插入排序独立排序所有h个子文件。尽管这个过程已经很简单，但我们甚至还可以使用更简单的方式，因为这些子文件是独立的。当使用h-排序文件时，将较大元素移到右边，然后在h-子文件的前面元素中插入。
#include <iostream>
using namespace std;
void shellSort(int arr[, int n)
{
int i, j;
int key;
int h;
for (h = 1; h <= (n-1)/9; h = 3*h + 1)
;
for (; h > 0; h /= 3)
for (i = h; i < n; i++)
{
key = arr[i;
j = i;
while ((j >= h) && (arr[j-h > key))
{
arr[j = arr[j-h;
j -= h;
}
arr[j = key;
}
}
int main()
{
int arr[15 = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753};
int i;
cout << "Original array" << endl;
for (i = 0; i < 15; i++)
cout << arr[i << " ";
cout << endl << endl;
shellSort(arr, 15);
cout << "Sorted array" << endl;
for (i = 0; i < 15; i++)
cout << arr[i << " ";
cout << endl;
return 0;
}
页:
[1]