上周给大家分享了希尔排序的内容：

传送门：如何理解希尔排序的过程？（一）

有需要的同学可以温故一下。

下面让我们继续希尔排序的第二部分分享：

3，关于希尔排序的性能分析

（1）对希尔排序的时间复杂度分析很困难，在特定情况下可以准确的估算排序码的比较次数和元素移动的次数，但要想弄清楚排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

（2）这里我们把3种常用的插入排序做一个程序测试，通过每种算法测试所执行的时间，来定性的认识希尔排序的性能优劣。测试的思路是通过生成1000个1——1000之间的随机数，令三种排序算法分别对其进行排序，输出排序所花费的时间。

（3）测试的程序源码（C++）

/*

* 插入排序算法

*/

#include <iostream>

#include <vector>

#include <string>

#include <ctime>

using namespace std;

//vector<int> numbers{3, 2, 4, 6, 1, 9, 5, 8, 7, 10};

//vector<int> numbers{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};

//vector<int> numbers{21, 25, 49, 25, 16, 8};

vector<int> numbers;

//函数功能，直接插入算法对数字排序

//函数参数，数列起点，数列终点

void dinsert_sort(const int start, const int end) {

    for (int i = start + 1; i <= end; ++i) {

        if (numbers[i] < numbers[i - 1]) {

            int temp = numbers[i];

            int j = i - 1;

            do {    //依次移动并寻找插入位置

                numbers[j + 1] = numbers[j];

                --j;

            }while (j >= start && numbers[j] > temp);

            numbers[j + 1] = temp;  //插入元素

        }

    }

}

//函数功能，折半插入算法对数字排序

//函数参数，数列起点，数列终点

void binsert_sort(const int start, const int end) {

    int low = 0, high = 0, middle = 0;

    for (int i = start + 1; i <= end; ++i) {

        int temp = numbers[i];

        low = start;

        high = i - 1;

        while (low <= high) {   //折半搜索寻找插入位置

            middle = (low + high) / 2;

            if (numbers[middle] > temp) {   

                high = middle - 1;  //定位到前半部分

            }

            else {

                low = middle + 1;   //定位到后半部分

            }

        }

        for (int k = i - 1; k >= low; --k) {

            numbers[k + 1] = numbers[k];    //成块移动，空出插入位置

        }

        numbers[low] = temp;    //插入元素

    }

}

//函数功能，希尔排序算法对数字递增排序

//函数参数，数列起点，数列终点

void shell_sort(const int start, const int end) {

    int increment = end - start + 1;    //初始化划分增量

    int temp{ 0 };

    do {    //每次减小增量，直到increment = 1

        increment = increment / 3 + 1;

        for (int i = start + increment; i <= end; ++i) {    //对每个划分进行直接插入排序

            if (numbers[i - increment] > numbers[i]) {

                temp = numbers[i];

                int j = i - increment;

                do {    //移动元素并寻找位置

                    numbers[j + increment] = numbers[j];

                    j -= increment;

                } while (j >= start && numbers[j] > temp);

                numbers[j + increment] = temp;  //插入元素

            }

        }

    } while (increment > 1);

}

//函数功能，随机产生amount个start——end内的随机数并存入指定容器

//函数参数，随机数范围起点，随机数范围终点，随机数生成数量

void produceRandomNumbers(const int start, const int end, const int amount) {

    srand((unsigned)time(NULL));

    for (int cnt = 1; cnt <= amount; ++cnt) {

        numbers.push_back(start + (rand() % (end - start)));

    }

}

int main()

{

    time_t c_start, c_end;

    produceRandomNumbers(1, 1000, 1000);

    c_start = clock();

    //dinsert_sort(0, 999);

    //binsert_sort(0, 999);

    shell_sort(0, 999);

    c_end = clock();

    cout << "当前排序算法花费时间为：" << difftime(c_end, c_start) << "ms" << endl;

    for (auto iter = numbers.cbegin(); iter != numbers.cend(); ++iter) {

        cout << *iter << " ";

    }

    system("pause");

    return 0;

}

（4）有关测试结果

直接插入排序：

折半插入排序：

希尔排序：

当然这里没有让其对同一组数据进行测试，会存在一定的误差，但是通过对其多次测试，3中算法的平均优劣程度还是比较明显的。

4，写在最后

关于数字的排序算法的研究是一个乐此不疲的话题，对于这些基本的排序算法应该常记、常用。也希望大家对文中不当之处给予指正。

如果需要详细了解试听或培训课程费用可留下 姓名+联系方式（手机号或微信号），我们会在第一时间为您解答服务！

软件测试零基础班

软件测试周末精品班

java开发班

ISTQB考试班

更多资讯尽在官方网站

www.njzhenghou.com