行业资讯
【正厚软件】如何理解希尔排序的过程?(二)
2019-08-19

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

传送门:如何理解希尔排序的过程?(一)

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

 

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

 

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

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

 

(2)这里我们把3种常用的插入排序做一个程序测试,通过每种算法测试所执行的时间,来定性的认识希尔排序的性能优劣。测试的思路是通过生成10001——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);

}

 

//函数功能,随机产生amountstart——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

咨询热线
预约试听:025-86665061
官方公众号:ZhenghouSoft
技术热线:025-86665061
联系地址
南京总部:南京市鼓楼区湖南路16号5楼
重庆中心:重庆市渝中区投资大厦6楼
武汉中心:江夏区光谷智慧园16栋
微信公众号
联系我们
咨询热线:025-86665061
友情链接
Copyright © 2018 南京正厚软件 苏ICP备17057415号 网站地图 XML地图