前端常见的四种JavaScript的排序算法

最近几天总结了一下前端常见的四种JavaScript的排序算法，拿出来给大家分享一下：
这四种排序算法依次是冒泡排序、选择排序、插入排序和快速排序。

冒泡排序

中心思想：

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

算法原理：

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

代码实现：

let temp = 0;
for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) { // 相邻元素作比较,小的放前面大的放后面
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

选择排序

中心思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

算法原理：

1. 比较相邻的元素。如果后面的元素比前面的元素小，则用一个变量key来记住该元素在数组中的索引。
2. 接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量key来记住该元素在数组中的索引，循环结束之后可以找到最小的元素的索引。
3. 然后判断如果这个最小元素的索引不是第一个元素的索引，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的值了。
4. 重复以上步骤就可以接着找出整个数组中第二小的值等。

代码实现：

let temp = 0;
let key = 0; // 用来记录最小值的索引
for (let i = 0; i < arr.length; i++) {
    key = i; // 记录当前索引
    for (let j = i + 1; j < arr.length; j++) {
        if (arr[key] > arr[j]) { // 最小值和后一个值作比较
            key = j; // 把新的最小值记录下来
        }
    }
    temp = arr[key];
    arr[key] = arr[i];
    arr[i] = temp;
}

插入排序

中心思想：

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

算法原理：

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

代码实现：

let iPrev = 0; // 前一个值的索引
let iCurrent = 0; // 当前值
for (let i = 1; i < arr.length; i++) {
    iPrev = i - 1;
    iCurrent = arr[i];
    while (iPrev >= 0 && iCurrent < arr[iPrev]) { // 当前值和前一个值作比较
        arr[iPrev + 1] = arr[iPrev]; // 前一个值大即向后挪一位
        iPrev--; // 继续和前一个值的前一个值作比较, 以此类推...
    }
    arr[iPrev + 1] = iCurrent; // 当前值小即向前挪一位 ==> 相当于和刚才比较的值互换位置
}

快速排序

中心思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法原理：

1. 定义两个变量iLeft、iRight，排序开始的时候：iLeft = 1，iRight = arr.length - 1，这两个小东西在代码中姑且叫它们为'左key'和'右key'，以此来确保数组左边的数都比‘关键数据’小,右边的数都比‘关键数据’大，这个‘关键数据’也就是下文中每次进入循环的新数组的第一项
2. 接着用'右key'从数组的后面依次向前查找，直到找到一个小于等于‘关键数据’的为止。
3. 接着用'左key'从数组的前面依次向后查找，直到找到一个大于等于‘关键数据’的为止。
4. 步骤2和3会得到两个值，将他们的位置进行互换，再继续找。
5. 重复步骤2~4，如果这一过程中'右key'和'左key'都落在了同一个值的身上时，直接将‘关键数据’和他们进行位置互换，再将当前数组以'关键数据'为基准切割成三个新的数组，递归新的数组到最后必然会有多个单项数组，再将这些单项数组拼接成新的数组也就是最终快排的结果。

代码实现：

if (arr.length < 2) {  // 单项数组直接返回
    return arr;
}
// 下边的iLeft和iRight分别表示从数组的两端做检测
let iLeft = 1; // 定义为: '左key'
let iRight = arr.length - 1; // 定义为: '右key'
while (iLeft < iRight) {
    // arr[0] 每次进入循环的新的数组的第一个数作为'关键数据',以此来确保左边的数都比它小,右边的数都比它大,分成三个新的数组
    while (iLeft < iRight && arr[0] <= arr[iRight]) { // 确保'左key'小于'右key'的同时'关键数据'要小于等于'右key'的数据
        iRight--; // '右key'开始向左检测
    }
    while (iLeft < iRight && arr[0] >= arr[iLeft]) { // 确保'左key'小于'右key'的同时'关键数据'要大于等于'左key'的数据
        iLeft++; // '左key'开始向右检测
    }
    if (iLeft == iRight) { // 两个key如果相等直接互换位置
        let temp = null;
        temp = arr[0];
        arr[0] = arr[iRight];
        arr[iRight] = temp;
        break;
    }
    fnToTemp(arr, iLeft, iRight);
}
// 接下来'左key'一旦大于等于'右key', 即把当前数组以'关键数据'为基准切割成三个新的数组
let newArrLeft = arr.slice(0, iLeft);
let newArrCenter = arr.slice(iLeft, iRight + 1);
let newArrRight = arr.slice(iRight + 1);
// 递归每一个数组, 将每一个只包含一个数据的数组拼接成为新的数组也就是我们要的快速排序后的数组
return fnSort(newArrLeft).concat(fnSort(newArrCenter)).concat(fnSort(newArrRight));

以上四种排序算法总结就是这些，想要运行一下代码看看的朋友们可以戳这里，如果以上排序算法还有哪些原理或者代码不懂的可以在评论区指出，本人会第一时间安排Thanks♪(･ω･)ﾉ

希望大家阅读完本文可以有所收获，因为能力有限，掌握的知识也是不够全面，欢迎大家提出来一起分享！谢谢O(∩_∩)O~

欢迎访问我的GitHub，喜欢的可以star，项目随意fork，支持转载但要下标注，同时恭候：个人博客