插入排序

       

插入排序

插入排序是最简单的排序算法之一。插入排序由N趟排序组成。当i从1至N趟，插入排序保证数组下标i-1之前的元素为已排序状态。进行排序时，若arr[i]<arr[i-1]则将arr[i]和arr[i-1]交换，再将arr[i-1]与前一个元素比较，直到不比前一个元素小为止。若arr[i]>arr[i-1],则不作任何操作。

package com.insertionsort.yy;

/**
 * 直接插入排序（升序）
 *@author yuyang_csu
 *@data 2013-4-5
 */
public class InsertionSort {
	private int arr[];

	public InsertionSort(int arr[]) {
		this.arr = arr;
	}

	// 插入排序方法
	public void insertionSort() {
		int tmp;
		for (int i = 0; i < arr.length; i++) {
			tmp = arr[i];
			for (int j = i - 1; j >= 0 && tmp < arr[j]; j--) {
				arr[j + 1] = arr[j];
				arr[j] = tmp;
			}
		}
	}

    //显示数组元素的方法
	public void display(){
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void main(String[] args) {
		int[] arr = { 1, 5, 9, 4, 6, 3, 10, 7 };
		InsertionSort in = new InsertionSort(arr);
		in.insertionSort();
		in.display();
	}
}

插入排序时间复杂度分析：
最坏情况下，数组是按由大到小排序的，内循环每一次都要操作i-1次，总共需要1+2+3+...+N-1 = N(N-1)/2次，所以最坏情况下时间复杂度为O（N^2）。在最理想的情况下，时间复杂度为O(N)。平均情况下，时间复杂度也为O（N^2）,由于过程过于复杂，这里不作累述。

插入排序稳定性分析：
由代码可知，加入待排序数组中存在若干个相等的关键字，排序的时候不会改变这些相等关键字的顺序，所以该排序算法是稳定的。