希尔排序

希尔排序是插入排序的改良版本，参考希尔排序

算法步骤

每隔一个gap 进行分组，然后对分组内部进行排序，选择插入排序
缩小 gap，继续排序，直到 gap =1，此时这个数列大体上已经是有序的，最后一次执行插入排序

可以看到，每一次分组执行，都将组内进行排序，使得小的值排在前面，大的值排在了后面

复杂度分析：

时间复杂度：O(nlogn) - O(n^2)
空间复杂度：O(1)

代码

Array.prototype.shellSort = function () {
	let arr = this.slice(0);
	var len = arr.length;
	var gap;
	var i, j;
	var temp;

	// 按照gap分组
	for (gap = len >> 1; gap > 0; gap >>= 1) {
		console.log({ gap });
		// 组内插入排序
		for (var 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;
};

var a = [
	3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7,
	4, 0, 2, 6,
];

console.log(a.shellSort());

python 代码

def shellSort(self, nums):
    length = len(nums)
    gap = length // 2

    while gap > 0:
      # 这里从gap开始，直到最后一个元素，执行插入排序
      # 可能会说，为什么不这样选择 [0， gap, 2gap, 3gap], [1， gap+1, 2gap+1, ...], [2， gap+2, 2gap+2, ...] 等数列进行编写代码
      # 这样也可以不过需要算出每个分组内部是什么样的
      # 现在直接从 gap 开始，每个元素都与前面的有序数列进行插入排序操作，不会有遗漏的数据
      for i in range(gap, length):
        num = nums[i]
        j = i

        while j >= gap and nums[j-gap] > num:
          nums[j] = nums[j-gap]
          j -= gap

        nums[j] = num

      gap = gap // 2

    return  nums

希尔排序 ​

算法步骤 ​

代码 ​

希尔排序

算法步骤

代码