Notes.

常见排序算法的 C 语言和 JavaSript 实现之「希尔排序」

2016-02-14 • ☕️ 1 min read

上面我们介绍了在速度上比较慢的插入排序，现在我们来介绍一种在速度上秒杀插入排序的排序算法——希尔排序。

希尔排序

算法描述

希尔排序也成为增量排序。希尔排序使用一个序列 $\\{h_1, h_2, h_3, … h_t\\}$ ，叫增量序列。只要 $h_1 = 1$ ，任何增量序列都是可以的。在使用增量 $h_k$ 的一趟排序后，对于每一个 $i$ 我们有 $A[i] \leq A[i + h_k]$ （A 为待排序的数组），所有相隔 $h_k$ 的元素都将被排序，此时称其为hk-排序的。希尔排序的一个重要性质是：一个 $h_k$ 排序的文件将保持它的h_k 排序性，也就是说经 $h_{k-1}$ 排序后，任然满足 $A[i] \leq A[i + h_k]$ 。

算法时间复杂度

依据所选择的增量序列的不同，算法的时间复杂度也有所不同。对于 shell 本人推荐的 $ht = N / 2， hk = h_{k+1} / 2$ 增量序列来说，时间复杂度为： $O(N ^ {\frac{3}{2}})$ 。

C 语言实现

int * shell_sort(int * data, int num){
	int i, j, increment, temp;
	for(increment = num / 2; increment > 0 ; increment = increment / 2){
		for(i = increment; i < num; i ++){
			temp = data[i];
			for(j = i; j >= increment; j -= increment){
				if(temp < data[j - increment])
					data[j] = data[j - increment];
				else
					break;
			}

			data[j] = temp;
		}  
	}
	return data;
}

JavaScript 实现

function shell_sort(data) {
    var increment = Math.floor((data.length / 2));
    var temp;
    for (; increment > 0; increment =  Math.floor((increment / 2))) {
        for (var i = increment; i < data.length; i ++) {
            temp = data[i];
            for(var j = i; j >= increment; j -= increment) {
                if(temp < data[j - increment]) {
                    data[j] = data[j - increment];
                } else {
                    break;
                }
            }
            data[j] = temp;
        }
    }
}

性能横向测试

测试平台和代码上篇已经介绍过了，这里就不赘述了，直接给出测试结果。

C 语言希尔排序 JavaScript 语言希尔排序

Personal blog by Natumsol.
Note thoughts and experience.