排序算法

title
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。

排序算法

  • 冒泡算法
  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function bubbleSort(arr) {
    for(let i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j+1]) { //相邻元素两两对比
    var temp = arr[j+1]; //元素交换
    arr[j+1] = arr[j];
    arr[j] = temp;
    }
    }
    }
    return arr;
    }
    console.log(bubbleSort([1,23,4,3]));
  • 快速排序,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function quickSort(arr) {
    if(arr.length <= 1) {
    return arr;
    }
    let leftArr = [];
    let rightArr = [];
    let q = arr[0];
    for(let i = 1; i<arr.length;i++) {
    if(arr[i] > q) {
    rightArr.push(arr[i]);
    } else {
    leftArr.push(arr[i]);
    }
    }
    return [].concat(quickSort(leftArr),[q],quickSort(rightArr));
    }
    console.log(quickSort([1,23,4,3]));