排序算法之希尔排序

快来打我* 2022-08-21 01:05 185阅读 0赞

# 排序算法之希尔排序 #

这一系列主要讲的是排序算法，首先会简单介绍各种排序算法的基本思想，然后会给出每种算法的Python实现和C++实现,代码中均有非常详细的注释。最后会给出不同算法的复杂度分析。

文中Python代码是在`Python3.4.3或 Python3.2`上实现的，C++代码是在`Dev-C++5.7.1`上实现的。如果有什么不清楚或者不对的地方，欢迎大家随时指正。

**希尔排序的基本思想是**：将相距某个“增量”的记录组成一个子序列，在每个子序列内分别进行直接插入排序，使得到的结果基本有序（即小的关键字基本在前面，大的关键字基本在后面），最后再对整体使用一次直接插入排序，得到有序序列。

**Python代码实现**：

import numpy as np
    
    def ShellSort(unSortedArray):
        length = len(unSortedArray)   #获取待排序数组的长度
    
        #通过希尔排序让整个序列基本有序
        increment = int(np.log(length) // np.log(2))+1   #根据完全二叉树的深度计算增量，即子序列间元素的间隔
        for i in range(increment):
            k = i
            #分段之后，排序跟直接插入排序一致
            for j in range(i,length-increment,increment):
                flag = True
                while j >= k and flag == True:
                    flag = False
                    if unSortedArray[j] > unSortedArray[j+increment]:
                        temp = unSortedArray[j]
                        unSortedArray[j] = unSortedArray[j+increment]
                        unSortedArray[j+increment] = temp
                        flag = True
                        j -= increment        #如果调换，说明还需要跟前面的元素比较
    
        #元素基本有序之后再进行一次直接插入排序
        for i in range(length-1):
            flag = True  #设置标志变量
            while i >= 0 and flag == True:    #因为插入的是有序序列，所以一旦不需要交换，就退出内层循环
                flag = False
                if unSortedArray[i] > unSortedArray[i+1]:
                    temp = unSortedArray[i]
                    unSortedArray[i] = unSortedArray[i+1]
                    unSortedArray[i+1] = temp
                    flag = True
                    i -= 1                    #此处的i跟外层循环的i不一样
    
        return unSortedArray
    
    #算法验证
    unSortedArray = np.array([0,27,12,9,1,5,8,3,7,4,6,2,18,15,10])
    print("The original data is: ",unSortedArray)
    print("The sorted data is: ",ShellSort(unSortedArray))

运行结果为：

>>> ================================ RESTART ================================
    >>>
    The original data is: [ 0 27 12 9 1 5 8 3 7 4 6 2 18 15 10]
    The sorted data is: [ 0 1 2 3 4 5 6 7 8 9 10 12 15 18 27]

**C++代码实现**：

#include <iostream>
    #include <cmath>
    
    using namespace std;
    
    //交换两个元素，形参为引用形参
    void swap(int &a, int &b)
    {
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
    
    //希尔插入排序：在各个子序列上使用直接插入排序，待整个数组基本有序时，再在整个数组上使用直接插入排序 
    int* ShellSort(int *a, int length)
    {
        int increment = static_cast<int>(log(length)/log(2))+1;    //根据完全二叉树的深度计算增量，即子序列间元素的间隔
    
        for(int i = 0; i < increment; ++i)
        {
            int k = i;                        // i为各个子序列的起始位置
    
            //各个子序列分别直接插入排序
            for(; k < length-increment; k += increment)
            {
                int j = k + increment;       //子序列相邻元素间隔为increment
                bool flag = true;
    
                while(j > i && flag == true)
                {
                    flag = false;
                    if(a[j] < a[j-increment])
                    {
                        swap(a[j], a[j-increment]);
                        flag = true;
                        j -= increment;
                    }
                }
            }
        }
    
        //整个数组基本有序之后，再整体进行一次直接插入排序
        for(int i = 0; i < length-1; ++i)
        {
            bool flag = true;
            int j = i+1;
    
            while(j > 0 && flag == true)           //因为每次都是插入到有序数组中，所以当没有交换时直接退出内循环
            {
                flag = false;
                if(a[j] < a[j-1])                  //比较待插入元素和有序数组中的元素
                {
                    swap(a[j], a[j-1]);            //交换之后设置标志变量为true，说明还需要与有序数组中其它元素进行比较
                    flag = true;
                    --j;                           //内层循环变量减1，指向待插入元素
                }
            }
        }
        return a;
    }
    
    int main(int argc, char** argv) {
    
        int originalArray[] = {
       0,27,12,9,1,5,8,3,7,4,6,2,18,15,10};
        int length = sizeof(originalArray)/sizeof(int);          //计算数组长度
    
        cout << "The length of the array is " << length << endl;
        cout << "The original array is: ";
        for(int i = 0; i <= length-1; i++)                       //打印待排序数组元素
        {
            cout << originalArray[i] << static_cast<char>(32);   //32是空格的ASCII值，把它转换成空格输出
        }
        cout << endl;
    
        int *sortedArray = ShellSort(originalArray,length);     //调用排序算法，返回一个指向int型数组的指针
        cout << "The sorted array is: ";
        for(int i = 0; i <= length-1; i++)                       //打印排序结束之后的数组元素
        {
            cout << sortedArray[i] << static_cast<char>(32);
        }
        return 0;
    }

运行结果为：

The length of the array is 15
    The original array is: 0 27 12 9 1 5 8 3 7 4 6 2 18 15 10
    The sorted array is: 0 1 2 3 4 5 6 7 8 9 10 12 15 18 27

**希尔排序的算法复杂度**：  
由于希尔排序中元素是跳跃式的移动，所以它不是一种稳定的排序算法。希尔排序中“增量”的选取很重要，选取恰当时，其时间复杂度可以达到O(n^(3/2))。

[排序算法之直接插入排序 ][Link 1]

[Link 1]: http://blog.csdn.net/qq_33256568/article/details/50816170