排序

冒泡排序

執(zhí)行時(shí)間
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let temp;
// 優(yōu)化點(diǎn)耿导,如果某次冒泡并沒(méi)有交換搪桂,那后面都不需要交換了
  let flag = false;
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }

    }
    if (flag) {
      flag = false;
    } else {
      break;
    }
  }
}

選擇排序

執(zhí)行時(shí)間


image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let temp;
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    temp = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

插入排序

執(zhí)行時(shí)間
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
console.log(arr);

function sort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let insert = i - 1;
    let temp = arr[i];
    while (insert >= 0 && temp < arr[insert]) {
      arr[insert + 1] = arr[insert];
      insert--;
    }
    arr[insert + 1] = temp;
  }
}

希爾排序-

  1. 交換法

    執(zhí)行時(shí)間
    image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');

function sort(arr) {
  let len = arr.length;
  let temp;
  do {
    len = Math.floor(len / 2);
    for (let i = len; i < arr.length; i++) {
      for (let j = i - len; j >= 0; j -= len) {
        if (arr[j + len] < arr[j]) {
          temp = arr[j];
          arr[j] = arr[j + len];
          arr[j + len] = temp;
        }
      }
    }
  } while (len > 1);
}
  1. 插入法

    執(zhí)行時(shí)間
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let gap = Math.floor(arr.length / 2);
  while (gap >= 1) {
    for (let i = gap; i < arr.length; i++) {
      let j = i - gap;
      let temp = arr[i];
      while (j >= 0 && temp < arr[j]) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;
      // let j = i;
      // let temp = arr[j];
      // if (arr[j] < arr[j - gap]) {
      //   while (j - gap >= 0 && temp < arr[j - gap]) {
      //     arr[j] = arr[j - gap];
      //     j -= gap;
      //   }
      //   arr[j] = temp
      // }


    }
    gap = Math.floor(gap / 2);
  }
}

快速排序

執(zhí)行時(shí)間
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');



function sort(arr, left, right) {
  let l = left;
  let r = right;
  const middle = arr[Math.floor((left + right) / 2)];
  let temp;
  while (l < r) {
    while (arr[l] < middle) {
      l++;
    }
    while (arr[r] > middle) {
      r--;
    }
    if (l == r) {
      r -= 1;
      l += 1;
      break;
    }
    temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
    //  減少一次沒(méi)必要的比較
     if(arr[l]==middle){
      r--;
    }else if(arr[r]==middle){
      l++;
    }else{
      l++;
      r--;
    }
  }
  if (left < r) {
    sort(arr, left, r)
  }
  if (right > l) {
    sort(arr, l, right)
  }

}


歸并排序

執(zhí)行時(shí)間

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');




function sortOrigin(arr, left, mid, right) {
    let i = left;
    let j = mid + 1;
    let temp = [];
    let t = 0;

    while (i <= mid && j <=  right) {

        if (arr[i] < arr[j]) {
            temp[t] = arr[i];
            i++;

        } else {
            temp[t] = arr[j];
            j++;
        }
        t++;
    }
    while (i < mid) {
        temp[t] = arr[i];
        i++;
        t++;
    }
    while (j < right) {
        temp[t] = arr[j];
        j++;
        t++;
    }
    t = 0;
    while (left <= right) {
        arr[left] = temp[t];
        t++;
        left++;
    }


}

function sort(arr, left, right) {
    if (left < right) {
        let mid = Math.floor((left + right) / 2);
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        sortOrigin(arr, left, mid, right)
    }

}

基數(shù)排序

執(zhí)行時(shí)間


let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');

function sort(arr) {
  var max = 0;
  for (let i = 0; i < arr.length; i++) {
    max = Math.max(max, arr[i]);
  }
  var maxLength = (max + '').length;
  let bet = [];
  for (let i = 0; i < 10; i++) {
    bet[i] = [];
  }
  let betLength = new Array(10).fill(0);

  for (let i = 0, step = 1; i < maxLength; i++, step *= 10) {
    for (let j = 0; j < arr.length; j++) {
      let num = Math.floor(arr[j] / step) % 10;
      bet[num][betLength[num]] = arr[j];
      betLength[num]++;
    }
    let t = 0;
    for (let k = 0; k < 10; k++) {
      if (betLength[k]) {
        for (let d = 0; d < betLength[k]; d++) {
          arr[t] = bet[k][d];
          t++;
        }
        betLength[k] = 0;
      }
    }
  }

}

sort(arr);

堆排序

執(zhí)行時(shí)間


image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');

function start(arr) {
  var i = Math.floor(arr.length / 2) - 1
  for (var j = i; j >= 0; j--) {
    sort(arr, j, arr.length)
  }
  var temp;
  for (var j = arr.length - 1; j > 0; j--) {
    temp = arr[j];
    arr[j] = arr[0];
    arr[0] = temp;
    sort(arr, 0, j)
  }
}

function sort(arr, i, len) {
  let temp = arr[i];
  for (let j = i * 2 + 1; j < len; j = j * 2 + 1) {
    if (j + 1 < len && arr[j] < arr[j + 1]) {
      j++;
    }
    if (temp < arr[j]) {
      arr[i] = arr[j]
      i = j
    } else {
      break;
    }
  }
  arr[i] = temp;

}
start(arr)

我的博客即將同步至騰訊云開(kāi)發(fā)者社區(qū)譬挚,邀請(qǐng)大家一同入駐:https://cloud.tencent.com/developer/support-plan?invite_code=2hny1q3rjeyo8

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市特笋,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖律适,帶你破解...
    沈念sama閱讀 217,277評(píng)論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異遏插,居然都是意外死亡捂贿,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評(píng)論 3 393
  • 文/潘曉璐 我一進(jìn)店門胳嘲,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)厂僧,“玉大人,你說(shuō)我怎么就攤上這事了牛∮跸担” “怎么了?”我有些...
    開(kāi)封第一講書人閱讀 163,624評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵白魂,是天一觀的道長(zhǎng)汽纤。 經(jīng)常有香客問(wèn)我,道長(zhǎng)福荸,這世上最難降的妖魔是什么蕴坪? 我笑而不...
    開(kāi)封第一講書人閱讀 58,356評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮敬锐,結(jié)果婚禮上背传,老公的妹妹穿的比我還像新娘。我一直安慰自己台夺,他們只是感情好径玖,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,402評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著颤介,像睡著了一般梳星。 火紅的嫁衣襯著肌膚如雪赞赖。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書人閱讀 51,292評(píng)論 1 301
  • 那天冤灾,我揣著相機(jī)與錄音前域,去河邊找鬼。 笑死韵吨,一個(gè)胖子當(dāng)著我的面吹牛匿垄,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播归粉,決...
    沈念sama閱讀 40,135評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼椿疗,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了糠悼?” 一聲冷哼從身側(cè)響起变丧,我...
    開(kāi)封第一講書人閱讀 38,992評(píng)論 0 275
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎绢掰,沒(méi)想到半個(gè)月后痒蓬,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,429評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡滴劲,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,636評(píng)論 3 334
  • 正文 我和宋清朗相戀三年攻晒,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片班挖。...
    茶點(diǎn)故事閱讀 39,785評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡鲁捏,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出萧芙,到底是詐尸還是另有隱情给梅,我是刑警寧澤,帶...
    沈念sama閱讀 35,492評(píng)論 5 345
  • 正文 年R本政府宣布双揪,位于F島的核電站动羽,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏渔期。R本人自食惡果不足惜运吓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,092評(píng)論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望疯趟。 院中可真熱鬧拘哨,春花似錦、人聲如沸信峻。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 31,723評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)盹舞。三九已至产镐,卻和暖如春隘庄,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背磷账。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 32,858評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工峭沦, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留贾虽,地道東北人逃糟。 一個(gè)月前我還...
    沈念sama閱讀 47,891評(píng)論 2 370
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像蓬豁,于是被迫代替她去往敵國(guó)和親绰咽。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,713評(píng)論 2 354

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