Java排序算法總結(jié)之插入排序

更新時(shí)間：2015年05月19日 10:06:31 作者：一羽清寧

這篇文章主要介紹了Java排序算法總結(jié)之插入排序,較為詳細(xì)的分析了插入排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Java插入排序方法。分享給大家供大家參考。具體分析如下：

有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到插入排序法。本文主要介紹的是插入排序的java實(shí)現(xiàn)。

插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。比較和交換的時(shí)間復(fù)雜度為O(n^2)，算法自適應(yīng)，對(duì)于數(shù)據(jù)已基本有序的情況，時(shí)間復(fù)雜度為O(n)，算法穩(wěn)定，開銷很低。算法適合于數(shù)據(jù)已基本有序或者數(shù)據(jù)量小的情況。

插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外，而第二部分就只包含這一個(gè)元素。在第一部分排序后，再把這個(gè)最后元素插入到此刻已是有序的第一部分里的位置。

算法描述

一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到下一位置中
6. 重復(fù)步驟2

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

代碼實(shí)現(xiàn)

public void insertionSort() { 
  // 插入排序 
  int out, in; 
  int count1 = 0, count2 = 0;// 復(fù)制次數(shù)，比較次數(shù) 
  for (out = 1; out < nElems; out++) { 
   long temp = a[out]; 
   in = out; 
   boolean flag=in>0&&a[in-1]>=temp; 
   while(flag){ 
   if(a[in-1]>=temp){ 
    if(in>0){ 
    a[in]=a[in-1]; 
    count1++; 
    --in;  
    } 
   } 
    count2++; 
    flag=in>0&&a[in-1]>=temp; 
   }  
   a[in] = temp; 
  } 
  System.out.println("復(fù)制次數(shù)為：" + count1 + " 比較次數(shù)為：" + count2); 
}

插入排序法在數(shù)據(jù)已有一定順序的情況下，效率較好。但如果數(shù)據(jù)無規(guī)則，則需要移動(dòng)大量的數(shù)據(jù)，其效率就與冒泡排序法和選擇排序法一樣差了。

希望本文所述對(duì)大家的java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: