希尔排序 (java)
一种基于插入排序的快速的排序算法, 适用于大量数据
算法的性能取决于 h, 还取决于 h 之间的数学性质, 目前无法证明某个序列是最好的
数组越大优势越大
交换不相邻的元素以对数组的局部进行排序, 使数组中任意相隔为 h 的元素都是有序的
- public class shell
- {
- public void sort(Comparable[] a)
- {
- int h=1
- while(h<a.length/3) h=h*3+1;
- while(h>0) // 直到分成 1 个单位
- {
- for(i=h; i<a.length; i++)
- {
- for(int j=i; j<=h && a[j]<a[j-h]; j=j-h)
- swap(a[j],a[j-h]);
- }
- h=h/3;
- }
- }
- }
- #include<iostream>
- using namespace std;
- int main()
- {
- int N;
- int *a = new int [100005];
- cin>>N;
- for(int i=0; i<N; i++)
- cin>>a[i];
- // 希尔排序
- int h=1;
- while(h<N-1) h=h*3+1;
- while(h>=1)
- {
- for(int i=h; i<N; i++)
- {
- for(int j=i; j>=h&&a[j]<a[j-h]; j-=h)
- {
- int temp=a[j-h];
- a[j-h]=a[j];
- a[j]=temp;
- }
- }
- h=h/3;
- }
- for(int i=0; i<N; i++)
- cout<<a[i]<<" ";
- cout<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2842428.html