希尔排序

on October 7, 2016 under jekyll

1 minute read

算法描述：

基本思想为分组的直接插入排序

将要排序的数组分成若干组，每组由若干相隔一段距离的元素组成，这段距离称为增量（delta）。
增量的初值一般为数组长度的一般，以后每趟增量逐渐减小，最后值为1。随着增量的减小，组数也越来越少，组内元素个数越来越多，整个数组接近有序。最后增量为1时，整个数组为一组，再进行一趟直接插入排序即完成排序。

稳定性：不稳定。

时间复杂度：测量方法十分复杂，取决于要排序的数组。

空间复杂度：O（1）

希尔排序几乎没有最坏情况，无论是正序、逆序、乱序，所用时间都不是很多。

Java实现：

public class M002 {
	// 希尔排序
	public static void main(String[] args) {
		int[] number = { 21, 32, 2, 4, 65, 90, 54 };
		int result[] = shellSort(number);
		for (int i : result) {
			System.out.print(i + " ");
		}
	}

	private static int[] shellSort(int[] number) {
		for (int delta = number.length / 2; delta > 0; delta /= 2) {
			for (int i = delta; i < number.length; i++) {
				int temp = number[i], j;
				for (j = i - delta; j >= 0 && temp < number[j]; j -= delta) {
					number[j + delta] = number[j];
				}
				number[j + delta] = temp;
			}
		}
		return number;
	}
}

学习笔记, 数据结构, Java, 排序

I feedback.
Let me know what you think of this article on twitter @Yanlei_Hello or leave a comment below!