排序
常见的排序算法
将常见的几种排序手写了一边，一些心得和理解写在了代码的注释中,其中桶排序、计数排序、堆排序未写代码，写了一些自己的理解。
本文参考：
1、排序图解：js排序算法实现
2、五分钟学会一个高难度算法：希尔排序
3、排序算法（九）：桶排序
4、堆排序及其分析
let unSortArr = [17, 25, 3, 14, 20, 9];
let unSortArr2 = [1, 2, 3, 4, 5, 6];
//冒泡
function Bubble(preArr) {
let temp,
arr = preArr.slice(0);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
//冒泡改进，对于上次没有交换任何元素时(说明已经有序)，可不进行接下来的遍历，减少运行次数
function Bubble2(preArr) {
let temp,
arr = preArr.slice(0),
exchangeFlag = true;
for (let i = 0; i < arr.length; i++) {
exchangeFlag = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
exchangeFlag = true;
}
}
if (!exchangeFlag) break;
}
return arr;
}
// 插入排序 从下标1开始每增1项排序一次，越往后遍历次数越多
function insert(arr) {
let res = arr.slice(0),
j,
temp;
for (let i = 1; i < res.length; i++) {
j = i - 1;
//此处的j+1不应该写为i,因为每次的对比是相邻的两个对比，是变动的，纵观这几种排序，外部循环的值一般只参与控制和判断，不会深入到内部的循环中
while (j >= 0 && res[j + 1] < res[j]) {
temp = res[j];
res[j] = res[j + 1];
res[j + 1] = temp;
j--;
}
}
return res;
}
//改进插入排序，每次的交换稍显多余，可先用前一个数值覆盖，最后将需要插入的值赋到合适的地方
function insert2(array) {
var len = array.length,
i,
j,
tmp,
result;
result = array.slice(0);
for (i = 1; i < len; i++) {
tmp = result[i];
j = i - 1;
while (j >= 0 && tmp < result[j]) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = tmp;
}
return result;
}
//改进插入排序，可优化的点在于可利用二分法查找应该插入的位置，减少遍历的时间
function insert3(array) {
var len = array.length,
i,
j,
tmp,
low,
high,
mid,
result;
// 赋予数组副本
result = array.slice(0);
for (i = 1; i < len; i++) {
tmp = result[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = parseInt((low + high) / 2, 10);
if (tmp < result[mid]) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) {
result[j + 1] = result[j];
}
result[j + 1] = tmp;
}
return result;
}
//选择排序，其实在写插入排序改进版的时候就有这样的念头，这种交换效率的问题，因为冒泡的交换所持有的待比较的数并不确定
//不能像改进的插入排序那样，最后再选择插入位置。选择排序的核心有点像冒泡，一轮下来，将最大或者最小的放置在边缘
//（遍历时，保存当时的最大或者最小的序号）遍历结束后再进行交换
function selection(array) {
let k,
temp,
res = array.slice(0);
for (let i = 0; i < res.length; i++) {
k = i;
for (let j = i + 1; j < res.length; j++) {
if (res[j] < res[k]) k = j; //保存当前最大的序号
}
if (k !== i) {
//序号不一致则交换
temp = res[i];
res[i] = res[k];
res[k] = temp;
}
}
return res;
}
//快排：选取合适的中间数，比其小的放一侧，大的放另一侧，再迭代
function quick(arr) {
if (arr.length <= 1) return arr;
let mid,
left = [],
right = [];
mid = arr.splice(Math.floor(arr.length / 2), 1);
for (let i = 0; i < arr.length; i++) {
if (arr[i] < mid) left.push(arr[i]);
else right.push(arr[i]);
}
return quick(left).concat(mid, quick(right));
}
//希尔排序：选取不同的增量进行多次插入排序
//对于增量的选取，只要最后增量为1即可，回想希尔排序的实质，就是利用插入排序对有序序列效率高（运行次数小）这一点
//进行改进，让其在增量为1（插入排序增量一直为1）时，尽可能的有序，来减少遍历判断移动的次数
function shell(arr) {
let i,
j,
temp,
len = arr.length,
gap,
res = arr.slice(0);
gap = parseInt(len / 2);
while (gap > 0) {
for (i = gap; i < len; i++) {
temp = res[i];
j = i - gap;
while (j >= 0 && temp < res[j]) {
res[j + gap] = res[j];
j = j - gap;
}
res[j + gap] = temp;
}
gap = parseInt(gap / 2);
}
return res;
}
//归并排序，对无序数组拆分成若干个小数组（最小数组长度为1）进行排序，再把一个一个小数组合并，合并的时候根据大小顺序合并
function merge(arr) {
function Sort(_arr) {
if (_arr.length == 1) return _arr;
let len = _arr.length,
mid = parseInt(len / 2),
left = _arr.slice(0, mid),
right = _arr.slice(mid, len);
return mergeArr(Sort(left), Sort(right));
}
function mergeArr(left, right) {
let res = [];
while (left.length || right.length) {
//left和right肯定是已经排好序的，且left和right的长度最多相差1（sort函数中切分数组取的是中间mid），故分下三种情况
if (left.length && right.length) {
if (left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
} else if (left.length) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
return res;
}
return Sort(arr);
}
console.log(merge(unSortArr));
- 对于堆排序，主要是利用大根堆这个数据结构（最大元素在堆顶），主要步骤为：
1、调整二叉树，形成大根堆（一种完全二叉树）
2、交换堆顶元素跟最后元素位置，最后元素弹出堆。然后继续回到1，调整堆，
3、重复1、2步骤，直至所有元素出堆，得到的就是有序的序列。 - 计数排序：根据取值的值域开辟连续的空间，遍历无需序列，依次累加相应的值次数，最后按值域大小依次输出，典型例子：统计分数（开辟分数值域数组，记录每个分数的学生个数，再按分数的高低输出）
- 对于桶排序，其实是一种计数排序的优化，弱化了计数排序中空间的浪费，通俗些说，增大了桶，减少了桶的数量，即最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况，之后每个桶再进行排序，排序的算法可以是之前的任何一种，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。
不同算法的时间空间复杂度分析
参考链接八大排序算法时间和空间复杂度
查看1道真题和解析