欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2015年05月19日 10:06:31   作者:一羽清寧  
這篇文章主要介紹了Java排序算法總結(jié)之插入排序,較為詳細(xì)的分析了插入排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下

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

有一個已經(jīng)有序的數(shù)據(jù)序列,要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù),但要求插入后此數(shù)據(jù)序列仍然有序,這個時候就要用到插入排序法。本文主要介紹的是插入排序的java實(shí)現(xiàn)。
 
插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)。比較和交換的時間復(fù)雜度為O(n^2),算法自適應(yīng),對于數(shù)據(jù)已基本有序的情況,時間復(fù)雜度為O(n),算法穩(wěn)定,開銷很低。算法適合于數(shù)據(jù)已基本有序或者數(shù)據(jù)量小的情況。

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

算法描述

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

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

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

代碼實(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ī)則,則需要移動大量的數(shù)據(jù),其效率就與冒泡排序法和選擇排序法一樣差了。

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

相關(guān)文章

  • Java實(shí)現(xiàn)連連看算法

    Java實(shí)現(xiàn)連連看算法

    這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)連連看算法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • servlet 解決亂碼問題

    servlet 解決亂碼問題

    這篇文章主要介紹了servlet 解決亂碼問題 ,需要的朋友可以參考下
    2015-04-04
  • Java封裝公共Result結(jié)果返回類的實(shí)現(xiàn)

    Java封裝公共Result結(jié)果返回類的實(shí)現(xiàn)

    在使用Java開發(fā)接口請求中,我們需要對請求進(jìn)行進(jìn)行統(tǒng)一返回值,這時候我們自己封裝一個統(tǒng)一的Result返回類,本文主要介紹了Java封裝公共Result結(jié)果返回類的實(shí)現(xiàn),感興趣的可以了解一下
    2023-01-01
  • springboot下實(shí)現(xiàn)RedisTemplate?List?清空

    springboot下實(shí)現(xiàn)RedisTemplate?List?清空

    我們經(jīng)常會使用Redis的List數(shù)據(jù)結(jié)構(gòu)來存儲一系列的元素,當(dāng)我們需要清空一個List時,可以使用RedisTemplate來實(shí)現(xiàn),本文就來詳細(xì)的介紹一下如何實(shí)現(xiàn),感興趣的可以了解一下
    2024-01-01
  • springboot項(xiàng)目test文件夾下帶main方法的類不能運(yùn)行問題

    springboot項(xiàng)目test文件夾下帶main方法的類不能運(yùn)行問題

    這篇文章主要介紹了springboot項(xiàng)目test文件夾下帶main方法的類不能運(yùn)行問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-11-11
  • Java對日期Date類進(jìn)行加減運(yùn)算、年份加減月份加減、時間差等等

    Java對日期Date類進(jìn)行加減運(yùn)算、年份加減月份加減、時間差等等

    這篇文章主要介紹了Java對日期Date類進(jìn)行加減運(yùn)算、年份加減月份加減、時間差等等,在網(wǎng)上查閱資料,加上自己總結(jié)的一些關(guān)于Date類的工具類
    2017-01-01
  • Java Collections.shuffle()方法案例詳解

    Java Collections.shuffle()方法案例詳解

    這篇文章主要介紹了Java Collections.shuffle()方法案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • centos上安裝配置java WEB環(huán)境

    centos上安裝配置java WEB環(huán)境

    前提是centos6.3系統(tǒng)已經(jīng)安裝好,在這里以64位系統(tǒng)為例,下面是jdk,tomcat,mysql下載安裝步驟,有需要的小伙伴可以參考下
    2016-10-10
  • 教你springboot+dubbo快速啟動的方法

    教你springboot+dubbo快速啟動的方法

    這篇文章主要介紹了springboot+dubbo快速啟動的方法,dubbo的角色廣泛的分為三類provider,comsumer,注冊中心,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下
    2022-04-04
  • springboot如何添加全局異常捕獲類

    springboot如何添加全局異常捕獲類

    這篇文章主要介紹了springboot如何添加全局異常捕獲類,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-01-01

最新評論