排序算法

发表于 | 分类于 | | 阅读次数:
字数统计: 456 | 阅读时长 ≈ 1

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]));