基本算法之排序

把我上學時候在csdn上的筆記搬過來了

簡單選擇排序

選擇排序要用到交換胳挎,在開始之前不妨說下數(shù)值交換的三種方法

臨時變量

public static void swap(int[] arr, int i, int j) {
        if (i != j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

加法

public static void swap(int[] arr, int i, int j) {
        if (i != j) {
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
        }

    }

異或

public static void swap(int[] arr, int i, int j) {
            if(i!=j){
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }

}

簡單選擇排序思路很簡單署照,就是每次遍歷數(shù)組獲得最小值得位置,然后將最小值與數(shù)組中第一個值交換簇秒,然后從第二個值開始遍歷獲得最小值與第二個元素交換,以此類推。

public static void selectSort(int[] arr) {
        int min;
        for (int i = 0; i < arr.length; i++) {
            min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(arr, min, i);
        }
    }

最好最肺缕、壞時間復雜度都是O(n2)。內層for循環(huán)執(zhí)行次數(shù)依次為n-1授帕,n-2同木,n-3,……,1。加起來為n(n-1)/2 跛十。 該算法是不穩(wěn)定的泉手,很容易理解,由于交換的時候偶器,會改變兩個相等值得相對位置斩萌。

直接插入排序

將序列中的第一個元素作為一個有序序列缝裤,然后將剩下的n-1個元素按照關鍵字大小依次插入該有序序列,每插入一個元素后依然保持該序列有序颊郎,經過n-1趟排序后即成為有序序列憋飞。

public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int temp = arr[i];
            while (j > 0 && temp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }

算法必須進行n-1趟。最好情況下姆吭,每趟都比較一次榛做,時間復雜度為O(n);最壞情況下的時間復雜度為O(n2)内狸。 插入排序是穩(wěn)定的检眯,當然這與循環(huán)條件中”temp < arr[j - 1]”密切相關,如果改為”temp < =arr[j - 1]” 那么就不穩(wěn)定了昆淡。

冒泡排序

第一趟在數(shù)組(arr[0]-arr[n-1])中從前往后進行兩個相鄰元素的比較锰瘸,若后者小,則交換昂灵,比較n-1次避凝;第一趟排序結束,最大的元素到 arr[n-1] 中 眨补;下一趟排序在子數(shù)組arr[0]-arr[n-2]中進行管削;如果在某一趟排序中未交換元素,說明子序列已經有序撑螺,不需要再進行下一趟排序含思。

public static void bubbleSort(int[] arr) {
        int i = arr.length - 1;
        int last;//記錄某趟最后交換的位置,其后的元素都是有序的
        while (i > 0) {
            last=0;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    last= j;
                }
            }
            i=last;
        }
    }

其中變量last主要是要記錄甘晤,某趟遍歷時最后一次交換的位置茸俭。在last之后的元素其實都已經在排序結果中正確的位置。后面再進行下一趟時安皱,只要從arr[0]到arr[last] 進行操作即可调鬓。最終當last=0時,就說明arr[0]之后的元素都已經在正確的位置了酌伊,那么只剩arr[0]肯定也是在正確的位置腾窝。
該算法最多進行n-1趟。冒泡排序在已排序的情況下是最好情況居砖,只用進行一趟虹脯,比較n-1次,時間復雜度為O(n) ; 最壞情況下要進行n-1趟奏候,第i每次比較n-i次循集,移動3(n-i)次,時間復雜度為O(n2); 冒泡排序是穩(wěn)定的排序算法蔗草,這當然也與算法中的判斷條件相關咒彤。

快速排序

快排簡略來說就是一種分治的思想疆柔。對一個數(shù)組,選定一個基準元素x镶柱,把數(shù)組劃分為兩個部分旷档,低端部分都比x小,高端元素都比x大歇拆,那么此時基準元素就在正確的位置了鞋屈。然后再分別都低端部分和高端部分,分別進行上面的步驟故觅,直到子數(shù)組中只有一個元素為止厂庇。

遞歸版

