`
flyer2010
  • 浏览: 358834 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

插入排序---直接插入排序

 
阅读更多
基本思想
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。

演示网址:http://www.yxqzzx.cn/teacher/ShowArticle.asp?ArticleID=417
举例说明:

待排序数组R[7,3,4,1,5,8]

第1趟排序:
3 | 7  3  4  1  5  8
3 | 7  7  4  1  5  8
3 | 3  7  4  1  5  8

第2趟排序:
4 | 3  7  4  1  5  8
4 | 3  7  7  1  5  8
4 | 3  4  7  1  5  8


第3趟排序:
1 | 3  4  7  1  5  8
1 | 3  4  7  7  5  8
1 | 3  4  4  7  5  8
1 | 3  3  4  7  5  8
1 | 1  3  4  7  5  8


第4趟排序:
5 | 1  3  4  7  5  8
5 | 1  3  4  7  7  8
5 | 1  3  4  5  7  8
第4趟排序:
R[i-1]<R[i]不需要排序。

从上面的步骤可以看出,直接插入排序的过程为:从数组第一个元素开始,两两相邻的元素进行比较,找出其中的小的元素作为哨兵,并记录位置j,然后从位置j开始,j--到数组起始位置,进行数据交换。


	/**
	 * 直接插入排序
	 * 
	 * @param unsorted
	 */
	public static void insertion_sort(int[] unsorted) {
		for (int i = 1; i < unsorted.length; i++) {
			if (unsorted[i - 1] > unsorted[i]) {
				int temp = unsorted[i];
				int j = i;
				while (j > 0 && unsorted[j - 1] > temp) {
					unsorted[j] = unsorted[j - 1];
					j--;
				}
				unsorted[j] = temp;
			}
		}
	}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics