乱序的意思就是将数组打乱，需要注意的是保证每个位置出现的可能性平均。排序就是将数组升序或降序，需要考虑算法复杂度。在这里我们从一个乱序不彻底的现象来引入各个排序算法。
乱序
乱序不彻底的原因分析和乱序彻底策略。
Math.random
一个经常会遇见的写法是使用 Math.random()：
var values = [1, 2, 3, 4, 5];
values.sort(function(){
return Math.random() - 0.5;
});
上述代码的一个问题就是乱序的不彻底，不信写一个简单的例子进行统计：
var times = [0, 0, 0, 0, 0];
for (var i = 0; i < 100000; i++) {
let arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);
times[arr[4]-1]++;
}
console.log(times)
测试原理是：将 [1, 2, 3, 4, 5] 乱序 10 万次，计算乱序后的数组的最后一个元素是 1、2、3、4、5 的次数分别是多少？你会发现差别不是一点大。
Array.sort
针对 sort 函数的原理，然而 ECMAScript 只规定了效果，没有规定实现的方式，所以不同浏览器实现的方式还不一样。
以 v8 为例，v8 在处理 sort 方法时，当目标数组长度小于 10 时，使用插入排序；反之，使用快速排序和插入排序的混合排序。因此v8引擎的sort排序是插入排序和快速排序的结合。
为什么v8要如此选择呢，主要是因为当数组是快要排序好的状态或者问题规模比较小的时候，插入排序效率更高。这也是为什么 v8 会在数组长度小于等于 10 的时候采用插入排序。
API
语法：arrayObject.sort(sortby)；参数sortby可选，用于规定排序规则，必须是函数。
如果调用该方法时没有使用参数，将按字母顺序对数组中的元素进行排序(按照
字符编码的顺序)
如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：
- a < b，排序后的数组中 a 在 b 前，返回一个小于 0 的值
- a == b，返回 0
- a > b，返回一个大于 0 的值
比较函数不提供两个参数也是可以的，原理是一样的，如果是正数则降序排列，如果是负数则升序排列，如果是 0 就不变
具体分析
为什么乱序不测试呢？使用上面的例子统计，你大概会发现概率分布总体不会变，更加详细分布比例如下：
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = [1, 2, 3];
arr.sort(() => Math.random() - 0.5);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 为了方便展示，转换成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)
根本原因在于：其实就在于在插入排序的算法中，当待排序元素跟有序元素进行比较时，一旦确定了位置，就不会再跟位置前面的有序元素进行比较，所以就乱序的不彻底。
Fisher–Yates
话不多说，我们直接看 JavaScript 的实现，代码其实很简单：
function shuffle(a) {
var j, x, i;
for (i = a.length; i; i--) {
j = Math.floor(Math.random() * i);
x = a[i - 1];
a[i - 1] = a[j];
a[j] = x;
}
return a;
}
原理很简单，就是遍历数组元素，然后将当前元素与以后随机位置的元素进行交换，从代码中也可以看出，这样乱序的就会更加彻底。
名词解释
在介绍更多算法之前，我们了解一些名词解释，比如稳定性、内外排序、复杂度、place。
稳定性
- 稳定性是指相同的元素在排序后是否还保持相对的位置。
- 要注意的是对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。比如 [3, 3, 1]，排序后，还是 [3, 3, 1]，但是其实是第二个 3 在 第一个 3 前，那这就是不稳定的排序算法。
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内外排序
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
复杂度
- 时间复杂度: 一个算法执行所耗费的时间，时间复杂度是指执行算法所需要的计算工作量，它考察当输入值大小趋近无穷时的情况，一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数。
- 空间复杂度: 运行完一个程序所需内存的大小。
place
- In-place: 占用常数内存，不占用额外内存
- Out-place: 占用额外内存
插入排序
插入排序原理在于将第一个元素视为有序序列，遍历数组，将之后的元素依次插入这个构建的有序序列中。
插入排序中：
- 最好情况：数组升序排列，时间复杂度为：O(n)
- 最坏情况：数组降序排列，时间复杂度为：O(n²)
插入排序是稳定的算法。
源码如下：
function insertSort(arr) {
// 原数组，从1开始，默认0号位是已排序，j依赖于i，从而将一个数组一分为二动态遍历
for (var i = 1; i < arr.length; i++) {
var element = arr[i];
// 已排序
for (var j = i - 1; j >= 0; j--) {
var tmp = arr[j];
var order = comparefn(tmp, element);
// 寻找element元素合适的插入位置，不满足比较规则，则一排序数组位后移，知道位置合适在插入element元素
if (order > 0) {
arr[j + 1] = tmp;
} else {
break;
}
}
arr[j + 1] = element;
}
}
// 升序
function comparefn(a, b) {
return a - b;
}
插入排序优化：插入排序的原理是从乱数组中选择元素插入已排序数组中，因此针对已排序数组选择插入位置的查找过程可以使用二分法。
二分法元素查找：
function binarySearch(items, value) {
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex) / 2);
while (items[middle] != value && startIndex < stopIndex) {
if (value < items[middle]) {
stopIndex = middle - 1;
} else if (value > items[middle]) {
startIndex = middle + 1;
}
middle = Math.floor((stopIndex + startIndex) / 2);
}
return (items[middle] != value) ? -1 : middle;
}
我们的需求需要对二分法进行修改，得到的下标应该是我们元素的插入位置，修改如下：
function binarySearch(arr, target) {
var left = 0;
var right = arr.length - 1;
while (left <= right) {
var middle = parseInt((left + right) / 2);
if (target < arr[middle]) {
// 说明在左半区
right = middle - 1;
} else {
left = middle + 1;
}
}
return left;
}
有两个细节必须注意：
- 退出循环的条件必须是left<=right，而不能是left<right，后者会导致有元素没有比较到
- 返回left还是right，取决于你相等的值放在哪个区间，因此返回left，而且left是插入的位置下标
二分法优化过后的插入排序：
function binaryInsertionSort(arr) {
// 原数组，从1开始，默认0号位是已排序
for (var i = 1; i < arr.length; i++) {
var element = arr[i],
left = 0,
right = i - 1;
// 对于已排序数组，可以使用二分查找
while (left <= right) {
var middle = parseInt((left + right) / 2);
if (element < arr[middle]) {
// 说明在左半区
right = middle - 1;
} else {
left = middle + 1;
}
}
// 实现插入
for (var j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j]
}
arr[left] = element;
return arr;
}
}
快速排序
原理
- 选择一个元素作为"基准"，一般去中间元素，比较好理解
- 小于"基准"的元素，都移到"基准"的左边；大于"基准"的元素，都移到"基准"的右边。
- 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
实现
简单版，这种方式需要额外使用空间来存储左右子集
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
// 取数组的中间元素作为基准
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr[pivotIndex];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
原地(in-place)排序思路与源码：
- 默认第一个元素为基准值，用剩余的值和基准值进行比较
- 基准值
右边元素构成一个左边数组，用storeIndex记录此时左边数组的最后一个元素下标 - 此处应该有一个比较函数，在这里使用升序的方式，因此小于时将目标元素放入
左边数组操作就是与左边数组的后一个元素交换 - 将基准值和左边数组最后一个元素交换，实现左右数组结构
经过分区之后，便有了左右数组，然后递归调用，出口就是left>=right时
function quickSort(arr) { // 交换元素 function swap(arr, a, b) { var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } function partition(arr, left, right) { var pivot = arr[left]; var storeIndex = left; for (var i = left + 1; i <= right; i++) { if (arr[i] < pivot) { swap(arr, ++storeIndex, i); } } swap(arr, left, storeIndex); return storeIndex; } function sort(arr, left, right) { if (left < right) { var storeIndex = partition(arr, left, right); sort(arr, left, storeIndex - 1); sort(arr, storeIndex + 1, right); } } sort(arr, 0, arr.length - 1); return arr; }
稳定性与复杂度
快速排序是不稳定的排序。就以数组 [1, 2, 3, 3, 4, 5] 为例，因为基准的选择不确定，假如选定了第三个元素(也就是第一个 3) 为基准，所有小于 3 的元素在前面，大于等于 3 的在后面，排序的结果没有问题。可是如果选择了第四个元素(也就是第二个 3 )，小于 3 的在基准前面，大于等于 3 的在基准后面，第一个 3 就会被移动到 第二个 3 后面，所以快速排序是不稳定的排序。
原地排序中基准取最左边的元素。快速排序的关键点就在于基准的选择，选取不同的基准时，会有不同性能表现。
在最佳情况下，每一次都平分整个数组。假设数组有 n 个元素，其递归的深度就为 log2n + 1，时间复杂度为 O(n)[(log2n + 1)]，因为时间复杂度考察当输入值大小趋近无穷时的情况，所以会忽略低阶项，时间复杂度为：o(nlog2n)。
而在最差情况下，如果对一个已经排序好的数组，每次选择基准元素时总是选择第一个元素或者最后一个元素，那么每次都会有一个子集是空的，递归的层数将达到 n，最后导致算法的时间复杂度退化为 O(n²)。
如果一个程序的运行时间是对数级的，则随着 n 的增大程序会渐渐慢下来。如果底数是 10，lg1000 等于 3，如果 n 为 1000000，lgn 等于 6，仅为之前的两倍。如果底数为 2，log21000 的值约为 10，log21000000 的值约为 19，约为之前的两倍。我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。所以我们认为 O(logn)已经可以表达所有底数的对数了，所以时间复杂度最后为： O(nlogn)。
这也充分说明了一个基准的选择是多么的重要，而 v8 为了提高性能，就对基准的选择做了很多优化。
V8基准选择与源码
这个日后有时间再磕！在资料2中！
冒泡排序
这应该是大多数学习编码时，最熟悉的排序算法了吧，当然对于我也不例外，那时候觉得这也是最好理解的一个啦。
算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
算法分析：
- 最佳情况：T(n) = O(n)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
简单版：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
// 外层循环每循环一次，就完成一个元素的冒泡，因此减去i，同时元素比较会和后一个元素比较，因此再减去1
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
优化思路1：置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
function bubbleSort2(arr) {
var i = arr.length - 1;
while (i > 0) {
var pos = 0;
for (var j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
pos = j;
}
}
i = pos;
}
return arr;
}
优化思路2：双向冒泡
function bubbleSort3(arr) {
var low = 0;
var high = arr.length - 1;
var tmp, j;
while (low < high) {
//正向冒泡,找到最大者
for (j = low; j < high; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
high--;
//反向冒泡,找到最小者
for (j = high; j >low; j--) {
if (arr[j] < arr[j - 1]) {
var temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
low++;
}
return arr;
}
选择排序
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。也是最为简单的排序的吧。
工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码实现：
function selectSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
// 直接找出最小值，与有序数组后一位元素交换，可以借住外层循环i分区，因为外层循环每循环一次，有序+1，无序-1，i用来分区在合适不过
for (var j = i + 1; j < len; j++) {
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}