public static void quickSort(int[] arr) {
        qSort(arr, 0, arr.length - 1);
    }

    private static void qSort(int[] arr, int left, int right) {
        //如果分割元素角標p為子數(shù)組的邊界,那么分割后就只有低端序列或者高端序列输吏,此時判斷防止角標越界
        if(left==right){
            return;
        }
        int p = partition(arr, left, right);
        qSort(arr, left, p - 1);
        qSort(arr, p+1,right);
    }

    /**
     * 把數(shù)組分為兩部分
     * 
     * @param arr
     * @param left
     *            子數(shù)組最小角標
     * @param right
     *            子數(shù)組最大角標
     * @return 返回分割元素的角標
     */
    private static int partition(int[] arr, int left, int right) {
        int base = arr[right];
        int small=left-1;//用來記錄小于base的數(shù)字放到左邊第幾個位置
        for(int i=left;i<right;i++){
            if(arr[i]<base){
                small++;
                swap(arr,small,i);
            }
        }
        small++;
        swap(arr, small,right);
        return small;
    }

非遞歸版

    public static void quickSort(int[] arr){
        Deque<Integer> leftStack=new ArrayDeque<Integer>();
        Deque<Integer> rightStack=new ArrayDeque<Integer>();
        leftStack.addFirst(0);
        rightStack.addFirst(arr.length-1);
        while(leftStack.size()!=0){
            Integer left = leftStack.removeFirst();
            Integer right = rightStack.removeFirst();
            int p = partition(arr, left, right);
            if(p>left){
                leftStack.addFirst(left);
                rightStack.addFirst(p-1);
            }
            if(p<right){
                leftStack.addFirst(p+1);
                rightStack.addFirst(right);
            }
        }
    }

上面partition函數(shù)中每次選擇子數(shù)組中第一個元素作為基準元素权旷,當然你也可以選擇其他的。
當初始數(shù)組有序(順序或逆序)時评也,快排效率最低炼杖,因為每次分割后有一個子數(shù)組是空灭返,時間復雜度是O(n2)盗迟;在平均情況下可以證明快排的時間復雜度是O(nlogn)。
在最壞的情況下空間復雜度是O(n),最好的情況下是O(logn)熙含。
我們可以看出無論是遞歸還是非遞歸罚缕,快排至少O(logn)的空間復雜度,這個是省不掉的怎静。
快排是不穩(wěn)定的邮弹。

歸并排序

把n個長度的數(shù)組看成是n個長度為1的數(shù)組,然后兩兩合并時排序蚓聘,得到n/2個長度為2的數(shù)組(可能包含一個1); 繼續(xù)兩兩合并排序腌乡,依次類推。

歸并排序算法的核心是合并夜牡,我具體來說一下合并的思路与纽。比如我們有數(shù)組A,B,此時我們要在合并時排序,需要一個臨時數(shù)組C塘装。用leftPosition急迂,rightPosition和tempPositon 分別來指示數(shù)組元素,它們的起始位置對應數(shù)組的始端。A[leftPostion]和B[rightPosition]中較小者被拷貝到C中tempPostion的位置蹦肴。相關的指示器加1僚碎。當A和B中有一個用完時,另一個數(shù)組中的剩余部分直接拷貝到C中阴幌。

代碼如下:

    /**
     * @param arr
     *            數(shù)組
     * @param tempArr
     *            臨時數(shù)組勺阐,用于臨時存放合并后的結果
     * @param leftPostion
     *            第一個子數(shù)組的開始
     * @param rightPosition
     *            第二個字數(shù)組的開始位置
     * @param rightEnd
     *            第二個子數(shù)組的結束位置
     */
    private static void merge(int[] arr, int[] tempArr, int leftPostion,
            int rightPosition, int rightEnd) {
        int leftEnd = rightPosition - 1;
        int tempPositon = leftPostion;

        int begin=leftPostion;
        while (leftPostion <= leftEnd && rightPosition <= rightEnd) {
            if(arr[leftPostion]<arr[rightPosition]){
                tempArr[tempPositon++]=arr[leftPostion++];
            }else {
                tempArr[tempPositon++]=arr[rightPosition++];
            }
        }
        while(leftPostion<=leftEnd){
            tempArr[tempPositon++]=arr[leftPostion++];
        }
        while(rightPosition<=rightEnd){
            tempArr[tempPositon++]=arr[rightPosition++];
        }

        //復制到原數(shù)組
        for(int i=begin;i<=rightEnd;i++){
            arr[i]=tempArr[i];
        }

    }


