首頁技術(shù)文章正文

Jva培訓(xùn)之插入排序法

更新時間:2016年08月29日17時25分來源:傳智播客Java培訓(xùn)學(xué)院瀏覽次數(shù):

  思想:插入排序法的排序思想就是從數(shù)組的第二個元素開始,將數(shù)組中的每一個元素按照規(guī)則插入到已排好序的數(shù)組中以達到排序的目的.一般情況下將數(shù)組的第一個元素作為啟始元素,從第二個元素開始依次插入.由于要插入到的數(shù)組是已經(jīng)排好序的,所以只是要從右向左找到比插入點(下面程序中的insertNote)小(對升序而言)的第一個數(shù)組元素就插入到其后面.直到將最后一個數(shù)組元素插入到數(shù)組中,整個排序過程就算完成.
    穩(wěn)定性:穩(wěn)定的.
    時間復(fù)雜度:O(n²)
    實例:
import java.util.*;
class sorts
{
public static void main(String[] args)
{
  int[] arr= new int[]{800,9,3,6,12,54,35,411,3,245,1,0,4};
  sorts.InsertSort(arr);
}
public static int[] InsertSort(int[] arr)
{
  int i,j;
  int insertNote;//要插入的數(shù)據(jù)
  int[] array=arr;

   //從數(shù)組的第二個元素開始循環(huán)將數(shù)組中的元素插入
  for (i=1;i<array.length;i++)
  {
   //設(shè)置數(shù)組中的第2個元素為第一次循環(huán)要播講的數(shù)據(jù)
   insertNote = array[i];
   j=i-1;
   while(j>=0&&insertNote<array[j])
   {
    //如果要播講的元素小于第j個元素,就將第j個元素向后移動
    array[j+1]=array[j];
    j--;
   }
   //直到要插入的元素不小于第j個元素,將insertNote插入到數(shù)組中
   array[j+1]=insertNote;
  }
  //打印排序后的數(shù)組
  System.out.println(Arrays.toString(array));
  return array;

}
}

本文版權(quán)歸傳智播客Java培訓(xùn)學(xué)院所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明作者出處。謝謝！
作者：傳智播客Java培訓(xùn)學(xué)院
首發(fā)：http://metathetuscanyresort.com/javaee

上一篇：Java培訓(xùn)之關(guān)于嵌套查詢和連接查詢的效率問題 下一篇：Java培訓(xùn)之Struts2 result type(結(jié)果類型)