排序算法--直接插入排序、折半插入排序、希尔排序

59 阅读 0 评论 39 点赞

我是靠谱客的博主苹果玉米，最近开发中收集的这篇文章主要介绍排序算法--直接插入排序、折半插入排序、希尔排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

插入排序这个比较简单，理解也容易。文章结构还是三部曲：1、文字描述 2、图片深入 3、程序辅助（我就是逗比一枚）

插入排序的基本操作：将一个记录插入已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

来张图理解一下，这个不多解释了。应该都能明白：

直接插入排序代码：本文代码本人亲测！！！

public static void InsertSort(int[] a){
	int j = 0;
	for(int i = 1; i < a.length; i++){
		if(a[i] < a[i - 1]){
			int temp = a[i];
			j = i - 1;
			do{
				a[j + 1] = a[j];
				j--;
			}while(j >= 0 && temp < a[j]);
			a[j + 1] = temp;
		}
	}
}

2、折半插入排序

基本思想：跟插入排序类似，假设数组中的元素有序，则在插入的时候用折半查找的方法寻找插入位置。这个比直接插入排序效率高。

折半插入排序代码：

public static void InsertSort1(int[] a){
	for(int i = 1; i < a.length; i++){
		int temp = a[i];
		int low = 0;
		int high = i - 1;
		while(low <= high){
			int mid = (low + high)/2;
			if(a[mid] > temp)
				high = mid - 1;
			else
				low = mid + 1; 
		}
		for(int k = i - 1; k >= low; k--)
			a[k+1] = a[k];   //向后移动，找到插入点
		a[low] = temp;       //插入a[i]
	}
}

3、希尔排序

希尔排序为什么也在这写呢，因为这三个排序都是类似插入排序的原理。

希尔排序：又称为缩小增量排序。

基本思想：设待排序的元素序列有n个元素，首先取一个整数gap<n作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素放在同一个子序列中，在每一个子序列中分别用直接插入排序。然后缩小间隔gap，重复上述的子序列划分和排序。直到最后gap = 1，将所有的元素放在同一个序列中排序为止。

希尔排序看似很啰嗦，但是用起来还是挺好用的，几乎排序几次就能搞定了，用不到gap = 1的情况。

上图：

希尔排序代码：

public static void ShellSort(int[] a){
	int gap = a.length + 1;
	int i = 0, j = 0, temp = 0;
	do{
		gap = gap/3 + 1;        //间隔
		for(i = gap; i < a.length; i++){
			if(a[i] < a[i - gap]){
				temp = a[i];
				j = i - gap;
				do{
					a[i]= a[i - gap];
					j = j - gap;
				}while(j >= 0 && temp < a[j]);
				a[i - gap] = temp;
			}
		}
	}while(gap > 1);
}