排序算法之 - 希爾排序(基于選擇排序,插入排序)

    之前說的選擇,插入,冒泡三種基本排序,時間複雜度都為O平方,直到希爾排序的出現,打破了O平方的魔咒.希爾排序的基本思想我了解是屬于分而治之,把一個無序序列劃分為若幹個子序列,再分别對這寫子序列使用三種基本排序方法進行排序.

下邊直接看示意圖:

要排的序列為 int array[] = {12,32,2,4,6,54,34,76,89,32,14};排序為升序排序

第一次劃分:假設間隔d = 3,那麼可以劃分為{12,32,2,4,6,54,34,76,89,32,14}得到三個子序列(一個顔色集合為一個子序列)

接着對三個子序列按基本排序法排序,得到{4,6,2,12,14,54,32,32,89,34,76},從這裡我們可以看到,這個序列已經基本有序.

第二次劃分:縮減間隔d=2,那麼可劃分為{4,6,2,12,14,54,32,32,89,34,76} 得到兩個子序列,然後對這兩個子序列按基本排序法排序,

得到  {2,6,4,12,14,32,32,34,76,54,89}

第三次劃分:縮減間隔d=1,劃分為 {2,6,4,12,14,32,32,34,76,54,89},到了這裡,整個序列基本已經排好了,隻需要在使用一次基本排序,做少量的元素交換,便可完成序列的排序.

    以上便是希爾排序的基本思想,先分而治之,劃分為各個子序列,各自排序,之後隻需要統一做少量的交換工作,便可完成整個序列的排序.下邊來看看代碼,這裡我分别使用選擇排序,插入排序來實作

#include <iostream>
#include <string.h>
#include <errno.h>
#include <stdio.h>

using namespace std;

//需要注意的是,這裡的類模闆需要放在頭檔案中去實作,這裡為了直覺,直接放這裡了
template <typename T>
class Sort : public Object
{
private:
static void swap(T& nLeft, T& nRight)
{
    T tmp = nLeft;
    nLeft = nRight;
    nRight = tmp;
}
public:
//基于選擇排序的希爾排序
static void SelectShell(T* nArray, int nLen, bool Min2Max = true)
{
    int d = nLen;
    while(d > 1)
    {
        d = d/3 +1;
        int count = 0;
        while(count<d)
        {
            for(int i=count; i<nLen; i+=d)
            {                
                int index = i;

                for(int j=i+d; j<nLen; j+=d)
                {
                    if( Min2Max ? (nArray[index] > nArray[j]):(nArray[index] < nArray[j]))
                    {
                        index = j;
                    }
                }
                if(index != i)
                {
                    swap(nArray[index], nArray[i]);
                }
            } 
            count++;
        }                   
    }
}
//基于插入排序的希爾排序
static void InsertShell(T* nArray, int nLen, bool Min2Max = true)
{
    int d = nLen;
    while(d > 1)
    {
        d = d/3 + 1;
        int count = 0;
        while(count < d)
        {
            for(int i=count; i<nLen; i+=d)
            {
                int index = i;
                T e = nArray[index];
                for(int j=i; j>=0; j-=d)
                {
                    if( Min2Max ? (e < nArray[j]):(e> nArray[j]))
                    {
                        nArray[j+d] = nArray[j];
                        index = j;
                    }
                }
                if(index != i)
                {
                    nArray[index] = e;
                }
            }
            count++;
        }        
    }
}
};

int main(int argc, char* argv[])
{
    int array[] = {12,32,2,4,6,54,13,34,25,87,76,89,32,14,23};
    int len = sizeof(array)/sizeof(int);

    Sort<int>::InsertShell(array, len);

    for(int i=0; i<len; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    Sort<int>::SelectShellShell(array, len, false);

    for(int i=0; i<len; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}
           

main測試函數中分别用了基于插入排序與基于選擇排序的希爾排序來測試,一個測升序,一個測降序,其結果是符合我們的預期的