排序算法-希尔排序

深藏阁楼爱情的钟 2023-06-13 11:22 3阅读 0赞

> **1.希尔排序**

将待排序数组按照步长进行分组，然后将每组的元素利用直接插入排序的方法进行排序，每次将步长折半减小，gap=1时，利用直接插入完成排序。

1）第一层循环将gap依次折半，对序列进行分组直到gap=1；

2）第二、三层循环利用**直接插入排序**的两次循环

> **2.图例**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70][]

> ** 3.算法**

//希尔排序
    void shellSort(int *arr, int num)
    {
        // 9,1,2,5,7,4,8,6,3,5进行排序  第一次gap = 5;
        for (int gap = num/2;gap > 0;gap /= 2)
        {
            for (int i = gap;i < num;i++)
            {
                //进行分组插入排序，gab = 5时，arr[i]和arr[gap+i]比较
                for (int j = i; j - gap >= 0 && arr[j - gap] > arr[j]; j -= gap)
                {
                    //交换
                    swap(arr[j - gap], arr[j]);
                }
            }
        }
    }
    
    void printArr(int *arr, int num)
    {
        for (int i = 0;i < num;i++)
        {
            cout << arr[i] << " ";
        }
    }
    
    int main()
    {
        int a[] = { 9,1,2,0,5,7,4,8,6,3,5 };
    
        cout << "排序前: " << endl;
        printArr(a, 11);
        shellSort(a, 11);
        cout << "\n";
        cout << "排序后: " << endl;
        printArr(a, 11);
        return 0;
    }

> **4.运行截图 **

![20191117115751198.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019111711415641.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw==,size_16,color_FFFFFF,t_70
[20191117115751198.png]: https://img-blog.csdnimg.cn/20191117115751198.png