希尔排序
- 时间复杂度：平均O(n^1.3),最好为O(n),最坏为0(n ^ 2)
- 空间复杂度：O(1)
- 稳定性：不稳定
算法解析：
- 希尔排序是直接插入排序的一种改进，又称做缩小增量排序
- 希尔排序是把待排序集合计算出一个增量集合Tn
- 把待排序集合分成若干个子集，然后每个子集进行直接插入排序，知道Ti=1为止，排序结束
- 遍历次数为增量集合的count数
举例
有一个集合如下图所示：
list.png
计算增量：gap = length/2
-
第一次：gap = 4，把待排序列划分为4个子序列
第一次.png -
第二次 ：gap = 2，把待排序列划分为2个子序列
第二次.png 第三次：gap = 1，进行一次直接插入排序，排序结束
排序结果：
第一次：7 3 1 2 8 5 4 10 9
第二次：1 2 4 3 7 5 8 10 9
第三次：1 2 3 4 5 7 8 9 10
C语言实现
void shellSort(int arr[],int length) {
int gap;//间距or增量
for (gap = length/2; gap>0; gap/=2) { //gap->1 共分几次
for (int i=gap; i<length; i++) {//从gap个元素开始，直接插入排序
if (arr[i] < arr[i-gap]) {
int tmp = arr[i];
int k = i-gap;
while (k>=0 && arr[k] > tmp) {
arr[k+gap] = arr[k];
k-=gap;
}
arr[k+gap] = tmp;
}
}
}
}
OC实现
- (NSArray *)shellSort:(NSMutableArray *)arr {
int length = arr.count;
int gap;
for (gap = length/2; gap>0; gap/=2) {
for (int i = gap; i < length; i++) {
if ([arr[i] intValue] < [arr[i-gap] intValue]) {
NSNumber *tmp = arr[i];
int k = i-gap;
while (k>=0 && [arr[k] intValue] > tmp.intValue) {
arr[k+gap] = arr[k];
k-=gap;
}
arr[k+gap] = tmp;
}
}
}
return arr.copy;
}
以下实现来源于网络，未验证
c++实现
void shell_sort(const int start, const int end) {
int increment = end - start + 1; //初始化划分增量
int temp{ 0 };
do { //每次减小增量，直到increment = 1
increment = increment / 3 + 1;
for (int i = start + increment; i <= end; ++i) { //对每个划分进行直接插入排序
if (numbers[i - increment] > numbers[i]) {
temp = numbers[i];
int j = i - increment;
do { //移动元素并寻找位置
numbers[j + increment] = numbers[j];
j -= increment;
} while (j >= start && numbers[j] > temp);
numbers[j + increment] = temp; //插入元素
}
}
} while (increment > 1);
}
js实现
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 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 < len(arr)/3):
gap = gap*3+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 < gap/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 class ShellSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
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 = (int) Math.floor(gap / 3);
}
return arr;
}
}
PHP 代码实现
function shellSort($arr)
{
$len = count($arr);
$temp = 0;
$gap = 1;
while($gap < $len / 3) {
$gap = $gap * 3 + 1;
}
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
for ($i = $gap; $i < $len; $i++) {
$temp = $arr[$i];
for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
$arr[$j+$gap] = $arr[$j];
}
$arr[$j+$gap] = $temp;
}
}
return $arr;
}
