成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

排序算法(Java)——那些年面試常見的排序算法

Harpsichord1207 / 1492人閱讀

摘要:下面會(huì)介紹的一種排序算法快速排序甚至被譽(yù)為世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。為了展示初級(jí)排序算法性質(zhì)的價(jià)值,我們來看一下基于插入排序的快速的排序算法希爾排序。

前言

  排序就是將一組對(duì)象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期,大家普遍認(rèn)為30%的計(jì)算周期都用在了排序上,今天這個(gè)比例可能降低了,大概是因?yàn)楝F(xiàn)在的排序算法更加高效?,F(xiàn)在這個(gè)時(shí)代數(shù)據(jù)可以說是無處不在,而整理數(shù)據(jù)的第一步往往就是進(jìn)行排序。所有的計(jì)算機(jī)系統(tǒng)都實(shí)現(xiàn)了各種排序算法以供系統(tǒng)和用戶使用。
  即使你只是使用標(biāo)準(zhǔn)庫中的排序函數(shù),學(xué)習(xí)排序算法仍然有很大的實(shí)際意義:

排序算法往往是我們解決其他問題的第一步

排序算法有助于我們理解其他算法

算法在公司面試中占有很大比例,排序算法作為其中的重要組成部分,我們理所當(dāng)然要學(xué)好了。

  另外,更重的是下面介紹的這些算法都很經(jīng)典,優(yōu)雅而且高效,學(xué)習(xí)其中的精髓對(duì)自己提高自己的編程能力也有很大的幫助。
  排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計(jì)算中有很重要的地位,它能夠應(yīng)用于事務(wù)處理,組合優(yōu)化,天體物理學(xué),分子動(dòng)力學(xué),語言學(xué),基因組學(xué),天氣預(yù)報(bào)和很多其他領(lǐng)域。下面會(huì)介紹的一種排序算法(快速排序)甚至被譽(yù)為20世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。后面我們會(huì)依次學(xué)習(xí)幾種經(jīng)典的排序算法,并高效地實(shí)現(xiàn)“優(yōu)先隊(duì)列”這種基礎(chǔ)數(shù)據(jù)類型。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。

第一章——初始初級(jí)排序算法 一,我知道的第一個(gè)排序算法——冒泡排序 1. 介紹: 

  這是比較簡(jiǎn)單的一種的排序算法,應(yīng)該是我們大學(xué)最先接觸到的一個(gè)排序算法了。很簡(jiǎn)單的一種排序算法,大學(xué)里好像也是每次必考的吧!

2. 原理:

  比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。 對(duì)每一對(duì)相鄰元素作同樣的工作,從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
代碼實(shí)現(xiàn):

3. 實(shí)現(xiàn)代碼
    public static void bubbleSort(int[] numbers) {
        int temp = 0;
        int size = numbers.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                 // 交換兩數(shù)位置
                if (numbers[j] > numbers[j + 1])
                {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }
二,另一個(gè)簡(jiǎn)單排序算法——選擇排序 1. 介紹: 

  選擇排序市一中很容易理解和實(shí)現(xiàn)的簡(jiǎn)單排序算法。學(xué)習(xí)它之前首先要知道它的兩個(gè)很鮮明的特點(diǎn)。

運(yùn)行時(shí)間和輸入無關(guān)。為了找出最小的元素而掃描一遍數(shù)組并不能為下一遍掃描提供任何實(shí)質(zhì)性幫助的信息。因此使用這種排序的我們會(huì)驚訝的發(fā)現(xiàn),一個(gè)已經(jīng)有序的數(shù)組或者數(shù)組內(nèi)元素全部相等的數(shù)組和一個(gè)元素隨機(jī)排列的數(shù)組所用的排序時(shí)間竟然一樣長(zhǎng)!而其他算法會(huì)更善于利用輸入的初始狀態(tài),選擇排序則不然。

數(shù)據(jù)移動(dòng)是最少的選擇排序的交換次數(shù)和數(shù)組大小關(guān)系是線性關(guān)系??聪旅娴脑頃r(shí)可以很容易明白這一點(diǎn)。

2. 原理:

  在要排序的一組數(shù)中,選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換;然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換,如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。類似下圖:

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

3. 實(shí)現(xiàn)代碼
    public static void selectSort(int[] numbers) {
        // 數(shù)組長(zhǎng)度
        int size = numbers.length; 
        // 中間變量
        int temp = 0; 

        for (int i = 0; i < size; i++) {
            // 待確定的位置
            int k = i; 
            // 選擇出應(yīng)該在第i個(gè)位置的數(shù)
            for (int j = size - 1; j > i; j--) {
                if (numbers[j] < numbers[k]) {
                    k = j;
                }
            }
            // 交換兩個(gè)數(shù)
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
        }
    }
三,另一個(gè)簡(jiǎn)單排序算法——插入排序 1. 介紹: 

  通常人們整理橋牌的方法是一張一張的來,將每一張牌插入到其他已經(jīng)有序牌中的適當(dāng)位置。在計(jì)算機(jī)的實(shí)現(xiàn)中,為了給要插入的元素騰出空間,我們需要將其余所有元素在插入之前都向右移動(dòng)以為。這種算法就叫插入排序。
 ** 與選擇排序一樣,當(dāng)前索引左邊的所有元素都是有序的,但他們的最終位置還不確定為了給更小的元素騰出空間,他們可能會(huì)被移動(dòng)。但是當(dāng)索引到達(dá)數(shù)組的右端時(shí),數(shù)組排序就完成了。
  和選擇排序不同的是,插入排序所需的時(shí)間取決于輸入中元素的初始順序。也就是說對(duì)一個(gè)接近有序或有序的數(shù)組進(jìn)行排序會(huì)比隨機(jī)順序或是逆序的數(shù)組進(jìn)行排序要快的多。**

2. 原理: 

  每步將一個(gè)待排序的記錄,按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位置(從后向前找到合適位置后),直到全部插入排序完為止。類似下圖:
  

3. 實(shí)現(xiàn)代碼
    /**
     * 插入排序
     * 
     * 從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序 取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描
     * 如果該元素(已排序)大于新元素,將該元素移到下一位置 重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置 將新元素插入到該位置中 重復(fù)步驟2
     * 
     * @param numbers
     *            待排序數(shù)組
     */
    public static void insertSort(int[] numbers) {
        int size = numbers.length;
        int temp = 0;
        int j = 0;

        for (int i = 0; i < size; i++) {
            temp = numbers[i];
            // 假如temp比前面的值小,則將前面的值后移
            for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
                numbers[j] = numbers[j - 1];
            }
            numbers[j] = temp;
        }
    }
