JavaScript排序算法

1：基本概念

时间复杂度：算法执行所耗费的时间。

这个复杂度直接和样本的个数有关，复杂度反映了算法的性能，一般来说，复杂度越低，算法所消耗的时间越短。

    /* 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++) {
            ...
        }
    }

空间复杂度：运行一个程序所需内存的大小。

空间复杂度和时间复杂度是对立的，比如说，时间复杂度越高，空间复杂度越低；反之则相反。

内排序：所有排序操作都在内存中完成。

2：常用的排序算法

冒泡排序（Bubble Sort）

基本概念：依次比较相邻的两个数,将小数放在前面，大数放在后面。

时间复杂度：O(N2)。

实现原理：重复的走访要排序的数列，一次比较两个元素，大的元素放后面，如果它们的顺序错误就把它们交换过来。

代码实现：有两层循环嵌套，外循环遍历数组的每一项，内循环用于两两元素的比较，每次内循环减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）

时间复杂度：O(N2)。

实现原理：从未排序的序列中找到最小(大)的元素存放到指定的起始位置，再从未排序的序列元素中重复上一步，直至排序完成。

代码实现：两层循环嵌套，外循环遍历数组的每一项，内循环用于找到样本里面的最小值或者最大值，每次内循环减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）

时间复杂度：O(N * log2N)。

实现原理：通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。

代码实现：找到一个数作为参考，然后比这个数字大的放在数字左边，比它小的放在右边，分别再对左右两边的序列做相同的操作。

    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）

时间复杂度：O(N2)。

实现原理：构建一个有序序列，未排序数据在已排序序列中从后向前扫描，找到正确位置插入。

代码实现：两层循环嵌套，创建已排序数组, 起始包含数组的第一个元素，比这个数字大的放在数字左边， 比它小的放在右边。

    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;
    }