数组常用的几种排序方式

冒泡排序

冒泡拍排序：俩俩捉对比较，大或小就换位置，一直比下去，最大或者最小的放最后

最后的结果是从小到大（从1开始排列）

注意：如果要从大到小排列的话，就把compare方法中的a>b的判断改为a https://blog.csdn.net/weixin_49950087/article/details/122088742

选择排序

选择排序：
在数组中先找出最小数的索引，设一个变量保存下来，找到就进行交换
最小的数和数组的第一个数进行交换，
以此类推，再把数组其他数字最小数的索引找出，再和数组的第二位数进行交换。

举例：
例：5,4,7,2,9,1,6

第一趟排序 ：1,4,7,2,9,5,6

第二趟排序： 1,2,7,4,9,5,6

第三趟排序: 1,2,4,7,9,5,6

第四趟排序： 1,2,4,5,9,7,6
…….

首先在未排序序列中找到最大（小）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

不稳定的排序算法

不稳定的排序算法主要有以下四种：1、选择排序；2、快速排序；3、希尔排序(shell)；4、堆排序

稳定的排序算法

稳定的排序算法有以下4种：1、冒泡排序；2、插入排序；3、归并排序 ；4、基数排序。

排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。

注意：
排序算法稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
https://baike.baidu.com/item/排序算法稳定性/9763250

exchange用于选择排序：
maxIndex始终为0，也就是第一个，arr.lengrh-1为最后一个，arr.length-1-i为最后的数字-当前循环的第几个（倒数第二，倒数第三等等一直到0第一个）

快速排序

js的sort（）配合自己的写法：
https://blog.csdn.net/qq_34595425/article/details/122851284

js中⽤⽅法sort()为数组排序。sort()⽅法有⼀个可选参数，是⽤来确定元素顺序的函数。如果这个参数被省略，那么数组中的元素将按照ASCII字符顺序进⾏排序

注意：使用sort（）需要自己写一个确认顺序的函数，作为参数使用

数组对象进⾏排序
sort⽅法接收⼀个函数作为参数，这⾥嵌套⼀层函数⽤来接收对象属性名，其他部分代码与正常使⽤sort⽅法相同.

递归排序（快速排序）

1.从数列中取出一个数作为参考,分区过程。
2.将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3.对左右区间重复第二步，直到各区间只有一个数。
简易的快速排序（不使用sort（））

.concat（）是两个数组连接的方法
在concat拼接前，left和right为什么要再递归一次quickSort？
最后输出 是重点
注意：因为不递归，最后输出的 左边 和 右边的数字 排序可能并不一定会是从小到大，所以要递归quickSort

因为每次递归都会把 左和右合并后的数组 的第一个拿来做leader，每次都会出现一个新的左和右数组，并且数组的长度会比之前少一个（因为第一个被拿去做为leader）

直到递归到最后数组中只剩一个值，这个值被拿去做leader，左右数组中值一个不剩，导致左右合并后的数组为空，跳出递归

这样其实也是把所有的值都和leader对比了一遍（其实和leader对比后，分为两块后，，再合成一个新数组，返回，循环往复操作）

递归的操作其实就是分为两块后，再次一一对比了一遍

但这种写法 性能较差

二分法插入排序

算法
二分法排序一般指本词条
二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left

算法思想简单描述：
二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。

复杂度分析
二分插入排序是稳定的与二分查找的复杂度相同；[1]
最好的情况是当插入的位置刚好是二分位置 所用时间为O(log2n);
最坏的情况是当插入的位置不在二分位置 所需比较次

插入排序

两个循环，内部循环，一个一个插入，只要上一个比大或者小就立即插入

插入排序，一旦你遇到比自己大或小的了，你就知道，后面都是比自己大或小的，就没必要再继续往前走了，现在坐下，当前元素就进入了有序序列

插入的每一次插，都不一定要轮一遍有序序列

function insertionSort(arr) {
    //外层循环：拿到标记的元素
    for (let i = 0; i < arr.length; i++) {
        let temp = arr[i];
        //内层循环：从后往前比较元素的大小
        let j = i;
        while (arr[j - 1] > arr[j] && j > 0) {
            arr[j] = arr[j - 1];
            j--;
        }
        //最后便将其插入进去即可
        arr[j] = temp;
    }
    return arr;
}

//测试一下
console.log(insertionSort([1, 3, 2, 6, 4, 5]));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18