四,希爾排序 1. 介紹:

  這個(gè)排序咋一看名字感覺很高大上,這是以D.L.shell名字命名的排序算法。
  為了展示初級(jí)排序算法性質(zhì)的價(jià)值,我們來看一下基于插入排序的快速的排序算法——希爾排序。對(duì)于大規(guī)模亂序的數(shù)組插入排序很慢,因?yàn)樗粫?huì)交換相鄰的元素,因此元素只能一點(diǎn)一點(diǎn)地從數(shù)組的一端移動(dòng)到另一端。如果最小的元素剛好在數(shù)組的盡頭的話,那么要將它移動(dòng)到正確的位置要N-1次移動(dòng)。希爾排序?yàn)榱思涌焖俣群?jiǎn)單地改進(jìn)了插入排序,交換不相鄰的元素以對(duì)數(shù)組的局部進(jìn)行排序,并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。

2. 原理:

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個(gè)序列中的記錄“基本有序”時(shí),再對(duì)全體記錄進(jìn)行依次直接插入排序。

3. 實(shí)現(xiàn)代碼
 /**
     * 希爾排序的原理:根據(jù)需求,如果你想要結(jié)果從大到小排列,它會(huì)首先將數(shù)組進(jìn)行分組,然后將較大值移到前面,較小值
     * 移到后面,最后將整個(gè)數(shù)組進(jìn)行插入排序,這樣比起一開始就用插入排序減少了數(shù)據(jù)交換和移動(dòng)的次數(shù),可以說希爾排序是加強(qiáng) 版的插入排序 拿數(shù)組5, 2,
     * 8, 9, 1, 3,4來說,數(shù)組長(zhǎng)度為7,當(dāng)increment為3時(shí),數(shù)組分為兩個(gè)序列
     * 5,2,8和9,1,3,4,第一次排序,9和5比較,1和2比較,3和8比較,4和比其下標(biāo)值小increment的數(shù)組值相比較
     * 此例子是按照從大到小排列,所以大的會(huì)排在前面,第一次排序后數(shù)組為9, 2, 8, 5, 1, 3,4
     * 第一次后increment的值變?yōu)?/2=1,此時(shí)對(duì)數(shù)組進(jìn)行插入排序, 實(shí)現(xiàn)數(shù)組從大到小排
     */

    public static void shellSort(int[] data) {
        int j = 0;
        int temp = 0;
        // 每次將步長(zhǎng)縮短為原來的一半
        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < data.length; i++) {
                temp = data[i];
                for (j = i; j >= increment; j -= increment) {
                   // 如想從小到大排只需修改這里
                    if (temp > data[j - increment])
                    {
                        data[j] = data[j - increment];
                    } else {
                        break;
                    }

                }
                data[j] = temp;
            }

        }
    }
