前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >希尔排序

希尔排序

作者头像
hotarugali
发布2022-03-01 16:24:04
1850
发布2022-03-01 16:24:04
举报

1. 简介

希尔排序又称缩小增量排序,其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法,希尔排序在时间效率上更加优秀。

2. 思想

对于普通的插入算法,其时间复杂度为 O(n^2),且在序列有序时,可以达到最好的时间复杂度 O(n);而且当 nnn 较小时,由于移动的元素较少,插入排序效率也比较高。

因此,我们可以采用分治的思想,先将整个待排序序列分割成为若干个子序列分别进行插入排序,待整个序列「基本有序」时再对全体进行插入排序,即自底向上实现整个序列的排序。

【注】这里的子序列不是简单的逐段分割,而是将相隔某个增量的元素组成一个子序列,这样对子序列进行插入排序时,元素就不是一步一步移动,而是跳跃式地往前移。

3. 伪代码

代码语言:javascript
复制
ShellSort(A, D) {
    // 按增量序列 D 对数组 A 进行希尔排序
    for i = 1 to D.length
        //  以下类比与一般的插入排序,增量为 D[i] 而不是 1 
        for j = D[i] + 1 to A.length
            key = A[j]
            k = j - D[i]
            while k > 0 and A[k] > key
                A[k+D[i]] = A[k]
                k = k - D[i]
            A[k+D[i]] = key
}

其中,数组 D 为增量序列。常用的增量序列有:

  • D[k] = 2 \lfloor {n \over 2^{k+1}} \rfloor + 1 , \ \ 0 \lt k \leq t = \lfloor \log_2 n \rfloor 希尔排序时间复杂度 O(n^{1.5})
  • D[k] = 2^{t - k} - 1 , \ \ 0 \leq k \lt t = \lfloor \log_2 (n+1) \rfloor 希尔排序时间复杂度 O(n^{1.5})
  • D[k] = \lfloor 2^{t - k} + 1 \rfloor, \ \ 0 \leq k \leq t+1, \ \ t = \lfloor \log_2 (n-1) \rfloor 希尔排序时间复杂度 O(n^{1.5})
  • D[k] = \lfloor {3^{t - k} - 1 \over 2} \rfloor, \ \ 0 \leq k \lt t = \lfloor \log_3 (2n+1) \rfloor 希尔排序时间复杂度 O(n^{1.5})
  • D[k] = \lfloor {3^{t - k} - 1 \over 2} \rfloor, \ \ 0 \leq k \lt t = \lfloor \log_3 (2n+1) \rfloor 希尔排序时间复杂度 O(n^{1.5})
  • D[k] = \begin{cases} 1, & \ \ k = t \\ 4^{t-k} + 3 \cdot 2^{t-k-1} + 1, & \ \ 0 \leq k \lt t \\ \end{cases} , \ \ t = \lfloor \log_2 (\sqrt{9+16(n-1)} - 3) - 2 \rfloor 希尔排序时间复杂度 O(n^{4 \over 3})
  • D[k] = 2^i 3^j, \ \ 0 \lt 2^i 3^j \leq n i,ji, 递减到 0(即连续递减到 1 的光滑数 2^p 3^q) 希尔排序时间复杂度 O(n \log^2 n)

希尔排序是不稳定的、原址的。不稳定原因在于希尔排序中不同段交换元素时会打乱相等元素初始的相对位置。

4. 模板

代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;

#ifndef _SHELLSORT_
#define _SHELLSORT_
#define ll int

// 比较元素
template < typename T >
bool compare(const T & a, const T & b)  { return a < b; }
// 希尔排序

template < typename T >
void shellSort(T *bA, T *eA, ll *bD, ll *eD, bool (*cmp)(const T & a, const T & b) = compare) {
    ll len_A = eA - bA;
    ll len_D = eD - bD;
    T *A = bA;
    ll *D = bD;
    // 按增量序列 D 对数组 A 进行希尔排序
    for(ll i = 0; i < len_D; ++i) {
        //  以下类比与一般的插入排序,增量为 D[i] 而不是 1 
        for(ll j = D[i]; j < len_A; ++j) {
            T key = A[j];
            ll k = j - D[i];
            while(~k && compare(key, A[k])) {
                A[k+D[i]] = A[k];
                k = k - D[i];
            }
            A[k+D[i]] = key;
        }
    }
}
#endif
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 简介
  • 2. 思想
  • 3. 伪代码
  • 4. 模板
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档