C++实现希尔排序算法实例

2024-07-28 14:32:28

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++实现希尔排序算法实例的文章就介绍到这了,更多相关C++希尔排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t
C++ 算法之希尔排序详解及实例

C++ 算法之希尔排序算法详解及实例希尔排序算法定义: 希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 算法思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止. 时间复杂度: O(N) 空间复杂度: O(1) 性能: 希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的
C++实现希尔排序（ShellSort）

本文实例为大家分享了C++实现希尔排序的具体代码,供大家参考,具体内容如下一.思路: 希尔排序:又称缩小增量排序,是一种改进的插入排序算法,是不稳定的. 设排序元素序列有n个元素,首先取一个整数gap<n作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.然后缩小间隔gap,重复上述的子序列和排序工作. 二.实现程序: #include <iostream> using namespace std; const int
C++实现简单的希尔排序Shell Sort实例

本文以实例形式讲述了基于C++实现简单的希尔排序Shell Sort的方法,是一个很经典的算法,具体实现代码如下: #include <iostream> using namespace std; void ShellSort(int* iArray,int length) { //初始化jump等于length int jump = length; //标记本趟检测是否进行了交换, // 若进行了则还有下次从头开始的检测, // 否则停止,继续改变jump的值做另一趟排序 bool is
C++实现希尔排序算法实例

目录 1.代码模板 2.算法介绍 3.实例 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] <
python实现的希尔排序算法实例

本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc] j -= inc items[j] = temp inc = inc/2
java 中基本算法之希尔排序的实例详解

java 中基本算法之希尔排序的实例详解希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL．Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差
Python实现希尔排序算法的原理与用法实例分析

本文实例讲述了Python实现希尔排序算法的原理与用法.分享给大家供大家参考,具体如下: 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高
php实现希尔排序算法的方法分析

本文实例讲述了php实现希尔排序算法的方法.分享给大家供大家参考,具体如下: 虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法. 理解这些复杂的排序算法还是很有意思的,体会这些排序算法的精妙~ 希尔排序(shell sort):希尔排序是基于插入排序的,区别在于插入排序是相邻的一个个比较(类似于希尔中h=1的情形),而希尔排序是距离h的比较和替换. 希尔排序中一个常数因子n,原数组被分成各个小组,每个小组由h个元素组成,很可能会有多余的元素.当然
c语言5个常用的排序算法实例代码

1.插入排序基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =
java实现希尔排序算法

希尔排序算法的基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<d1),即所有记录放在同一组中进行直接插入排序为止.该方法实质上是一种分组插入方法. //带增量的插入排序 public static void shellSort(int[] array) { int len =
使用Java实现希尔排序算法的简单示例

简介希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量. 常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生: h = 3 * h +1 反过来程序需要反向计算h序列,应该使用 h=(h
Java 插入排序之希尔排序的实例

Java 插入排序之希尔排序的实例 Java代码 /*希尔排序(Shell Sort)是插入排序的一种.其基本思想是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1 * 个组,所有距离为d1的倍数的记录放在同一个组中,在各个组中进行插入排序:然后,取第二个增量d2<d1,重复上述的分组和排序, * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止. * new int[]{8,5,1,7,9,4,6}
Java的Arrays.sort()方法排序算法实例分析

暂时网上看过很多JDK8中Arrays.sort的底层原理,有些说是插入排序,有些说是归并排序,也有说大于域值用计数排序法,否则就使用插入排序...其实不全对.让我们分析个究竟: // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } 数组一进来,会碰到第一个阀值QUICK

C++实现希尔排序算法实例

目录

1.代码模板

2.算法介绍

3.实例

相关推荐

随机推荐