C++希尔排序怎么使用

这篇文章主要讲解了“C++希尔排序怎么使用”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++希尔排序怎么使用”吧！

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序 

最后一个增量必须为1才可以， 由于是跳跃式的排序 希尔排序不稳定，时间复杂度为O(N^1.5)

#include <iostream>
#include <cstring>
using namespace std;
void ShellSort(int *a, int n)
{
    int step = n/2;  //先按增量step n/2,n为要排序数的个数进行希尔排序
    while(step>=1)
    {
        for(int i=step;i<n;i++)
        {
            if(a[i]<a[i-step])
            {
                int temp = a[i];
                int j=i-step;
                for(; j>=0 && temp<a[j]; j=j-step)
                {
                    a[j+step] = a[j];
                }
                a[j+step] = temp;
            }
        }
        step = step/2;
    }
}
void InsertSort(int *a, int n)
{
    for(int i=1; i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            int temp = a[i];
            int j=i-1;
            for(;j>=0 && temp<a[j];j--)
            {
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
}
int main()
{
    int a[9] = {9,1,5,8,3,7,4,6,2};
    int b = sizeof(a)/sizeof(int);
    ShellSort(a,9);
    for(int i=0;i<9;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

感谢各位的阅读，以上就是“C++希尔排序怎么使用”的内容了，经过本文的学习后，相信大家对C++希尔排序怎么使用这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！