第二章——進(jìn)階之歸并排序 1, 介紹

  歸并即將兩個(gè)有序的數(shù)組歸并并成一個(gè)更大的有序數(shù)組。人們很快根據(jù)這個(gè)思路發(fā)明了一種簡(jiǎn)單的遞歸排序算法:歸并排序。要將一個(gè)數(shù)組排序,可以先(遞歸地)將它分成兩半分別排序,然后將結(jié)果歸并起來。歸并排序最吸引人的性質(zhì)是它能保證任意長(zhǎng)度為N的數(shù)組排序所需時(shí)間和NlogN成正比;它的主要缺點(diǎn)也顯而易見就是它所需的額外空間和N成正比。簡(jiǎn)單的歸并排序如下圖:

2,原理

  歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
  合并方法:
  設(shè)r[i…n]由兩個(gè)有序子表r[i…m]和r[m+1…n]組成,兩個(gè)子表長(zhǎng)度分別為n-i +1、n-m。

1、j=m+1;k=i;i=i; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)
2、若i>m 或j>n,轉(zhuǎn)⑷ //其中一個(gè)子表已合并完,比較選取結(jié)束
3、//選取r[i]和r[j]較小的存入輔助數(shù)組rf
        如果r[i]
3,實(shí)現(xiàn)代碼
/**
     * 歸并排序 簡(jiǎn)介:將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表
     * 即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列 時(shí)間復(fù)雜度為O(nlogn) 穩(wěn)定排序方式
     * 
     * @param nums
     *            待排序數(shù)組
     * @return 輸出有序數(shù)組
     */

    public static int[] mergeSort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左邊
            mergeSort(nums, low, mid);
            // 右邊
            mergeSort(nums, mid + 1, high);
            // 左右歸并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    /**
     * 將數(shù)組中l(wèi)ow到high位置的數(shù)進(jìn)行排序
     * 
     * @param nums
     *            待排序數(shù)組
     * @param low
     *            待排的開始位置
     * @param mid
     *            待排中間位置
     * @param high
     *            待排結(jié)束位置
     */
    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指針
        int j = mid + 1;// 右指針
        int k = 0;

        // 把較小的數(shù)先移到新數(shù)組中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 把左邊剩余的數(shù)移入數(shù)組
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 把右邊邊剩余的數(shù)移入數(shù)組
        while (j <= high) {
            temp[k++] = nums[j++];
        }

        // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }
第三章——進(jìn)階之快速排序 前言:

  快速排序可能是應(yīng)用最廣泛的排序算法了??焖倥判蛄餍械脑蛑饕?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單,適用于不同的輸入數(shù)據(jù)且在一般應(yīng)用中比其他排序算法都要快得多??焖倥判蛞俗⒛康奶攸c(diǎn)包括它是原地排序(只需要一個(gè)很小的輔助棧),且將長(zhǎng)度為N的數(shù)組排序所需要的時(shí)間和NlgN成正比。我們之前提到的幾種排序算法都無法將這兩個(gè)優(yōu)點(diǎn)結(jié)合起來。另外,快速排序的內(nèi)循環(huán)比大多數(shù)排序算法都要短小,這意味著它無論是理論上還是實(shí)際中都要更快。它的主要缺點(diǎn)是非常脆弱,在實(shí)現(xiàn)時(shí)要非常小心才能避免低劣的性能。已經(jīng)有無數(shù)例子顯示許多錯(cuò)誤都能致使它在實(shí)際應(yīng)用中的性能只有平方級(jí)別。不過還好,我們由這些缺點(diǎn)和教訓(xùn)中大大改進(jìn)了快速排序算法,使它的應(yīng)用更加廣泛。

1,介紹

  快速排序是一種分治的排序算法。它將一個(gè)數(shù)組分成兩個(gè)字?jǐn)?shù)組,將兩部分獨(dú)立地排序??焖倥判蚝蜌w并排序是互補(bǔ)的:歸并排序?qū)?shù)組分成兩個(gè)字?jǐn)?shù)組分別排序,并將有序的字?jǐn)?shù)組歸并以將整個(gè)數(shù)組排序;而快速排序?qū)?shù)組排序的方式則是當(dāng)兩個(gè)字?jǐn)?shù)組都有序時(shí)整個(gè)數(shù)組也就自然有序了。在第一種情況中,遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之前;在第二種情況中,遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之后。在歸并排序中,一個(gè)數(shù)組被等分為兩半;快速排序中,切分的位置取決于數(shù)組的內(nèi)容??焖倥判虻倪^程大致如下:

2,原理

