歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> SHELL編程

算法----希爾排序(shell sort)

在分析插入排序(插入排序算法實現)的算法性能的過程時知道,當數組規模較小或者存在較多的有序子序列時,插入排序將會在很短的時間內完成數組的排序,為此可以設計一個單調序列h[n],將數組分為多個小的序列,然後這些小的序列使用插入排序。h[n]={1,4,7,10,13,16,19……,3*x+1}。

算法實現:

void sort::shell_sort(int* a, const int n)
{
 int h = 0;
 while (h<n/3)
  h = 3*h + 1;
 while(h>=1)
 {
  for(int i=h; i<n; i++)
  {
   for(int j=i; j>=h && a[j] < a[j-h]; j = j-h)
   {
    swap(a,j,j-h);
   }
  }
  h = h/3;
 }
}

算法分析:從上述算法的實現過程中可以看出,希爾排序主要是先將數組分成若干個小的數組組成,然後對這些小的數組依次進行插入排序,經過這番排序之後,整個數組將會存在多個局部有序的子序列,這樣的數組再使用(h=1時)插入排序,將會很快的完成數組的排序。

歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm

直接插入排序的三種實現 http://www.linuxidc.com/Linux/2014-09/107313.htm

直接選擇排序及交換二個數據的正確實現 http://www.linuxidc.com/Linux/2014-09/107315.htm

排序總結之選擇式排序  http://www.linuxidc.com/Linux/2014-09/106564.htm

Copyright © Linux教程網 All Rights Reserved