幾個(gè)小排序算法

冒泡排序

時(shí)間復(fù)雜度:n^2贼涩。
每一輪比較都從頭開(kāi)始,然后兩兩比較,如果左值比右值大,則交換位置,每一輪結(jié)束后,當(dāng)前輪"最后一個(gè)元素"必將是最大的.

public void bubbling(int[] arr, int length){
        for(int i = 0; i < length-1; i++){
            for(int j = 0; j< length -i -1; j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }

快速排序

時(shí)間復(fù)雜度:n*logN
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小抄腔,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序俱济,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列垢乙。

public static void quictSort(int[] sources,int start,int end){
        if(start < end){
            int tmp;
            int i = start;
            int j = end;
            int value = sources[i];
            while(i < j){
                while(sources[j] > value && i<j){
                    j--;
                }
                //右邊找到了比key大的.
                tmp = sources[i];
                sources[i] = sources[j];
                sources[j] = tmp;

                while(sources[i] < value && i<j){
                    i++;
                }
                //左邊找到了比key大的值
                tmp = sources[i];
                sources[i] = sources[j];
                sources[j] = tmp;
            }
            for (int x = 0; x < sources.length; x++) {
                System.out.print(sources[x] + " ");
            }
            System.out.println();

            quictSort(sources, start, j - 1);
            quictSort(sources, j + 1, end);
        }
    }

插入排序

時(shí)間復(fù)雜度:n^2
把待排序的紀(jì)錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中氮兵,直到所有的紀(jì)錄插入完為止,得到一個(gè)新的有序序列

public void insertSort(int[] arr, int size){
        for(int i=0; i < size-1; i++){
            for(int j=i; j>0; j--){
                if(arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }

歸并排序

時(shí)間復(fù)雜度:n*logN 空間復(fù)雜度: n
分治法,將數(shù)組逐步拆分為"組",直到最小的"組",然后每個(gè)組內(nèi)排序,然后依次和相鄰的組"排序合并",其中"排序".其內(nèi)部排序非常簡(jiǎn)單.直接比較.

public static void mergeSort(int[] sources,int begin,int end){
        if(begin < end){
            int range = end - begin;
            int mid = begin + range/2;
            mergeSort(sources, begin, mid);//左段
            mergeSort(sources, mid + 1, end);//右端
            System.out.println(Arrays.toString(sources));
            merge(sources, begin, mid, end);
        }
    }
    private static void merge(int[] sources,int begin,int mid,int end){
        int[] tmp = new int[end - begin + 1];
        int b1 = begin;
        int e1 = mid;
        int b2 = mid+1;
        int e2 = end;
        int i=0;
        for(;b1 <= e1 && b2 <= e2 ; i++){
            //填充tmp數(shù)組,并依此在兩段數(shù)據(jù)區(qū)域中找到最小的
            if(sources[b1] <= sources[b2]){
                tmp[i] = sources[b1];
                b1++;
            }else{
                tmp[i] = sources[b2];
                b2++;
            }
        }
        //到此為止,兩段數(shù)據(jù)區(qū)域,已經(jīng)至少一個(gè)被掃描完畢
        if(b1 > e1){
            //如果b1~e1掃描完畢,那么可能b2~e2還有剩余
            for(int t = b2;t < e2 + 1; t++){
                tmp[i] = sources[t];
                i++;
            }
        }
        if(b2 > e2){
            //如果b2~e2掃描完畢,那么可能b1~e1還有剩余
            for(int t = b1;t < e1 + 1; t++){
                tmp[i] = sources[t];
                i++;
            }
        }
        //replace and fill:將tmp數(shù)組的數(shù)據(jù),替換到source中,begin~end
        //因?yàn)榇藭r(shí)tmp中的數(shù)據(jù)是排序好的
        i=0;
        for(int t= begin;t <= end; t++){
            sources[t] = tmp[i];
            i++;
        }
        tmp = null;//
    }
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末抱慌,一起剝皮案震驚了整個(gè)濱河市逊桦,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌抑进,老刑警劉巖卫袒,帶你破解...
    沈念sama閱讀 206,482評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異单匣,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,377評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門户秤,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)码秉,“玉大人,你說(shuō)我怎么就攤上這事鸡号∽” “怎么了?”我有些...
    開(kāi)封第一講書人閱讀 152,762評(píng)論 0 342
  • 文/不壞的土叔 我叫張陵鲸伴,是天一觀的道長(zhǎng)府蔗。 經(jīng)常有香客問(wèn)我,道長(zhǎng)汞窗,這世上最難降的妖魔是什么姓赤? 我笑而不...
    開(kāi)封第一講書人閱讀 55,273評(píng)論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮仲吏,結(jié)果婚禮上不铆,老公的妹妹穿的比我還像新娘。我一直安慰自己裹唆,他們只是感情好誓斥,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,289評(píng)論 5 373
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著许帐,像睡著了一般劳坑。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上成畦,一...
    開(kāi)封第一講書人閱讀 49,046評(píng)論 1 285
  • 那天距芬,我揣著相機(jī)與錄音,去河邊找鬼羡鸥。 笑死蔑穴,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的惧浴。 我是一名探鬼主播存和,決...
    沈念sama閱讀 38,351評(píng)論 3 400
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼衷旅!你這毒婦竟也來(lái)了捐腿?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書人閱讀 36,988評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤柿顶,失蹤者是張志新(化名)和其女友劉穎茄袖,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體嘁锯,經(jīng)...
    沈念sama閱讀 43,476評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡宪祥,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,948評(píng)論 2 324
  • 正文 我和宋清朗相戀三年聂薪,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蝗羊。...
    茶點(diǎn)故事閱讀 38,064評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡藏澳,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出耀找,到底是詐尸還是另有隱情翔悠,我是刑警寧澤,帶...
    沈念sama閱讀 33,712評(píng)論 4 323
  • 正文 年R本政府宣布野芒,位于F島的核電站蓄愁,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏狞悲。R本人自食惡果不足惜撮抓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,261評(píng)論 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望效诅。 院中可真熱鬧胀滚,春花似錦、人聲如沸乱投。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 30,264評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)戚炫。三九已至剑刑,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間双肤,已是汗流浹背施掏。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 31,486評(píng)論 1 262
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留茅糜,地道東北人七芭。 一個(gè)月前我還...
    沈念sama閱讀 45,511評(píng)論 2 354
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像蔑赘,于是被迫代替她去往敵國(guó)和親狸驳。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,802評(píng)論 2 345

推薦閱讀更多精彩內(nèi)容

  • 十大基礎(chǔ)排序算法缩赛。 Basic-Sorting-Algorithm 關(guān)于十大基本排序算法的整理耙箍。 十大排序算法分別...
    一劍孤城閱讀 2,634評(píng)論 1 6
  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序酥馍,而外部排序是因排序的數(shù)據(jù)很大辩昆,一次不能容納全部...
    zwb_jianshu閱讀 1,104評(píng)論 0 0
  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序旨袒,而外部排序是因排序的數(shù)據(jù)很大汁针,一次不能容納全部...
    閑云清煙閱讀 756評(píng)論 0 6
  • 概述 排序有內(nèi)部排序和外部排序术辐,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大扇丛,一次不能容納全部...
    printf200閱讀 760評(píng)論 0 0
  • 轉(zhuǎn)載自CSDN規(guī)速 八大排序算法 概述 排序有內(nèi)部排序和外部排序术吗,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是...
    _小沫閱讀 543評(píng)論 0 1