综述
1959年Shell发明,第一个突破O(n^2)的排序算法,是简单插入排序的改进版.它与插入排序的不同之处在于,它会优先比较距离较远的元素.希尔排序又叫缩小增量排序.
算法描述
1.先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
2.选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
3.按增量序列个数k,对序列进行k 趟排序;
4.每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序.仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度.
示意图
希尔排序动态示意图
希尔排序静态示意图
性质
排序类别:交换排序
是否是稳定排序:不稳定
是否是原地排序:是
时间复杂度:最好是O(nlog n), 最坏是O(nlog²n), 所以时间复杂度是O(nlog²n)
空间复杂度:O(1)
解释
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因D.L.Shell于1959年提出而得名.
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止.
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。**
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
比较
希尔排序是基于插入排序的以下两点性质而提出改进方法的:该方法实质上是一种分组插入方法
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率.但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位.
基本思想
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组.所有距离为d1的倍数的记录放在同一个组中.
先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止.
稳定性分析
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的.
时间复杂度分析
最好是O(nlog n), 最坏是O(nlog²n), 所以时间复杂度是O(nlog²n)
Python实现及优化
import math
def shell_sort1(arr=[]):
if len(arr) < 2:
return arr
gap = math.floor(len(arr) / 2)
while gap > 0:
print('now gap is :', gap)
for i in range(gap, len(arr)):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
print('本次进行排列的结果是:', arr)
gap = math.floor(gap / 2)
return arr
dest = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
result = shell_sort1(dest)
print('最后的结果是:', result)
'''
now gap is : 5
本次进行排列的结果是: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
now gap is : 2
本次进行排列的结果是: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
now gap is : 1
本次进行排列的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最后的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''
"""
优化方式一
算法的性能不仅取决于 h ， 还取决于 h 之间的数学性质，比如它们的公因子等。
使用递增序列 1、4、13、40、121、364… 的希尔排序所需的比较次数不会超过 N 的若干倍乘以递增序列的长度。
"""
def shell_sort2(arr=[]):
if len(arr) < 2:
return arr
gap = 1
while gap < len(arr) / 3:
gap = gap * 3 + 1
while gap > 0:
print('now gap is:', gap)
for i in range(gap, len(arr)):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = math.floor(gap / 3)
print('本次进行排列的结果是:', arr)
return arr
dest = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
result = shell_sort2(dest)
print('最后的结果是:', result)
'''
now gap is: 4
本次进行排列的结果是: [2, 0, 1, 4, 6, 3, 5, 7, 8, 9]
now gap is: 1
本次进行排列的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最后的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''
"""
优化方式二
因为是基于插入排序的，所以可以使用其插入排序及其优化中给出的优化方案。
即：进行了预处理操作，并在内循环中，总是将较大的元素向右移动。原方案是交换。
"""
def shell_sort3(arr=[]):
if len(arr) < 2:
return arr
gap = 1
while gap < len(arr) / 3:
gap = gap * 3 + 1
print('start gap is:', gap)
length = len(arr)
exchanges = 0 # 交换次数
# 若arr[i] < arr[i - 1]，则交换两数
for i in range(length - 1, 0, -1):
if arr[i] < arr[i - 1]:
arr[i], arr[i - 1] = arr[i - 1], arr[i]
exchanges += 1
# 若交换次数为0（即数组有序），则无需进行下一步排序。
if exchanges == 0:
return arr
while gap > 0:
print('now gap is:', gap)
for i in range(gap, len(arr)):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = math.floor(gap / 3)
print('本次进行排列的结果是:', arr)
print('交换的次数是:', exchanges)
return arr
dest = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
result = shell_sort3(dest)
print('最后的结果是:', result)
'''
start gap is: 4
now gap is: 4
本次进行排列的结果是: [0, 2, 3, 1, 4, 6, 9, 5, 7, 8]
now gap is: 1
本次进行排列的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
交换的次数是: 9
最后的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''
C语言实现及优化
#include<stdio.h>
void shell_sort1(int arr[], int len)
{
int gap = len / 2;
while(gap>0)
{
for(int i=gap;i<len;i++)
{
int temp = arr[i];
int j = i - gap;
while(j>=0 && arr[j] > temp)
{
arr[j+gap] = arr[j];
j -= gap;
}
arr[j+gap] = temp;
}
gap = gap / 2;
}
}
/*
优化方式一
算法的性能不仅取决于 h , 还取决于 h 之间的数学性质,比如它们的公因子等.
使用递增序列 1、4、13、40、121、364… 的希尔排序所需的比较次数不会超过 N 的若干倍乘以递增序列的长度.
*/
void shell_sort2(int arr[], int len)
{
int gap = 1;
if(gap < len / 3)
gap = gap * 3 + 1;
while(gap>0)
{
for(int i=gap;i<len;i++)
{
int temp = arr[i];
int j = i - gap;
while(j>=0 && arr[j] > temp)
{
arr[j+gap] = arr[j];
j -= gap;
}
arr[j+gap] = temp;
}
gap = gap / 3;
}
}
/*
优化方式二
因为是基于插入排序的,所以可以使用其插入排序及其优化中给出的优化方案.
即:进行了预处理操作,并在内循环中,总是将较大的元素向右移动.原方案是交换.
*/
void shell_sort3(int arr[], int len)
{
int length = len;
int h = 1;
int temp;
while (h < length / 3)
{
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093...
}
int exchanges = 0; //交换次数
//若 arr[index] < arr[index - 1],则交换两数
for (int index = length - 1; index > 0; index--)
{
if (arr[index] < arr[index - 1])
{
int temp = arr[index];
arr[index] = arr[index-1];
arr[index-1] = temp;
exchanges++;
}
}
//若交换次数为0(即数组有序),则无需进行下一步排序.
if (exchanges == 0) return;
//若有交换次数,表明目前的数组无序.
while (h >= 1) {
// 将数组变为 h 有序
for (int indexI = h; indexI < length; indexI++) {
temp = arr[indexI]; //记录一下arr[indexI]的值
int indexJ = indexI; //indexI 的代替品
//若 indexJ 的前 h 位元素小于 temp,则将小于temp的元素向右移动 h 位
//需要注意:可能会出现 indexJ < h 的情况.而一般的插入排序不会出现.
while (indexJ >= h && temp < arr[indexJ - h])
{
arr[indexJ] = arr[indexJ - h];
indexJ -= h;
}
arr[indexJ] = temp; //将记录的值放在 indexJ 的位置上
}
h = h / 3;
}
}
int main()
{
// int dest1[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
// shell_sort1(dest1, 10);
// for(int i=0;i<10;i++)
// printf("%d ", dest1[i]);
// printf("\n");
//
// int dest2[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
// shell_sort2(dest2, 10);
// for(int i=0;i<10;i++)
// printf("%d ", dest2[i]);
// printf("\n");
int dest3[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shell_sort3(dest3, 10);
for(int i=0;i<10;i++)
printf("%d ", dest3[i]);
printf("\n");
return 0;
}
网友评论