C#希爾排序-C#.Net教程-PHP中文網

C#希爾排序

黄舟

發布： 2017-02-09 16:10:30

原創

2046 人瀏覽過

C#希爾排序

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class ShellSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            ShellSort(a);  
            return  a;  
        }  
        public static void ShellSort(int[] myArray)  
        {  
            int i, j, increment;  
            int temp;  
            for (increment = myArray.Length / 2; increment > 0; increment /= 2)  
            {  
                for (i = increment; i < myArray.Length; i++)  
                {  
                    temp = myArray[i];  
                    for (j = i; j >= increment; j -= increment)  
                    {  
                        if (temp < myArray[j - increment])  
                            myArray[j] = myArray[j - increment];  
                        else  
                            break;  
                    }  
                    myArray[j] = temp;  
                }  
            }  
        }  
    }  
}

登入後複製

希爾排序是對直接插入排序演算法的改進，其主要思想是：先將整個排序數列分割成為若干個子序列，在子序列分別進行直接插入排序，待整個數列基本有序時再對全部進行一次直接插入排序。以此來形成新的有序數列。一般分割方法是兩個元素相距d=n/2,n/4,n/8…以此類推。
1.基本思想：
把整個待排序的數據元素分成若干個小組，對同一小組內的數據元素用直接插入法排序；小組的個數逐次縮小，當完成了所有數據元素都在一個組內的排序後排序過程結束。
2.技巧：
小組的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個小組,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。
3.優點：
讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。

例子一：

C#希爾排序