快速排序的基本思想
  通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分,一部分全小于選取的參考值,另一部分全大于選取的參考值。這樣分別對(duì)兩部分排序之后順序就可以排好了。
例子:
(a)一趟排序的過程:

(b)排序的全過程:

3,實(shí)現(xiàn)代碼
    /**
     * 查找出中軸(默認(rèn)是最低位low)的在numbers數(shù)組排序后所在位置
     * 
     * @param numbers 帶查找數(shù)組
     * @param low 開始位置
     * @param high 結(jié)束位置
     * @return 中軸所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        // 數(shù)組的第一個(gè)作為中軸
        int temp = numbers[low]; 
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            // 比中軸小的記錄移到低端
            numbers[low] = numbers[high];
            while (low < high && numbers[low] < temp) {
                low++;
            }
            // 比中軸大的記錄移到高端
            numbers[high] = numbers[low]; 
        }
        numbers[low] = temp; // 中軸記錄到尾
        return low; // 返回中軸的位置
    }

    /**
     * 
     * @param numbers 帶排序數(shù)組
     * @param low 開始位置
     * @param high 結(jié)束位置
     */
    public static void quick(int[] numbers, int low, int high) {
        if (low < high) {
            int middle = getMiddle(numbers, low, high); // 將numbers數(shù)組進(jìn)行一分為二
            quick(numbers, low, middle - 1); // 對(duì)低字段表進(jìn)行遞歸排序
            quick(numbers, middle + 1, high); // 對(duì)高字段表進(jìn)行遞歸排序
        }

    }

    /**
     * 快速排序
     * 快速排序提供方法調(diào)用
     * @param numbers 帶排序數(shù)組
     */
    public static void quickSort(int[] numbers) {
        // 查看數(shù)組是否為空
        if (numbers.length > 0) 
        {
            quick(numbers, 0, numbers.length - 1);
        }
    }
4,改進(jìn)方法

我們只介紹一種常用的,具體代碼就不貼出了。想去的可以去https://algs4.cs.princeton.ed... 這個(gè)網(wǎng)站找。
三向切分快速排序
  核心思想就是將待排序的數(shù)據(jù)分為三部分,左邊都小于比較值,右邊都大于比較值,中間的數(shù)和比較值相等.三向切分快速排序的特性就是遇到和比較值相同時(shí),不進(jìn)行數(shù)據(jù)交換, 這樣對(duì)于有大量重復(fù)數(shù)據(jù)的排序時(shí),三向切分快速排序算法就會(huì)優(yōu)于普通快速排序算法,但由于它整體判斷代碼比普通快速排序多一點(diǎn),所以對(duì)于常見的大量非重復(fù)數(shù)據(jù),它并不能比普通快速排序多大多的優(yōu)勢(shì) 。

歡迎關(guān)注我的微信公眾號(hào)(分享各種Java學(xué)習(xí)資源,面試題,以及企業(yè)級(jí)Java實(shí)戰(zhàn)項(xiàng)目回復(fù)關(guān)鍵字免費(fèi)領(lǐng)?。?/strong>

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/68845.html

相關(guān)文章

  • 金三銀四背后,一個(gè) Android 程序員面試心得

    摘要:到十二月份,公司開始第二波裁員,我決定主動(dòng)拿賠償走人。加一個(gè)小插曲上面的題是餓了嗎面試問到的。想去的公司沒有面試好,不要?dú)怵H,繼續(xù)加油準(zhǔn)備。避免打擊自信心。 回顧一下自己這段時(shí)間的經(jīng)歷,九月份的時(shí)候,公司通知了裁員,我匆匆忙忙地出去面了幾家,但最終都沒有拿到offer,我感覺今年的寒冬有點(diǎn)冷。到十二月份,公司開始第二波裁員,我決定主動(dòng)拿賠償走人。后續(xù)的面試過程我做了一些準(zhǔn)備,基本都能走...

    Achilles 評(píng)論0 收藏0
  • 博客 - 收藏集 - 掘金

    摘要:技術(shù)之類加載機(jī)制掘金類加載機(jī)制是語言的一大亮點(diǎn),使得類可以被動(dòng)態(tài)加載到虛擬機(jī)中。玩轉(zhuǎn)仿探探卡片式滑動(dòng)效果掘金講起本篇博客的歷史起源,估計(jì)有一段歷史了。 Java 技術(shù)之類加載機(jī)制 - Android - 掘金類加載機(jī)制是 Java 語言的一大亮點(diǎn),使得 Java 類可以被動(dòng)態(tài)加載到 Java 虛擬機(jī)中。 這次我們拋開術(shù)語和概念,從例子入手,由淺入深地講解 Java 的類加載機(jī)制。 本文...

    Shimmer 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<