前言:在做leetcode的时候有一道非常简单的排序问题,但是官方给的难度系数是中等,并不是说这道题有多么难做,而是通过这道题可以让我引申到什么,所以我认为这道题是非常有价值的,借此机会总结一下常用的排序算法,希望能给自己带来一些帮助,也能给看到这篇文章的人带来帮助
排序算法可以大致的分为两大类:基于比较的排序算法(冒泡,选择,插入,归并,快速)和不基于比较的排序算法(计数,基数)
基本思想:外层循环每一次经过两两比较,把每一轮未排定部分最大的元素放到了数组的末尾,时间复杂度O(N^2)。
Array.prototype.BubSort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
let flag = true;
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
flag = false;
}
}
if (flag) return arr;
//如果我们通过内部循环完全不交换,这意味着数组已经排序,我们可以在这个点上停止冒泡排序。
}
return arr
}
思路:每一轮选取未排定的部分中最小的部分交换到未排定部分的最开头,经过若干个步骤,就能排定整个数组。
Array.prototype.SelectSort = (arr) => {
for (var i = 0; i < arr.length-1; i++) {
var flag = i
for (var j = i + 1; j < arr.length; j++) {
if (arr[flag] > arr[j]) {
flag = j
}
}
var temp = arr[flag]
arr[flag] = arr[i]
arr[i] = temp
}
return arr
}
每次将一个数字插入一个有序的数组里,成为一个长度更长的有序数组,有限次操作以后,数组整体有序。
Array.prototype.InsSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i];
let j = i;
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
return arr
}
基本思路:借助额外空间,合并两个有序数组,得到更长的有序数组。
算法思想:分治法
Array.prototype.MerSort = (nums) => {
let sort = (left, right) => {
if (left >= right) return;
let mid = parseInt((right + left) / 2)
sort(left, mid);
sort(mid + 1, right);
merge(left, mid, right);
return nums;
}
let merge = (left, mid, right) => {
let arr = [];
let index = 0;
let i = left, j = mid + 1;
while (i <= mid && j <= right) {
arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) arr[index++] = nums[i++];
while (j <= right) arr[index++] = nums[j++];
for (let t = 0; t < index; t++) {
nums[left + t] = arr[t];
}
}
return sort(0, nums.length - 1);
}
基本思路:快速排序每一次都排定一个元素(这个元素呆在了它最终应该呆的位置),然后递归地去排它左边的部分和右边的部分,依次进行下去,直到数组有序;
算法思想:分治法
const QuiSort = (array) => {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
return
}
let i = left
let j = right
const baseVal = arr[j] // 取无序数组最后一个数为基准值
while (i < j) {//把所有比基准值小的数放在左边大的数放在右边
while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
i++
}
arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己(i 等于 j)
while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
j--
}
arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己(i 等于 j)
}
arr[j] = baseVal // 将基准值放至中央位置完成一次循环(这时候 j 等于 i )
sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
}
const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr)
return newArr
}
以数组元素值为键,出现次数为值存进一个临时数组,最后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的,所以计数排序可以用来排列负数,但不可以排列小数。
Array.prototype.CouSort = (arr) => {
var temp = [];
arr.map((item)=>{
temp[item] = ++temp[item] || 1
})
arr = []
temp.map((item , index)=>{
while(item--){
arr.push(index)
}
})
return arr
}
使用十个桶 0-9,把每个数从低位到高位根据位数放到相应的桶里,以此循环最大值的位数次。但只能排列正整数,因为遇到负号和小数点无法进行比较。
Array.prototype.CouSort = (nums) => {
// 计算位数
let getDigits = (n) => {
let sum = 0;
while (n) {
sum++;
n = parseInt(n / 10);
}
return sum;
}
let arr = Array.from(Array(10)).map(() => Array());
let max = Math.max(...nums);
let maxDigits = getDigits(max);
for (let i = 0, len = nums.length; i < len; i++) {
// 用0把每一个数都填充成相同的位数
nums[i] = (nums[i] + '').padStart(maxDigits, 0);
// 先根据个位数把每一个数放到相应的桶里
let temp = nums[i][nums[i].length - 1];
arr[temp].push(nums[i]);
}
// 循环判断每个位数
for (let i = maxDigits - 2; i >= 0; i--) {
// 循环每一个桶
for (let j = 0; j <= 9; j++) {
let temp = arr[j]
let len = temp.length;
// 根据当前的位数i把桶里的数放到相应的桶里
while (len--) {
let str = temp[0];
temp.shift();
arr[str[i]].push(str);
}
}
}
// 修改回原数组
let res = [].concat.apply([], arr);
nums.forEach((val, index) => {
nums[index] = +res[index];
})
return nums
}