C++如何实现希尔排序算法

这篇“C++如何实现希尔排序算法”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++如何实现希尔排序算法”文章吧。

1.代码模板

// 希尔排序（Shell Sort）void ShellSort(SqList *L){    int i, j;    int increment = L->length;  // 先让增量初始化为序列的长度    do {        increment = increment / 3 + 1;   // 计算增量的值        for (i = increment + 1; i <= L->length; i ++ ) {             if (L->arr[i] < L->arr[i - increment]) {   // 如果L->[i]需要插入有序增量子表                L->arr[0] = L->arr[i];   // 暂存在哨兵位                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment) {  // 遍历增量子表，寻找插入位置                    L->arr[j + increment] = L->arr[j];                }                L->arr[j+increment] = L->arr[0];  // 插入            }        }    } while (increment > 1);}

2.算法介绍

希尔排序，又叫缩小增量排序，算法属于插入类排序的进阶算法，采取跳跃分割的策略，将关键字较小的元素跳跃式的往前挪，大大减小了交换比较的次数。使得序列整体基本有序 ，即大的元素基本在后面，小的元素基本在前面，不大不小的元素基本在中间。

希尔排序的关键在于将序列中相隔某个“增量”的元素组成一个子序列，且序列的最后一个增量必须为1，这样才能保证最后的结果是有序且正确的。但增量如何选择为最佳，至今仍无定论。且由于元素是跳跃式移动的，所有希尔排序是一个不稳定的排序算法，其时间复杂度受到增量选择的影响，最好为O(n^1.3) , 最坏为O(n*n)。

3.实例

#include <iostream>using namespace std;const int N = 100;typedef struct{    int arr[N];    // 存储待排序的序列    int length;    // 存储序列的长度} SqList;void ShellSort(SqList *L){    int i, j;    int increment = L->length;    do {        increment = increment / 3 + 1;        for (i = increment + 1; i <= L->length; i ++ ) {            if (L->arr[i] < L->arr[i - increment]) {                L->arr[0] = L->arr[i];                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment)                    L->arr[j + increment] = L->arr[j];                L->arr[j + increment] = L->arr[0];            }        }    } while (increment > 1);}int main(){    SqList L;    L.arr[1] = 50;    L.arr[2] = 10;    L.arr[3] = 90;    L.arr[4] = 30;    L.arr[5] = 70;    L.arr[6] = 40;    L.arr[7] = 80;    L.arr[8] = 60;    L.arr[9] = 20;    L.length = 9;    ShellSort(&L);    for (int i = 1; i <= L.length; i ++ )        cout << L.arr[i] << " ";}

以上就是关于“C++如何实现希尔排序算法”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网行业资讯频道。