資料結構--簡單排序_插入排序

插入排序算法：

漸進時間複雜度O(N^2)

比冒泡排序快一倍

插入排序方法：

要把第一個元素當成是有序的。（是以寫代碼的時候外層循環是從1開始的）

首先将第二個元素拿出來，放到臨時資料的地方，然後和第一個進行比較，誰小就放在前面

然後将第三個元素拿出來，放到臨時資料的地方，再依次和第二個元素比較，第一個元素比較。放到指定的位置

然後将第四個元素拿出來，放到臨時資料的地方，再依次和第三個元素比較，第二個元素比較，第一個元素比較，放到指定的位置。

依次類推。

舉例：

例如一組資料按照插入排序算法進行排序

12,34,2,45,6

==================================================================================================

第一次排序：

12,2,45,6   将第二個元素拿出來當成是臨時資料，也就是temp=34，然後和第一個元素比較，12小于34是以排序為：

12,34,2,45,6

==================================================================================================

第二次排序

12,34,45,6  将第三個元素拿出來當成是臨時資料，也就是temp=2,然後依次和第二個元素比較，第一個元素比較，是以排序為：

2,12,34,45,6

==================================================================================================

第三次排序

2,12,34,6  将第四個元素拿出來當成是臨時資料，也就是temp=45,然後依次和第三個元素比較，（因為都是有序的是以不用再和第二個元素和第一個元素比較），是以排序為:

2,12,34,45,6

==================================================================================================

第四次排序

2,12,34,45 将第五個元素拿出來當成是臨時資料，也就是temp=6,然後依次和第四個元素比較，第三個元素比較，第二個元素比較，第一個元素比較，是以排序為：

2,6,12,34,45

==================================================================================================

java代碼：

public class InsertSort {

	private long[] a;
	public int elements;
	
	public InsertSort(int max) {
		// TODO Auto-generated constructor stub
		a=new long[max];
		elements=0;
	}
	
	public void insert(long value){
		a[elements]=value;
		elements++;
	}
	
	public void display(){
		for(int j=0;j<elements;j++)
			System.out.print(a[j]+" ");
		System.out.println();
	}
	
	public void insertSort(){
		int out,in;//定義一個外層循環和内層循環的變量
		for(out=1;out<elements;out++){//外層循環從第一個元素開始
			long temp=a[out];//将該元素指派給臨時資料
			in=out;
			while(in>0&&a[in-1]>temp){//内層循環必須比0大
				a[in]=a[in-1];
				in--;
			}
			a[in]=temp;
		}
	}
	
	public static void main(String[] args) {
		InsertSort insertSort=new InsertSort(100);
		
		insertSort.insert(125);
		insertSort.insert(233);
		insertSort.insert(12);
		insertSort.insert(332);
		insertSort.insert(11);
		
		System.out.println("沒有排序前：");
		insertSort.display();
		
		System.out.println("排序後：");
		insertSort.insertSort();
		insertSort.display();
	}
}
           

或者：

/*
簡單插入排序函數 
*/
void insertSort(int *arr[],int len){
    int i;
    int j;
    int temp;  //定義一個臨時變量，用于交換資料時存儲 
    for(i=1;i<len;i++){  //因為我們要對該待排序列的每一個元素都和前面的已排好序的序列進行插入，是以我們會對序列進行周遊 
        for(j=0;j<i;j++){  //第二層循環主要用于對已排好序的序列進行掃描，和要插入進來的資料進行逐一比較，然後決定插入到哪裡 
            if(arr[j]>arr[i]){//從前往後對已排好序的元素和待插入元素進行大小比較，然後直到找到一個元素比被插入元素大，則交換位置 
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
}