一、插入類排序

目前創(chuàng)新互聯(lián)公司已為千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、安平網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

1.直接插入排序

思想：將第i個(gè)插入到前i-1個(gè)中的適當(dāng)位置

時(shí)間復(fù)雜度：T(n) = O(n²)。

空間復(fù)雜度：S(n) = O(1)。

穩(wěn)定性：穩(wěn)定排序。

如果碰見(jiàn)一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后順序沒(méi)有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定

哨兵有兩個(gè)作用：

① 進(jìn)人查找(插入位置)循環(huán)之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內(nèi)容；

② 它的主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。一旦越界(即j=0)，因?yàn)镽[0].可以和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測(cè)j是否越界(即省略了循環(huán)判定條件"j>=1")

public void insertSort(int[] array){
  for(int i=1;i<array.length;i++)//第0位獨(dú)自作為有序數(shù)列，從第1位開(kāi)始向后遍歷
  {
   if(array[i]<array[i-1])//0~i-1位為有序，若第i位小于i-1位，繼續(xù)尋位并插入，否則認(rèn)為0~i位也是有序的，忽略此次循環(huán)，相當(dāng)于continue
   {
    int temp=array[i];//保存第i位的值
    int k = i - 1;
    for(int j=k;j>=0 && temp<array[j];j--)//從第i-1位向前遍歷并移位，直至找到小于第i位值停止
    {
     array[j+1]=array[j];
     k--;
    }
    array[k+1]=temp;//插入第i位的值
   }
  }
}

文章標(biāo)題：詳細(xì)總結(jié)各種排序算法(Java實(shí)現(xiàn))-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)于：http://m.rwnh.cn/article10/ddsodo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、建站公司、品牌網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、做網(wǎng)站、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)