直接插入排序和希尔排序

在学ruby，正好顺便把排序算法都复习一遍，先来看直接插入排序（insertion sort) 和希尔排序 (shell sort)。

直接插入排序比较简单，直接上代码：（算法渐进时间复杂度 O(n2) ）

# insertion sort

def insertion_sort(list)
	return list if list.size <= 1

	tmp = -1

	1.upto(list.size - 1) do |i|
		inserted = false
		tmp = list[i]
		puts(i)
		(i - 1).downto(0) do |j|
			puts(j)
			if tmp >= list[j]
				list[j+1] = tmp
				inserted = true
				puts "insert",(tmp),(j+1)
			else
				list[j+1] = list[j]
			end
			break if inserted
		end
	end

	list
end

list = [3, 5, 22, 634, 4]
puts(insertion_sort(list))

直接插入排序算法时间复杂度和原数组有关：如果原数组基本有序就很快，反之如果原数组乱序或者逆序则达到最坏时间复杂度。基于以上原因，出现希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

希尔排序就是按照固定步长先对子数组排序，然后逐渐缩短步长，最后一次排序步长为1（此时相当于进行一次插入排序，因为此时数组已经基本有序，所以很快）。

希尔排序最重要的部分是步长的选择，。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。（想了半天发现还是维基百科的描述最好理解 >_< ）。

而已知

已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…）这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）

而有了上述步长队列之后，只需要选择队列中小于原数组长度的步长中的最大者作为第一次希尔排序的步长即可。

希尔排序代码：（ruby）

# shell sort

def shell_sort(list)
	return list if list.size <= 1
	
	steps = [1, 4, 10, 23, 57, 132]
	index = 0
	while steps[index + 1] < list.size do
		index += 1
	end

	index.downto(0) do |i|
		step = steps[i]

		step.upto(list.size - 1) do |j|
			tmp = list[j]
			#puts list.size if step == 4
			k = j
			while(k >= step && list[k - step] > tmp) do
				list[k] = list[k-step]
				k = k - step
			end
			list[k] = tmp
		end
	end

	list
end

list = [23, 4, 56, 6, 5, 153, 2, 7, 98, 235, 2, 90, 20, 201, 6, 34, 47, 30]
puts (shell_sort(list))

详细介绍直接查看维基百科：http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F