希尔排序属于插入排序的一种,也称为缩小增量排序
基本思想:
将待排序数列划分为几个数列,对这几个数列分别进行直接插入排序
具体操作:
选取增量d(小于数列长度n),将数列划分为n/d个数列,对划分的数列进行直接插入排序
再选取一个增量d1,d1<d,重复上述步骤
直到dn = 1结束
取d=5
23 52 12 63 8 17 28 72 36 41
----------------------------------------------
23 17
|_______________________|
52 28
|_______________________|
12 72
|_______________________|
63 36
|_______________________|
8 41
|_______________________|
一趟排序结果:
17 28 12 36 8 23 52 72 63 41
----------------------------------------------
取d=2
17 12 8 52 63
|_________|________|_________|_________|
28 36 23 72 41
|________|_________|________|_________|
二趟排序结果:
8 23 12 28 17 36 52 41 63 72
---------------------------------------------
取d=1
三趟排序结果:
8 12 17 23 28 36 41 52 63 72
时间复杂度:
很难判断准确的时间复杂度,这和选择的增量d有关系
最坏情况和平均情况一样:O(n*log(n))
稳定性:
一次插入排序是稳定的,但是希尔排序是多次插入,在不同的插入排序过程中,相同元素在各自的插入排序中位置可能会变更,所以是不稳定排序
python代码示例:shell_sort.py
def shell_sort(l):
length = len(l)
d = length/2 #起始增量d选取为数列的一半
while(d >= 1):
for i in range(d, length): #对l[d...n-1]分别插入各组有序子序列中
j = i - d
while(j >= 0 and l[j] > l[j+d]): #距离增量d的两个元素比较
tmp = l[j]
l[j] = l[j+d]
l[j+d] = tmp
j -= d #以d为增量,继续循环比较该子序列内的元素
d = d/2 #下一增量选取
if __name__ == '__main__':
l = [93,102,36,82,76,84,55,63,49,27]
shell_sort(l)
print('result:' + str(l)
lua代码示例:shell_sort.lua
require "math"
function shell_sort(t)
length = table.getn(t)
d = math:floor(lenght/2)
while(d >= 1) do
for i = d+1, length do --对t[d...n-1]分别插入各组有序子序列中
j = i - d
while(j > 0 and t[j] > t[j+d]) do
tmp = t[j]
t[j] = t[j+d]
t[j+d] = tmp
j = j - d
end
end
d = math:floor(d/2)
end
end
t = {93,102,36,82,76,84,55,63,49,27}
shell_sort(t)
for _, v in ipairs(t) do
print v
end
分享到:
相关推荐
C#算法 -- (三)希尔排序 朋友们,我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序....希尔排序是将组分段,进行插入排序. 对想提高C#语言编程能力的朋友,我们可以互相探讨一下。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
有选择排序,冒泡排序,希尔排序,插入排序,归并排序算法
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort...插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
快速排序 希尔排序 插入排序 折半排序算法
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht