希爾排序是直接插入排序的優化。比較次數和插入次數應該都會變小。
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void ShellSort(int arr[], int n)
{
int i;
int increment = n/2;
while(increment != 0)
{
for(i=increment; i<n; i++) //循環從第2個數組元素開始，移位arr[0]作為最初已排序部分
{
int j;
int temp = arr[i];
for(j=i-increment; j>=0 && arr[j]>temp; j=j-increment)
arr[j+increment] = arr[j];
arr[j+increment] = temp;
}
increment = increment/2;
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
ShellSort(arr,n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282211
