亚洲午夜精品一区二区,亚洲视频在线精品,图图资源网亚洲综合网站

java 插入排序

不扯太多概念性的東西，簡單點來說，插入排序將數組所有元素劃分成了有序區和無序區，假設當前數組有 N 個元素，
開始默認第一個元素（下標為0）所處的位置是有序區，這是局部有序，從第二個元素（i=1）至數組最后一個元素（i=N-1）屬于無序區；
假設數組元素是按從左至右存放的，如果用 i 來標記無序區中的第一個元素下標，也就是無序區中最左邊或者說是無序區中下標值最小的下標，
則每趟排序是將下標 i 所指向的有效值插入有序區的適當位置，使得每趟排序完成之后，有序區的所有元素總是保持局部有序狀態。
按這樣來回 N -1 趟插入之后，則 N 個元素已成有序狀態。

盡管插入排序的復雜度也是 O(n^2)，但一般情況下，插入排序會比冒泡排序快一倍，要比選擇排序還要快一點。

排序基類：BaseSort.java

package sort;

/**

* -----------------------------------------

* @文件: BaseSort.java

* @作者: fancy

* @郵箱: fancydeepin@yeah.net

* @時間: 2012-7-18

* @描述: 基類

* -----------------------------------------

public class BaseSort {

protected final static int ASC = 1; // 升序

protected final static int DESC = 0; // 降序

//交換i1、i2下標指向的值

public void swap(Object[] array, int i1, int i2){

Object tempObj;

tempObj = array[i1];

array[i1] = array[i2];

array[i2] = tempObj;

tempObj = null;

}

//打印輸出數組元素

public void print(Object[] array){

for(Object obj : array){

System.out.print(obj + " ");

}

System.out.println();

}

插入排序：InsertSort.java

package sort;

/**

* -----------------------------------------

* @文件: InsertSort.java

* @作者: fancy

* @郵箱: fancydeepin@yeah.net

* @時間: 2012-7-18

* @描述: 插入排序

* -----------------------------------------

public class InsertSort extends BaseSort{

/**

* @方法名: insertSort

* @參數名： array 排序對象

* @參數名： order 排序順序

* @描述語: 插入排序:默認第一個是有序,使其余的像紙牌游戲那樣依次插入，復雜度 O(n^2)

public void insertSort(Object[] array, int order){

int length = array.length;

if(order == ASC){

for(int i = 1, j; i < length; i++){ //默認第1個(下標0)有序，i是無序區第一個元素下標，第i趟結束后，i下移，如此來回 N -1趟

for(j = 0; j < i; j++){ //將無序區下標為i所指向的值插入有序區適當位置

if(Double.parseDouble(array[j].toString()) > Double.parseDouble(array[i].toString())){

swap(array, i, j);

}

System.out.println("--------------------------------------------------------------------------->第" + i + "趟");

print(array);

}

}else if(order == DESC){

for(int i = 1, j; i < length; i++){ //默認第1個(下標0)有序，i是無序區第一個元素下標，第i趟結束后，i下移，如此來回 N -1趟

for(j = 0; j < i; j++){ //將無序區下標為i所指向的值插入有序區適當位置

if(Double.parseDouble(array[j].toString()) < Double.parseDouble(array[i].toString())){

swap(array, i, j);

}

System.out.println("--------------------------------------------------------------------------->第" + i + "趟");

print(array);

}

如需了解上面由粉紅色標記出來的代碼的用意，請參考我 java 分類里的冒泡排序這一隨筆： http://www.tkk7.com/fancydeepin/archive/2012/07/18/java_bubblesort.html

測試類：TestApp.java

package sort;

/**

* -----------------------------------------

* @文件: TestApp.java

* @作者: fancy

* @郵箱: fancydeepin@yeah.net

* @時間: 2012-7-18

* @描述: 測試類

* -----------------------------------------

public class TestApp {

public static void main(String[] args) {

Object[] array = {9,5,7,1,6,3,8,10,4,2};

(new InsertSort()).insertSort(array, InsertSort.ASC);

}

后臺輸出打印結果：

--------------------------------------------------------------------------->第1趟

5 9 7 1 6 3 8 10 4 2

--------------------------------------------------------------------------->第2趟

5 7 9 1 6 3 8 10 4 2

--------------------------------------------------------------------------->第3趟

1 5 7 9 6 3 8 10 4 2

--------------------------------------------------------------------------->第4趟

1 5 6 7 9 3 8 10 4 2

--------------------------------------------------------------------------->第5趟

1 3 5 6 7 9 8 10 4 2

--------------------------------------------------------------------------->第6趟

1 3 5 6 7 8 9 10 4 2

--------------------------------------------------------------------------->第7趟

1 3 5 6 7 8 9 10 4 2

--------------------------------------------------------------------------->第8趟

1 3 4 5 6 7 8 9 10 2

--------------------------------------------------------------------------->第9趟

1 2 3 4 5 6 7 8 9 10

[ 轉載出處：http://www.tkk7.com/fancydeepin ]

posted on 2013-12-31 13:49 午后星期午閱讀(85) 評論(0) 編輯收藏所屬分類: Java

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: Java 單例模式詳解值傳遞、引用傳遞的區別 java枚舉 Java動態代理設計模式 Java數組使用實用的技巧通過java獲取mac地址 java 插入排序 java 雙向冒泡排序 java 泛型深入 Java生成隨機字符串

午后星期午

導航

統計

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

java 插入排序