首頁  >  文章  >  Java  >  Java插入排序的簡單實例

Java插入排序的簡單實例

黄舟
黄舟原創
2017-08-11 09:39:361608瀏覽

這篇文章主要為大家詳細介紹了java簡單插入排序實例,具有一定的參考價值,有興趣的小夥伴們可以參考一下

##一、基本概念

#      插入排序的基本操作就是將一個資料插入到已經排好序的有序資料中,從而得到一個新的、個數加一的有序數據,演算法適用於少量資料的排序,時間複雜度為O(n^2)。是穩定的排序方法。插入演算法將要排序的陣列分成兩部分:第一部分包含了這個陣列的所有元素,但將最後一個元素除外(讓陣列多一個空間才有插入的位置),而第二部分只包含這一個元素(即待插入元素)。在第一部分排序完成後,再將這個最後元素插入到已排好序的第一部分。

二、java程式碼實作


public class InsertSort {
  public static void inserSort(int[] array){
    if (array==null||array.length<2){
      return;
    }

    for (int i=1;i<array.length;i++){ //默认第一个元素为有序队列,从第二个元素开始循环插入
      int position=array[i];     //设置第二个元素为要插入的数据
      int j=i-1;
      while (j>=0&&position<array[j]){
        array[j+1]=array[j];   //如果插入发数小于第j个元素,将第j个数向后移
        j--;
      }
      array[j+1]=position;     //插入
    }
  }

  public static void main(String ags[]){
    int[] array={2,6,4,7,3,-1};
    inserSort(array);
    for (int i=0;i<array.length;i++){
      System.out.print(array[i]+" ");
    }
  }
}

三、效能分析

穩定

空間複雜度O(1)
時間複雜度O(n2)
最差情況:反序,需要移動n*(n-1)/2個元素
最好情況:正序,不需要移動元素

以上是Java插入排序的簡單實例的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn