排序問題

一凹炸、插入排序

遍歷數(shù)組的元素洞渤,nums[i]如果比nums[i-1]小雪隧,就說明需要將其插入到nums[0]....nums[i-1]的序列中碍讯。

var sortArray = function(nums) {
    var lookout = nums[0];  //監(jiān)視哨悬蔽,提供nums[i]的緩存單元
    for(var i=1;i<=nums.length;i++){
        if(nums[i] < nums[i-1]){
            lookout = nums[i];  // 將nums[i]保存到監(jiān)視哨中
            // 逐級后移
            for(var j=i-1;j>=0 && nums[j]>lookout;j--){ 
                nums[j+1] = nums[j];
            }
            // 插入nums[i]
            nums[j+1] = lookout;
        }
    }
    return nums;
};

算法復雜度:O(n^2)

二、希爾排序

將待排序數(shù)組根據(jù)一定的增量分組捉兴,每一組都進行插入排序蝎困,再減少增量,每組元素變多倍啥,當增量減至1時禾乘,整個文件恰被分成一組,對該組排序進行微調虽缕,算法便終止始藕。

var sortArray = function(nums) {
        var len = nums.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] > temp) {
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return nums;
}

算法復雜度:O(nlogn)

三、冒泡排序

在一趟比較中彼宠,比較相鄰兩個元素nums[j]和nums[j+1]的大小鳄虱,如果nums[j]>nums[j+1],兩元素交換凭峡,這樣最大的元素冒泡到數(shù)組的最右邊拙已。重復上述步驟,直到不存在需要交換的元素摧冀,結束循環(huán)倍踪。

var sortArray = function(nums) {
    var tmp;
    if(nums.length == 0) return [];
    for(var i=0;i<nums.length;i++){
        for(var j=0;j<nums.length-i;j++){
            if(nums[j] > nums[j+1]){
                tmp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = tmp;
            }
            // console.log(nums)
        }
    }
    return nums;
};

復雜度O(n^2)

四、快速排序

以序列中第一個元素作為基準索昂,在比較分區(qū)的過程中建车,如果比這個數(shù)小的就放在左邊,比這個數(shù)大的放在右邊椒惨,返回這個基準數(shù)在序列中的位置缤至;在這一趟比較中,比基準數(shù)小的數(shù)就全部在其左邊康谆,大的數(shù)全部在其右邊领斥。對左右區(qū)間分別重復上述步驟嫉到,直到區(qū)間中只有一個元素(low=high=0)。

var sortArray = function(nums) {
    // 快速排序
    quickSort(nums,0,nums.length-1);
    return nums;
};

var getPivot = function(nums,low,high){
    var pivot;
    while(low<high){
        while(low<high && nums[high] >= nums[low]){
            // 向前尋找比基準數(shù)小的元素
            high--;
        }
        if(nums[high] < nums[low]){
            // 較小的元素交換到基準數(shù)左邊
            pivot = nums[low]; 
            nums[low] = nums[high];
            nums[high] = pivot;
        }
        while(low<high && nums[low]<=nums[high]){
            // 向后尋找比基準數(shù)大的元素
            low++;
        }
        if(nums[low]>nums[high]){
            // 較大的元素交換到基準數(shù)右邊
            pivot = nums[low]; 
            nums[low] = nums[high];
            nums[high] = pivot;
        }
    }
    return low;
}