private static void mergeSort(int[] arr, int[] tempArr, int left, int right) {
            if(left<right){//如果只有一個子數(shù)組只有一個元素就直接返回
                int mid=(left+right)/2;
                mergeSort(arr,tempArr,left,mid);
                mergeSort(arr,tempArr,mid+1,right);
                merge(arr, tempArr, left, mid+1, right);
            }
    }


public static void mergeSort(int[] arr) {
        int[] tempArr=new int[arr.length];
        mergeSort(arr,tempArr,0,arr.length-1);
    }

下面我們來證明一下歸并排序的時間復雜度卷中,我們假設元素個數(shù)n是2的冪,這樣總是能將數(shù)組分為相等的兩部分皆看。
當n=1,歸并排序的時間 T(1)=1 ;
對于任意n個元素歸并排序的時間是兩個n2n2大小歸并排序的時間加上合并的時間仓坞。容易看出合并的時間是線性的,因為合并連個數(shù)組時腰吟,最多進行N-1比較无埃,即每比較依次肯定會有一個數(shù)加入到臨時數(shù)組中去的。
T(n)=T(n2n2)+n
等式兩邊同除以n毛雇,
T(n)nT(n)n=T(n/2)n/2T(n/2)n/2+1
該方程對2的冪的任意n都是成立的嫉称,我們每次除2可以得到下面的一系列等式:
T(n/2)n/2T(n/2)n/2=T(n/4)n/4T(n/4)n/4+1
T(n/4)n/4T(n/4)n/4=T(n/8)n/8T(n/8)n/8+1

T(2)2T(2)2=T(1)1T(1)1+1

明顯這些等式一共有l(wèi)ogn個。
然后把所有這些等式相加灵疮,消去左邊和右邊相等的項织阅,所得結果為T(n)nT(n)n=T(1)1T(1)1+logn
稍作變?yōu)門(n)=nlogn+n=O(nlogn)
另外歸并排序需要O(n)的空間復雜度,是一種穩(wěn)定的排序算法震捣。

堆排序

將初始數(shù)組構造成最大堆荔棉,第一趟排序,將堆頂元素arr[0]和堆底元素arr[n-1]交換位置蒿赢,然后將再將arr[0]往下調整润樱,使得剩余的n-1個元素還是堆;第i趟時羡棵,arr[0]與arr[n-i]交換壹若,arr[0]往下調整,使得剩余的n-i個元素還是堆皂冰;直到堆中只剩一個元素結束店展。

    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 構建初始堆
        for (int i = (n - 1) / 2; i >= 0; i--)
            percDown(arr, i, n - 1);
        // 排序,其實相當于每次刪除最大元素秃流,然后將剩下的最后一個元素換到0位置赂蕴,重新調整
        for (int i = 1; i < n; i++) {
            swap(arr, 0, n - i);
            percDown(arr, 0, n - i - 1);
        }
    }

    /**
     * @param arr
     *            數(shù)組
     * @param i
     *            要調整的那個元素的位置
     * @param n
     *            堆最后一個元素的角標
     */
    private static void percDown(int[] arr, int i, int n) {
        int temp = arr[i];
        int child = 2 * i + 1;
        while (child <= n) {
            if (child < n && arr[child] < arr[child + 1])
                child++;
            if (temp < arr[child]) {
                arr[i] = arr[child];
                i = child;// 讓i指向當前child的位置
                child = 2 * i + 1;// 獲得新的child
            }else{
                break;
            }
        }
        arr[i] = temp;
    }

percDown函數(shù)時間復雜度不超過O(logn),構造堆的最多時間為O(nlogn)。排序部分進行n-1趟舶胀,也是O(nlogn),所以總的時間復雜度還會O(nlogn)概说。
一趟排序可以確定一個元素的最終位置,堆排序是不穩(wěn)定的排序算法峻贮。

希爾排序

簡單來說就是分組插入排序席怪,它通過比較相距一定間隔的元素來工作;各趟比較所用的距離隨著算法的進行而減小纤控,直到只比較相鄰元素的最后一趟排序為止挂捻,因此也叫作縮減增量排序。
關于增量序列h1船万,h2刻撒,h3骨田,….,ht 只要是h1=1等任何增量序列都是可行的,因為最后一趟h1=1声怔,那么進行的工作就是插入排序啊态贤。
看到這里你也許會好奇,其實希爾排序最后一趟和插入排序做的工作就是一模一樣啊醋火,為什么在選取某些增量序列悠汽,比如Hibbard增量(1,3,7,…,2k2k-1)的情況下芥驳,時間復雜度為O(n32n32) 柿冲。

