常見内部排序算法之插入排序

[size=large][color=red]常見内部排序算法之插入排序[/color][/size]

今天來寫寫插入排序算法，包括[color=red][size=medium]直接插入，折半插入，希爾排序（Shell）[/size][/color]。

插入插入，就是[b]将數組分成已排序，未排序，然後将未排序中的第一個插入已排序中的适合位置[/b]，這樣，未排序越來越少，直到沒有就算排序完成！而預設[color=red][b]開始[/b][/color]則是第一個是已排序，剩下的則是未排序。

[color=red][size=medium]直接插入算法：[/size][/color]

package test.aglorith;

import java.util.Arrays;

public class InsertSort {
	public static void sort(int[] data) {
		int data_len=data.length;
		for (int i = 1; i < data_len; i++) {//預設第一個（下标是0）是已排序，從未排序中的第二個（下标是1）開始
			int temp=data[i];
			int j = i-1;
			while (j >=0&&temp<data[j]) {
				data[j+1]=data[j];
				j--;
			}
			data[j+1]=temp;
			System.out.println(Arrays.toString(data));
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}

}
           

[color=red][size=medium]折半插入算法：[/size][/color]

package test.aglorith;
import java.util.Arrays;

public class InsertSortBinary {
	public static void sort(int[] data) {
		int data_len=data.length;
		for (int i = 1; i < data_len; i++) {
			int temp=data[i];
			int mid=getMid(data, i);
			swapPass(data, i, mid);
			data[mid]=temp;
			System.out.println(Arrays.toString(data));
		}
	}
	public static int getMid(int[] data,int i) {
		int temp=data[i];
		int low=0;
		int hight=i-1;
		while (low<=hight) {
			int mid=(low+hight)/2;
			if (temp<data[mid]) {
				hight=mid-1;
			}else {
				low=mid+1;
			}
		}
		return low;//無論如何都是傳回low，折中折中，無非最後隻剩下兩個的時候，選擇誰作為被替代者
	}
	public static void swapPass(int[] data,int i,int mid) {
		for (int j = i; j > mid; j--) {
			data[j]=data[j-1];
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{11,10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}
}
           

[color=red][size=medium]希爾排序算法：又稱縮小增量排序[/size][/color]

[b]由于插入排序需要大量的移動資料，是以效率會受到影響[/b]。而在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組内直接插入較快，後來增量increment逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按[color=red]increment*+3[/color]作為距離排過序，使檔案較接近于[color=red]有序狀态[/color]，是以新的一趟排序過程也較快。是以，希爾排序在效率上較直接插入排序有較大的改進。

package test.aglorith;
import java.util.Arrays;
public class ShellSort {
	//通過增量increment分組進行排序
	public static void sortByIncrement(int[] data,int increment) {
		int data_len=data.length;
		for (int i = increment; i <data_len; i++) {
			int temp=data[i];
			int j=i-increment;
			while (j>=0&&temp<data[j]){
				data[j+increment]=data[j];
				j=j-increment;
			}
			data[j+increment]=temp;
		}
		System.out.println(Arrays.toString(data));
	}
	//不同的increment分組排序，直到increment=1（相當于直接插入排序，但是由于前面的排序已經使得數組基本上處于有序狀态）
	public static void sort(int[] data) {
		int increment=data.length;
		while (increment>1) {
			increment=(increment-1)/3;
			sortByIncrement(data,increment);
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{13,12,11,10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前"+Arrays.toString(data));
		sort(data);
	}
}