Java排序算法 插入排序

有一個已經有序的資料序列，要求在這個已經排好的資料序列中插入一個數，但要求插入後此資料序列仍然有序，這個時候就要用到插入排序法。本文主要介紹的是插入排序的java實作。

AD：

插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中,進而得到一個新的、個數加一的有序資料。比較和交換的時間複雜度為O(n^2)，算法自适應，對于資料已基本有序的情況，時間複雜度為O(n)，算法穩定，開銷很低。算法适合于資料已基本有序或者資料量小的情況。

插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外，而第二部分就隻包含這一個元素。在第一部分排序後，再把這個最後元素插入到此刻已是有序的第一部分裡的位置。

//插入排序是一種通過不斷地把新元素插入到已排好序的資料中的排序算法

算法描述

一般來說，插入排序都采用in-place在數組上實作。具體算法描述如下：

1. 從第一個元素開始，該元素可以認為已經被排序

2. 取出下一個元素，在已經排序的元素序列中從後向前掃描

3. 如果該元素（已排序）大于新元素，将該元素移到下一位置

4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到下一位置中

6. 重複步驟2

如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。

代碼實作

public class InsertSort {

public static void main(String[] args)

 {

  int[] arr= new

int[]{800,9,3,6,12,54,35,411,3,245,1,0,4};

  InsertSort(arr);

 }

 public static int[] InsertSort(int[] arr)

  int i,j;

  int insertNote;//要插入的資料

  int[] array=arr;

 //從數組的第二個元素開始循環将數組中的元素插入

  for

(i=1;i<array.length;i++)

  {

 //設定數組中的第2個元素為第一次循環要播講的資料

   insertNote = array[i];

   j=i-1;

   System.out.println("

    i  

j的值為："+i+"  "+j);

 System.out.print("insertNote:"+insertNote+"

  ");

 while(j>=0&&insertNote<array[j])

   {

//如果要播講的元素小于第j個元素,就将第j個元素向後移動

    array[j+1]=array[j];

    System.out.print("z");

    j--;

   }

 //直到要插入的元素不小于第j個元素,将insertNote插入到數組中

 array[j+1]=insertNote; 

   System.out.print("

Arrays:"+Arrays.toString(array));

  }

  //列印排序後的數組

 //

System.out.println(Arrays.toString(array));

  return array;

}

插入排序法在資料已有一定順序的情況下，效率較好。但如果資料無規則，則需要移動大量的資料，其效率就與冒泡排序法和選擇排序法一樣差了。