插入排序的性質:

插入排序在對幾乎已經排好序的數(shù)據(jù)操作時,效率高兆旬,即可以達到線性排序的效率假抄。
但插入排序一般來說是低效的,因為插入排序每次只能將數(shù)據(jù)移動一位丽猬。

所以希爾排序每趟做的工作宿饱,會對下一趟的排序有幫助,并且希爾排序能一次移動消除多個逆序對脚祟。
這里還是選用很常見的序列 ht=N/2,hk=hk+1/2,選用這個增量序列谬以,算法復雜度為O(n2n2)。
代碼如下:

public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[i];
                while (j >= gap && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }
                arr[j] = temp;
            }
        }
  }

我們知道一次插入排序是穩(wěn)定的愚铡,不會改變相同元素的相對順序蛉签,但在不同的插入排序過程中胡陪,相同的元素可能在各自的插入排序中移動沥寥,最后其穩(wěn)定性就會被打亂,所以shell排序是不穩(wěn)定的

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末柠座,一起剝皮案震驚了整個濱河市邑雅,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌妈经,老刑警劉巖淮野,帶你破解...
    沈念sama閱讀 217,277評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異吹泡,居然都是意外死亡骤星,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評論 3 393
  • 文/潘曉璐 我一進店門爆哑,熙熙樓的掌柜王于貴愁眉苦臉地迎上來洞难,“玉大人,你說我怎么就攤上這事揭朝《蛹” “怎么了色冀?”我有些...
    開封第一講書人閱讀 163,624評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長柱嫌。 經常有香客問我锋恬,道長,這世上最難降的妖魔是什么编丘? 我笑而不...
    開封第一講書人閱讀 58,356評論 1 293
  • 正文 為了忘掉前任与学,我火速辦了婚禮,結果婚禮上嘉抓,老公的妹妹穿的比我還像新娘癣防。我一直安慰自己,他們只是感情好掌眠,可當我...
    茶點故事閱讀 67,402評論 6 392
  • 文/花漫 我一把揭開白布蕾盯。 她就那樣靜靜地躺著,像睡著了一般蓝丙。 火紅的嫁衣襯著肌膚如雪级遭。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,292評論 1 301
  • 那天渺尘,我揣著相機與錄音挫鸽,去河邊找鬼。 笑死鸥跟,一個胖子當著我的面吹牛丢郊,可吹牛的內容都是我干的。 我是一名探鬼主播医咨,決...
    沈念sama閱讀 40,135評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼枫匾,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了拟淮?” 一聲冷哼從身側響起干茉,我...
    開封第一講書人閱讀 38,992評論 0 275
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎很泊,沒想到半個月后角虫,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經...
    沈念sama閱讀 45,429評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡委造,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,636評論 3 334
  • 正文 我和宋清朗相戀三年戳鹅,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片昏兆。...
    茶點故事閱讀 39,785評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡枫虏,死狀恐怖,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情模软,我是刑警寧澤伟骨,帶...
    沈念sama閱讀 35,492評論 5 345
  • 正文 年R本政府宣布,位于F島的核電站燃异,受9級特大地震影響携狭,放射性物質發(fā)生泄漏。R本人自食惡果不足惜回俐,卻給世界環(huán)境...
    茶點故事閱讀 41,092評論 3 328
  • 文/蒙蒙 一逛腿、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧仅颇,春花似錦单默、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至耕皮,卻和暖如春境蜕,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背凌停。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評論 1 269
  • 我被黑心中介騙來泰國打工粱年, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人罚拟。 一個月前我還...
    沈念sama閱讀 47,891評論 2 370
  • 正文 我出身青樓台诗,卻偏偏與公主長得像,于是被迫代替她去往敵國和親赐俗。 傳聞我的和親對象是個殘疾皇子拉队,可洞房花燭夜當晚...
    茶點故事閱讀 44,713評論 2 354

推薦閱讀更多精彩內容