Fancy DSA Fancy DSA
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)

Jonsam NG

想的更多,也要想的更远
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)
  • 开始上手
  • Plan 计划
  • Roadmap 路线
  • 算法简介
  • Sort 排序

    • 章节概要
    • AlphaNumericalSort [字母顺序排序]
    • BeadSort [珠排序]
    • BogoSort [Bogo 排序]
    • BubbleSort [冒泡排序]
    • BucketSort [桶排序]
    • CocktailShakerSort [鸡尾酒排序]
    • CombSort [梳排序]
      • 介绍
      • 原理
      • 复杂度
      • 实现
      • 参考
    • CountingSort [计数排序]
    • CycleSort [圈排序]
    • FisherYatesShuffle [洗牌算法]
    • FlashSort [闪电排序]
    • GnomeSort [侏儒排序]
    • HeapSort [堆排序]
    • InsertionSort [插入排序]
    • IntroSort [内省排序]
    • MergeSort [归并排序]
    • OddEvenSort [奇偶排序]
    • PancakeSort [煎饼排序]
    • PigeonHoleSort [鸽巢排序]
    • QuickSort [快速排序]
    • RadixSort [基数排序]
    • SelectionSort [选择排序]
    • ShellSort [希尔排序]
    • TimSort [Tim 排序]
    • TopologicalSorter [拓扑排序器]
    • WiggleSort [摆动排序]
  • Search 搜索

  • Recursive 递归

  • Graph 图

  • Tree 树

  • Math 数学

  • Hash 哈希

  • String 字符串

  • BitManipulation 位操纵

  • Backtracking 回溯

  • DynamicProgramming 动态规划

  • Cache 缓存

  • Array 数组

  • Ciphers 密码学

  • Conversions 转换

  • ProjectEuler 欧拉计划

  • 其他

  • 算法
  • Sort 排序
jonsam
2022-04-26
目录

CombSort [梳排序]

# 介绍

梳排序是改良自冒泡排序和快速排序,其要旨在于消除乌龟,亦即在数组尾部的小数值,这些数值是造成冒泡排序缓慢的主因。相对地,兔子,亦即在数组前端的大数值,不影响冒泡排序的性能。

# 原理

在冒泡排序中,只比较数组中相邻的二项,即比较的二项的间距(Gap)是 1,梳排序提出此间距其实可大于 1,改自插入排序的希尔排序同样提出相同观点。梳排序中,开始时的间距设置为数组长度,并在循环中以固定比率递减,通常递减率设置为 1.3。在一次循环中,梳排序如同冒泡排序一样把数组从首到尾扫描一次,比较及交换两项,不同的是两项的间距不固定于 1。如果间距递减至 1,梳排序假定输入数组大致排序好,并以冒泡排序作最后检查及修正。

CombSort

# 递减率

递减率的设置影响着梳排序的效率,原作者以随机数作实验,得到最有效递减率为 1.3 的。如果此比率太小,则导致一循环中有过多的比较,如果比率太大,则未能有效消除数组中的乌龟。

# 复杂度

  • 平均时间复杂度 Ω(n2/2p){\displaystyle \Omega (n^{2}/2^{p})}Ω(n2/2p),其中 p 表示增量。
  • 最坏时间复杂度Ω(n2)\Omega (n^{2})Ω(n2)。
  • 最优时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)。
  • 空间复杂度O(1)O(1)O(1)。

# 实现

# JavaScript

/**
 * Comb sort improves on bubble sort.
 *
 * The basic idea is to eliminate turtles, or small values
 * near the end of the list, since in a bubble sort these slow the sorting
 * down tremendously. Rabbits, large values around the beginning of the list,
 * do not pose a problem in bubble sort.
 *
 * In bubble sort, when any two elements are compared, they always have a
 * gap (distance from each other) of 1. The basic idea of comb sort is
 * that the gap can be much more than 1. The inner loop of bubble sort,
 * which does the actual swap, is modified such that gap between swapped
 * elements goes down (for each iteration of outer loop) in steps of
 * a "shrink factor" k: [ n/k, n/k2, n/k3, ..., 1 ].
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Comb_sort
 */

/**
 * combSort returns an array of numbers sorted in increasing order.
 *
 * @param {number[]} list The array of numbers to sort.
 * @return {number[]} The array of numbers sorted in increasing order.
 */
function combSort (list) {
  if (list.length === 0) {
    return list
  }
  const shrink = 1.3
  let gap = list.length
  let isSwapped = true
  let i = 0

  while (gap > 1 || isSwapped) {
    // Update the gap value for a next comb
    gap = parseInt(parseFloat(gap) / shrink, 10)

    isSwapped = false
    i = 0

    while (gap + i < list.length) {
      if (list[i] > list[i + gap]) {
        [list[i], list[i + gap]] = [list[i + gap], list[i]]
        isSwapped = true
      }
      i += 1
    }
  }
  return list
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 参考

  • 梳排序 - 维基百科,自由的百科全书 (opens new window)
编辑 (opens new window)
上次更新: 2022/04/28, 22:42:49
CocktailShakerSort [鸡尾酒排序]
CountingSort [计数排序]

← CocktailShakerSort [鸡尾酒排序] CountingSort [计数排序]→

最近更新
01
0-20题解
10-31
02
本章导读
10-31
03
算法与转换:Part1
10-28
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Fancy DSA | Made by Jonsam by ❤
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式