MENU

希尔排序

• August 4, 2022 • Read: 94 • 学习笔记,数据结构

最近在全面学习数据结构,常用算法记录:希尔排序,基本思想是选定一个增量 $d<n$,将元素按此增量分组(所有相距 $d$ 的元素为一组),然后在各个子序列内进行插入排序,完成后缩小增量 $d'(d'<d)$,如此反复操作,直到增量 $d = 1$ 为止,此时就成了标准的插入排序,但此时大部分元素已经有序,只需要少量操作,甚至不用操作即可完成排序。该排序算法为不稳定排序。

希尔排序还是比较绕的,需要多看看,多画一画。

最坏时间复杂度:$O(n^2)$
$n$ 在某范围内可达:$O(n^{1.3})$
目前无法用数学手段证明确切的时间复杂度。

#include <iostream>

using namespace std;

void shellSort(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    shellSort(arr, length);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

void shellSort(int arr[], int n)
{
    int d, i, j;
    //arr[0]为暂存单元
    for (d = n / 2; d > 0; d /= 2)  //d为步长
    {
        for (i = d + 1; i <= n; i++)    //从子表中第二个元素开始
            if(arr[i] < arr[i - d])     //小于子序列前一项
            {
                arr[0] = arr[i];    //暂存待插入元素
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];    //向后移动,为待插入元素腾出空位
                arr[j + d] = arr[0];    //插入暂存元素
            }
    }
}

image.png


版权属于:字节星球 (转载请联系作者授权)
原文链接:https://www.bytecho.net/archives/2087.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment