JavaScript的排序算法

booster 發(fā)布于2019-08-26 10:34 / 1397人閱讀

摘要：基本概念時(shí)間復(fù)雜度算法執(zhí)行所耗費(fèi)的時(shí)間。內(nèi)排序所有排序操作都在內(nèi)存中完成。常用的排序算法冒泡排序基本概念依次比較相鄰的兩個(gè)數(shù)將小數(shù)放在前面，大數(shù)放在后面。實(shí)現(xiàn)原理通過(guò)遞歸的方式將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列。

1：基本概念

時(shí)間復(fù)雜度：算法執(zhí)行所耗費(fèi)的時(shí)間。

這個(gè)復(fù)雜度直接和樣本的個(gè)數(shù)有關(guān)，復(fù)雜度反映了算法的性能，一般來(lái)說(shuō)，復(fù)雜度越低，算法所消耗的時(shí)間越短。

    /* O(N1) */
    for (var i = 0; i < data.length; i++) {
        ...
    }
    
    /* O(N2) */
    for (var i = 0; i < data.length; i++) {
        for (var j = 0; j < data.length; j++) {
            ...
        }
    }

空間復(fù)雜度：運(yùn)行一個(gè)程序所需內(nèi)存的大小。

空間復(fù)雜度和時(shí)間復(fù)雜度是對(duì)立的，比如說(shuō)，時(shí)間復(fù)雜度越高，空間復(fù)雜度越低；反之則相反。

內(nèi)排序：所有排序操作都在內(nèi)存中完成。

2：常用的排序算法 冒泡排序（Bubble Sort）

基本概念：依次比較相鄰的兩個(gè)數(shù),將小數(shù)放在前面，大數(shù)放在后面。

時(shí)間復(fù)雜度：O(N2)。

實(shí)現(xiàn)原理：重復(fù)的走訪要排序的數(shù)列，一次比較兩個(gè)元素，大的元素放后面，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。

代碼實(shí)現(xiàn)：有兩層循環(huán)嵌套，外循環(huán)遍歷數(shù)組的每一項(xiàng)，內(nèi)循環(huán)用于兩兩元素的比較，每次內(nèi)循環(huán)減1。

    function bubbleSort(arr) {
        var length = arr.length;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    [arr[j], arr[j+1]] = [arr[j+1], arr[j]];  
                }
            }
        }
        return arr;
    }

選擇排序（Selection Sort）

時(shí)間復(fù)雜度：O(N2)。

實(shí)現(xiàn)原理：從未排序的序列中找到最小(大)的元素存放到指定的起始位置，再?gòu)奈磁判虻男蛄性刂兄貜?fù)上一步，直至排序完成。

代碼實(shí)現(xiàn)：兩層循環(huán)嵌套，外循環(huán)遍歷數(shù)組的每一項(xiàng)，內(nèi)循環(huán)用于找到樣本里面的最小值或者最大值，每次內(nèi)循環(huán)減1。

    function selectionSort(arr) {
        var length = arr.length;
        var minIndex, temp;
        for (var i = 0; i < length - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
        return arr;
    }

快速排序（Quick Sort）

時(shí)間復(fù)雜度：O(N * log2N)。

實(shí)現(xiàn)原理：通過(guò)遞歸的方式將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列。

代碼實(shí)現(xiàn)：找到一個(gè)數(shù)作為參考，然后比這個(gè)數(shù)字大的放在數(shù)字左邊，比它小的放在右邊，分別再對(duì)左右兩邊的序列做相同的操作。

    function partition(arr, low, high) {
      let pivot = arr[low];
      while (low < high) {
        while (low < high && arr[high] > pivot) {
          --high;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
          ++low;
        }
        arr[high] = arr[low];
      }
      arr[low] = pivot;
      return low;
    }
    function quickSort(arr, low, high) {
      if (low < high) {
        let pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
      }
      return arr;
    }

插入排序（Insertion Sort）

時(shí)間復(fù)雜度：O(N2)。

實(shí)現(xiàn)原理：構(gòu)建一個(gè)有序序列，未排序數(shù)據(jù)在已排序序列中從后向前掃描，找到正確位置插入。

代碼實(shí)現(xiàn)：兩層循環(huán)嵌套，創(chuàng)建已排序數(shù)組, 起始包含數(shù)組的第一個(gè)元素，比這個(gè)數(shù)字大的放在數(shù)字左邊，比它小的放在右邊。

    function insertSort(arr) {
        for(let i = 1; i < arr.length; i++) {
            for(let j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                } else {
                    break;
                }
            }
        }
        return arr;
    }