var quickSort = function(nums,low,high){
    if(low<high){
        var i = getPivot(nums,low,high); // 返回基準數(shù)位置
        quickSort(nums,low,i-1); // 對左右區(qū)間分別重復操作
        quickSort(nums,i+1,high);
}

復雜度O(nlogn)

五月洛、選擇排序

將序列分為排序序列和未排序序列何恶,初始狀態(tài)下排序序列只有一個元素,即原序列的第一個元素嚼黔。選擇未排序序列中最小的元素细层,將它交換到排序序列的最后一位。重復上述操作唬涧。

var sortArray = function(nums) {
    // 選擇排序
    var sortedNums = nums[0],
        index,
        mintmp,minindex,
        temp;
    for(var i=0;i<nums.length;i++){
        minindex = i;
        mintmp = nums[minindex];
        for(var j=i+1;j<nums.length;j++){
            if(nums[j]<mintmp){
                mintmp = nums[j];
                minindex = j;
            }
        }
        temp = nums[i];
        nums[i] = nums[minindex];
        nums[minindex] = temp;
    }
    return nums;
};

復雜度O(n^2)

六疫赎、歸并排序

將待排序列多次二分成小序列,直到每個小序列只有一個元素為止爵卒。然后將小序列歸并成排好序的較大序列虚缎,直到歸并成最大的序列。
圖分析如下:(來源于https://blog.csdn.net/wojiuguowei/article/details/84321833

歸并排序圖解

var sortArray = function(nums) {
    // 歸并排序
    if(nums.length == 1){
        return nums;
    }
    // 拆分子列
    var mid = parseInt(nums.length/2),
        left = nums.slice(0,mid),
        right = nums.slice(mid,nums.length),
        sortedNums = new Array();
    // 子列不可再分(只有一個元素)后開始歸并
    sortedNums = merge(sortArray(left),sortArray(right));
    return sortedNums;
};

var merge = function(left,right){
    var len_l = left.length, // 序列剩余元素的個數(shù)
        len_r = right.length,
        i = 0,
        j = 0,
        result = [];
    // 左右兩列開始歸并钓株,由于兩列都是有序的实牡,只需要比較開始的元素大小后指針后移即可
    while(i<left.length && j<right.length){
        // if(left[i] == undefined) left[i] = Infinity;
        // if(right[i] == undefined) right[i] = Infinity;
        if(left[i]<right[j]){
            result.push(left[i]);
            i++;
            len_l--;
        }else{
            result.push(right[j]);
            j++;
            len_r--;
        }
    }
    // 考慮到兩序列的長度不一樣,將剩下的序列直接放入result尾部
    while(len_l>0){
        result.push(left[i]);
        i++;
        len_l--;
    }
    while(len_r>0){
        result.push(right[j]);
        j++;
        len_r--;
    }
    return result;
}

復雜度O(nlogn)

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末轴合,一起剝皮案震驚了整個濱河市创坞,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌受葛,老刑警劉巖题涨,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異总滩,居然都是意外死亡纲堵,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門闰渔,熙熙樓的掌柜王于貴愁眉苦臉地迎上來席函,“玉大人,你說我怎么就攤上這事冈涧∶剑” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵督弓,是天一觀的道長营曼。 經(jīng)常有香客問我,道長愚隧,這世上最難降的妖魔是什么蒂阱? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮,結果婚禮上蒜危,老公的妹妹穿的比我還像新娘虱痕。我一直安慰自己,他們只是感情好辐赞,可當我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著硝训,像睡著了一般响委。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上窖梁,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天赘风,我揣著相機與錄音,去河邊找鬼纵刘。 笑死邀窃,一個胖子當著我的面吹牛,可吹牛的內容都是我干的假哎。 我是一名探鬼主播瞬捕,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼舵抹!你這毒婦竟也來了肪虎?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤惧蛹,失蹤者是張志新(化名)和其女友劉穎扇救,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體香嗓,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡迅腔,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了靠娱。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片沧烈。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖饱岸,靈堂內的尸體忽然破棺而出掺出,到底是詐尸還是另有隱情,我是刑警寧澤苫费,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布汤锨,位于F島的核電站,受9級特大地震影響百框,放射性物質發(fā)生泄漏闲礼。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望柬泽。 院中可真熱鬧慎菲,春花似錦、人聲如沸锨并。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽第煮。三九已至解幼,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間包警,已是汗流浹背撵摆。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留害晦,地道東北人特铝。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像壹瘟,于是被迫代替她去往敵國和親鲫剿。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內容

  • 排序算法幾種分類方式: 1俐筋,穩(wěn)定排序和不穩(wěn)定排序 如果a==b牵素, 當排序之前a在b的前面,排序后澄者,a仍然在b...
    fly_ever閱讀 419評論 0 0
  • 排序問題 <!--more--> 排序方法 平均情況 最好情況 最壞情況 輔助空間 ...
    Never_68dd閱讀 152評論 0 0
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個記錄插入到已排序好...
    依依玖玥閱讀 1,262評論 0 2
  • 由于幾乎所有的排序都會用到兩個元素的交換笆呆,所以將交換方法放在這里,每個排序算法中直接使用: 冒泡排序 基本思想:每...
    maxwellyue閱讀 1,964評論 0 0
  • 目錄 荷蘭國旗問題 隨機快排 堆排序 排序算法的穩(wěn)定性及其匯總 工程中的綜合排序算法 比較器的使用 桶排序粱挡、計數(shù)排...
    管弦_閱讀 497評論 0 0