希尔排序，也称递减增量排序算法，是插入型誉排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而搏睁提出改进方法的：
插入排序在对几乎已经排好序的数据 *** 作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
1. 算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti >tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2. 动图演示
代码实现 JavaScript 实例function shellSort ( arr ) {
var len = arr. length ,
temp ,
gap = 1
while ( gap 0 gap = Math . floor ( gap / 3 ) ) {
for ( var i = gap i = 0 && arr [ j ] > temp j -= gap ) {
arr [ j + gap ] = arr [ j ]
}
arr [ j + gap ] = temp
}
}
return arr
}
Python 实例def shellSort ( arr ) :
import math
gap = 1
while ( gap 0 :
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 )
return arr
Go 实例func shellSort ( arr [] int ) [] int {
length := len ( arr )
gap := 1
for gap <length / 3 {
gap = gap * 3 + 1
}
for gap > 0 {
for i := gap i <length i ++ {
temp := arr [ i ]
j := i - gap
for j >= 0 &&arr [ j ] >temp {
arr [ j + gap ] = arr [ j ]
j -= gap
}
arr [ j + gap ] = temp
}
gap = gap / 3
}
return arr
}
Java 实例public static void shellSort ( int [ ] arr ) {
int length = arr. length
int temp
for ( int step = length / 2 step >= 1 step /= 2 ) {
for ( int i = step i = 0 && arr [ j ] > temp ) {
arr [ j + step ] = arr [ j ]
j -= step
}
arr [ j + step ] = temp
}
}
}
PHP 实例function shellSort ( $arr )
{
$len = count ( $arr )
$temp = 0
$gap = 1
while ( $gap 0$gap = floor ( $gap / 3 ) ) {
for ( $i = $gap$i = 0 && $arr [ $j ] > $temp$j -= $gap ) {
$arr [ $j + $gap ] = $arr [ $j ]
}
$arr [ $j + $gap ] = $temp
}
}
return $arr
}
C 实例void shell_sort ( int arr [ ] , int len ) {
int gap , i , j
int temp
for ( gap = len >> 1 gap > 0 gap >>= 1 )
for ( i = gap i = 0 && arr [ j ] > temp j -= gap )
arr [ j + gap ] = arr [ j ]
arr [ j + gap ] = temp
}
}
C++ 实例template
void shell_sort ( T array [ ] , int length ) {
int h = 1
while ( h = 1 ) {
for ( int i = h i = h && array [ j ]0) { for (int i = gapi arr.Lengthi++) { int tmp = arr[i] int j = i - gap while (j >= 0 &&arr[j] >tmp) { arr[j + gap] = arr[j] j -= gap } arr[j + gap] = tmp } gap /= 3 } } 以上为希尔排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
网友wang1992092对希尔排序的理解有些错误，希尔排序对每个子序列进行的是直接插入排序，而不是如他所给出的选择排序。你可以先百度一下希尔排序的定义。我这里给一梁塌个C源代码，你可以试试。直接插入排序的思路橡简圆是：将待排表分成两部分，一部分是已有序部分L，另一部分是待排序部分R。L初始化为只含第一个元素的表，因L现在只含一个元素，所以是有序的。然后每次从R中取出最前面的元素到tmp(相当于出队到tmp中)，然后在L中从后向前搜索插入位置，边搜索边向后移动比tmp大的元素，找到了插入位置后就将tmp插入到L中。直到R部分为空时结束。typedef int datatype
void InsertSort(datatype a[], int left, int right, int gap)
/*对数组a中起始下标为left，结束下标为right，步长为gap的子序列进行直接插入咐孙排序，当gap等于1时就是通常的插入排序了*/
{
int tmp, i, j
for(i = left + gapi <= righti += gap){
for(tmp = a[i], j = i - gapj >= left &&a[j] >tmpj -= gap)
a[j + gap] = a[j]
a[j + gap] = tmp
}
}
void ShellSort(datatype a[], int left, int right)
{
int gap = (right - left + 1) / 2, i/*步长gap初始化为n/2取下整*/
while(gap >0)
{
for(i = lefti <gapi++)/*对每个子序列进行直接插入排序*/
InsertSort(a, i, right, gap)
gap = gap / 2 /*将步长缩小为原来的一半并取下整*/
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）