C/C++教程

考研数据结构编程 ch08排序 —— 希尔排序

本文主要是介绍考研数据结构编程 ch08排序 —— 希尔排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

希尔排序


一、算法思想 (按递增排序)

  • 1、关键
    • ① 将数据根据 增量(步长)d,划分成若干个更差数列,每一个等差数列相当于一个子表。
    • ② 第i子表:(a[i],a[i+d],a[i+2d]);i的取值范围: [1,d]。
    • ③ 当步长d为1时,希尔排序就变成了直接插入排序。
  • 2、注意!a[0]比较特殊。
  • 3、在划分完子表之后,对各个子表进行直接插入排序。
  • 4、增量d会改变,d=d/2,每轮循环d变成原来的二分之一,知道d为1。
// ! 希尔排序
void ShellSort(int arrList[], int n)
{
    int i, j, d;
    // ! 注意,此时a[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到
    for (d = n / 2; d >= 1; d /= 2) // ! 增量d改变
    {
        // ! 每一轮,让增量d去划分子表,比如: (a[1], a[1+d], a[1+2d], ...)
        // ! 每一子表里,使用直接插入排序
        for (i = d + 1; i <= n; i++) // ! 直接插入排序就是从第2个元素开始遍历的
        {
            if (arrList[i] < arrList[i - d]) // ! 将a[i]插入有序增量子表
            {
                arrList[0] = arrList[i];
                for (j = i - d; j > 0 && arrList[j] > arrList[0]; j -= d)
                {
                    arrList[j + d] = arrList[j];
                }
                arrList[j + d] = arrList[0];
            }
        }
    }
}

二、具体测试代码

#include <iostream>

using namespace std;

// ! 希尔排序
void ShellSort(int arrList[], int n)
{
    int i, j, d;
    // ! 注意,此时a[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到
    for (d = n / 2; d >= 1; d /= 2) // ! 增量d改变
    {
        // ! 每一轮,让增量d去划分子表,比如: (a[1], a[1+d], a[1+2d], ...)
        // ! 每一子表里,使用直接插入排序
        for (i = d + 1; i <= n; i++) // ! 直接插入排序就是从第2个元素开始遍历的
        {
            if (arrList[i] < arrList[i - d]) // ! 将a[i]插入有序增量子表
            {
                arrList[0] = arrList[i];
                for (j = i - d; j > 0 && arrList[j] > arrList[0]; j -= d)
                {
                    arrList[j + d] = arrList[j];
                }
                arrList[j + d] = arrList[0];
            }
        }
    }
}

int main()
{
    int a[] = {0, 38, 49, 65, 97, 76, 13, 27, 49};
    ShellSort(a, 8);
    cout << "数组的元素个数: " << sizeof(a) / 4 << endl;
    for (int i = 0; i <= 8; i++)
    {
        cout << "a[" << i << "]: " << a[i] << "  ";
    }
    return 0;
}
这篇关于考研数据结构编程 ch08排序 —— 希尔排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!