javascript中十大排序算法

1、 冒泡排序(Bubble Sort)

实现思路:
对比第一项和第二项
如果第一项大于第二项，交换他们
对比第二项和第三项
如果第二项大于第三项，交换他们
持续直到数据结束

网上找到了一个动图可以形象的说明冒泡排序的原理

冒泡排序

es5的实现

ps:var len = arr.length; // 这样写，可以节省length的获取时间

function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        // 遍历数组的前arr.length - i项，忽略后面的i项（已排序部分）
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

es6语法则简单明了很多了(如果要倒序的话，把>改成<就ok了)

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

2、 选择排序(Selection Sort)

实现思路：
在未排序序列中找到最小的元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小的元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

选择排序

function selectionSort(arr) {
    let len = arr.length;
    let minIndex; // 最小值的索引
    for (let i = 0; i < len; i++) {
        minIndex = i;
        // 此处的j = i + 1是为了避免自己与自己比较
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
    return arr;
}
var arr = [1, 3, 1, 2, 3, 4, 55, 23, 4, 23, 2, -1, -3, 0];
console.log(selectionSort(arr)); //  [-3, -1, 0, 1, 1, 2, 2, 3, 3, 4, 4, 23, 23, 55]

3、 插入排序(insertion Sort)

实现思路：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。

插入排序

function insertionSort(arr) {
    let length = arr.length;
    // i = 1 从第一个元素开始，第一个元素(i为0的)可以认为已经被排序
    for (let i = 1; i < length; i++) {
        let key = arr[i]; // key为准备插入的值
        let j = i - 1; // j为已排序部分的索引，第一次循环时，j就是arr[0]的元素即认为已经被排序的元素
        // 如果当已排序部分的当前元素大于key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 将当前元素（arr[j]）向后移一位
            j = j - 1;
        }
        // 如果已排序部分的当前元素小于key，则直接插入
        arr[j + 1] = key;
    }
    return arr;
};

4、 希尔排序(Shell Sort)

看的有点懵逼，先记下来

实现思路:
希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻元素。通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。

function shellSort(arr) {
    let len = arr.length,
        temp,
        gap = 1;
    while (gap < len / 3) {
        //动态定义间隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        console.log(gap)
        for (let i = gap; i < len; i++) {
            temp = arr[i];
            let j = i - gap;
            for (; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
    return arr;
};

5、 归并排序(Merge Sort)

归并排序

6、 快速排序(Quick Sort)

实现思路:
找到该数组的基准点(通常为数组的第一个值)，并创建两个空数组left和right；
遍历数组，拿出数组中的每个数和基准点进行比较，如果比基准点小就放到left数组中，如果比基准点大就放到right数组中；
对数组left和right进行递归调用。

快速排序

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } else {
        var left = [],
            right = [],
            pivot = arr.shift(); //基准点  shift():该方法用于删除数组的第一个元素，并返回被删除的元素。
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] <= pivot) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return [].concat(quickSort(left), pivot, quickSort(right)) // 把left和right以及基准点拼接成新数组，位置不能乱！！！
    }
}
var arr = [1, 3, 1, 2, 3, 4, 55, 23, 4, 23, 2, -1, -3, 0];
console.log(quickSort(arr)) // [-3, -1, 0, 1, 1, 2, 2, 3, 3, 4, 4, 23, 23, 55]

7、 堆排序(Heap Sort)

8、 计数排序(Counting Sort)

9、 桶排序(Bucket Sort)

10、 基数排序(Radix Sort)

参考资料：
十大经典排序算法总结（JavaScript描述）
算法可视化工具