欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

希尔排序

程序员文章站 2022-06-04 17:54:12
...
#include<iostream>
using namespace std;

void shell_sort(int arr[], int len) {
    int increment, i, j;
    increment = len;
    do {
        increment = increment / 3 + 1;  //当 increment = 10 / 3 + 1 = 4时, 意味着数组被分成4组,且最后一个增量必须为1             
        for (i = increment; i < len; i++) {
            int temp = arr[i];
            //每组内分别进行直接插入排序
            for (j = i - increment; j >= 0 && temp < arr[j]; j = j - increment) {
                arr[j + increment] = arr[j];
            }           
            arr[j + increment] = temp;
        }
    } while (increment > 1);
}



int main()
{
    int arr[10] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    shell_sort(arr, 10);
    for (int i = 0; i < 10; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

希尔排序

注意:
内层for循环的准确意义
希尔排序

性能分析:
其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2),其下界为nlogn
存储空间:O(1)
稳定性分析:因为排序过程中元素可能会前后跳跃,所以不稳定。

https://www.cnblogs.com/chengxiao/p/6104371.html

相关标签: 希尔排序

上一篇: 希尔排序

下一篇: 希尔排序