排序1 插入排序

算法描述: 

将待排序的数组分为2部分,一部分为已排序数组，另外一部分为待排序数组

利用2重循环，每次从待排序数组中取一个数，跟已经排序好的数组进行比较，找到插入的位置，然后移动已排序好的数组

确保每次新插入的元素都能在正确的位置，那么当带排序数组元素为0的时候，整个数组也就排序完毕。

小例子：

有一个数组 5 3 2 4 1，假设进行升序排列

那么将此数组分成两部分

   已排序数组     待排序数组

初始状态       5                  3 2 4 1

 

第一次插入3   3  5             2 4 1

第二次插入2   2  3  5         4  1

第三次插入4   2  3  4  5     1

第四次插入1   1  2  3  4  5

保证在每次插入前和插入后整个数组都是有序的，那么插入完毕整个数组就是有序的

算法效率分析

时间复杂度：需要

空间复杂度：O(1);只需要1个变量存储待排序的元素就可以，移动在原数组上进行

算法优缺点

在排序较少的数据，并且已经大致有序的数组上速度较快

在大数据量或者数据非常无序的情况下较慢，需要大量的比较以及移动数组

总结体会

有点数学归纳法的感觉 n=1时式子成立，假设n=k时式子成立，只要证明n=k+1时成立，那么整个式子就成立

当已排序好的数组只有1个元素时，数组显然有序。

假设已排序好的数组有k个元素，再插入1个元素到正确的位置，数组仍然有序，所以整个插入做下来数组是有序的

（表达得不到位..）

 

算法代码实现

第一次的实现，使用了额外的空间

 

package com.ysb;

import java.util.Random;

/**
 * @author Administrator 测试各种排序方法 全部按 升序排列
 */
public class Sort {
	// 数组长度
	public static final int ARRAYLENGTH = 150000;

	public static void main(String[] args) {
		int[] randomArray = new int[ARRAYLENGTH];
		for (int i = 0; i < ARRAYLENGTH; i++) {
			randomArray[i] = new Random().nextInt(ARRAYLENGTH);
		}
		int[] sortArray = new int[ARRAYLENGTH];
		for (int i = 0; i < ARRAYLENGTH; i++) {
			sortArray[i] = i;
		}
		System.out.println("开始排序");
		long startTime1 = System.currentTimeMillis();
		sort1(randomArray);
		long endTime1 = System.currentTimeMillis();
		long startTime2 = System.currentTimeMillis();
		System.out.println("开始排序");
		sort1(randomArray);
		long endTime2 = System.currentTimeMillis();
		
		System.out.println("使用直接插入排序排序" + ARRAYLENGTH + "个无序数中使用的时间为"
				+ (endTime1 - startTime1) + "ms");
		System.out.println("使用直接插入排序排序" + ARRAYLENGTH + "个有序数中使用的时间为"
				+ (endTime2 - startTime2) + "ms");
		
	}

	private static void sort1(int[] array) {
		// 已排好序
		int[] hasSortArray = new int[array.length];
		// 第一个元素为原数组的第一个元素

		hasSortArray[0] = array[0];
	//	System.out.println("第1个数为" + hasSortArray[0]);
		int count = 1;
		for (int i = 1; i < array.length; i++) {
		//	System.out.print("已经排好序的数：");
		
			// 取出准备排序的数据
			int waitToSort = array[i];
		//	System.out.println();
	//		System.out.println("准备排序的数字 ：" + waitToSort);
			int j = 0;
			for (j = 0; j < count; j++) {
				if (waitToSort < hasSortArray[j]) {
					// 小则插入
				//	System.out.println("找到比" + waitToSort + "大的元素，应该插入在第" + j
				//			+ "个位置");
			//		System.out
			//				.println("从第" + j + "个元素到第" + (count-1) + "元素都往后移动1位");
					int move = count - j;
					for (int k = move + j; k > j; k--) {
						hasSortArray[k] = hasSortArray[k - 1];
					}
					hasSortArray[j] = waitToSort;
					break;
				}
			}
			if (j == count) {

			//	System.out.println("没有比" + waitToSort + "大的元素,直接放在" + count
			//			+ "位置");
				hasSortArray[count] = waitToSort;

			}

			count++;

		}
	//	System.out.println();
	//	System.out.println("验证100个");
		// 打印100个验证
		for (int i = 0; i < 100; i++) {
			System.out.print(hasSortArray[i] + " ");
		}
		System.out.println();
	}
}