十种排序算法
1.冒泡
时间复杂度 n*n， 并且大量移动, 最慢，不过稳定
function sort(arr){
let len = arr.length
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
// console.log(i + '===' + j);
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
var arr = []
for (let i = 0; i < 100000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 14505 ms （这个是十万级，百万级卡死了）
2.选择
function sort(arr){
let minIndex;
let len = arr.length
for (let i = 0; i < len; i++) {
minIndex = i
for (let j = i+1; j < len; j++) {
if(arr[minIndex] > arr[j]){
minIndex = j
}
}
if(minIndex != i){
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 100000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 2957 ms （这个是十万级，百万级卡死了）
3.插入
function sort(arr){
for (let i = 1; i < arr.length; i++) {
let curValue = arr[i]
let j = i
while(j > 0 && arr[j-1] > curValue){
arr[j] = arr[j-1]
j--
}
arr[j] = curValue
}
return arr
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 100000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 1739 ms （这个是十万级，百万级卡死了）
4.希尔
// 希尔 增量-插入
function sort(arr){
let len = arr.length
let gap = Math.floor(len/2)
while(gap > 0){
for (let i = gap; i < len; i++) {
let curValue = arr[i]
let j = i
while(j > 0 && arr[j-gap] > curValue){
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = curValue
}
gap = Math.floor(gap/2)
}
return arr
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 450 ms
5.归并
递归 + 合并有序数组
// 归并
function sort(arr){
if(arr.length < 2){
return arr
}
let mid = Math.floor(arr.length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid)
return merge(sort(left), sort(right))
}
function merge(left, right){
let i = 0, j = 0
let result = []
while(i < left.length && j < right.length){
if(left[i] < right[j]){
result.push(left[i++])
} else {
result.push(right[j++])
}
}
return result.concat(left.slice(i)).concat(right.slice(j))
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 350 ms
6.快排
- push简单版
// 快排, push简单版，三路快排，中间位置数，左 中 右
function sort(arr){
if(arr.length < 2){
return arr
}
let midIndex = Math.floor(arr.length / 2)
let mid = arr.splice(midIndex, 1)[0]
let left = []
let right = []
for (let i = 0; i < arr.length; i++) {
if(arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return sort(left).concat(mid).concat(sort(right))
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort_push")
sort(arr)
console.timeEnd("sort_push") // 2354 ms
- 快排 move版
// 快排 move版（内存和速度更优先）
function sort(arr, left=0, right=arr.length){
if (left < right) {
let pivotIndex = move(arr, left, right);
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex + 1, right);
}
return arr;
}
function move(arr, leftIndex, rightIndex){
let midValue = arr[Math.floor((leftIndex + rightIndex) / 2)]
let i =leftIndex
let j = rightIndex
while (i <= j) {
while (arr[i] < midValue) {
i++
}
while (arr[j] > midValue) {
j--
}
if(i<=j){
[arr[i],arr[j]] = [arr[j], arr[i]]
i++;
j--;
}
}
return i;
}
// var arr = [3,3,4,3,5,2,6,8,8,7,1,9,4]
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort_move")
sort(arr)
console.timeEnd("sort_move") // 115 ms
7.堆排序
完全二叉树，优先队列，数组存储，
大堆，父节点大于子节点，
8.桶排序
function sort(arr, size=1){
let max = arr[0]
let min = arr[0]
for (let i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max)
min = Math.min(arr[i], min)
}
let tmp = new Array(max - min + 1).fill(0).map(() => [])
for (let i = 0; i < arr.length; i++) {
tmp[arr[i] - min].push(arr[i])
}
// 桶大小1时，里面不用再排序了
return tmp.flat()
}
// let arr = [65,76,66,65,71,66,74,71,69,68,71,72,74,64];
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 30ms
9.计数排序
● 每个数字, 累加次数，
● 取次数-- = i+min
// 计数排序- 重复数字较多
function sort(arr){
let max = arr[0]
let min = arr[0]
for (let i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max)
min = Math.min(arr[i], min)
}
let tmp = new Array(max - min + 1).fill(0)
for (let i = 0; i < arr.length; i++) {
tmp[arr[i] - min] += 1 // 计数
}
// console.log(tmp);
let result = []
for (let i = 0; i < tmp.length; i++) {
let j = tmp[i]
while (j-- > 0) {
result.push(i+min)
}
}
// console.log(result);
}
// let arr = [65,76,66,65,71,66,74,71,69,68,71,72,74,64];
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 14 ms
10.基数排序
● 最大数位数
● 10桶，个位分桶有序 > 十位分桶有序 > .. 最大位有序
// 基数排序 手机号
function sort(arr){
let max = arr[0]
for (let i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max)
}
maxLen = max.toString().length // 最大数位数，决定几次分桶
for (let i = 0; i < maxLen; i++) {
// 桶
let tmp = new Array(10).fill(0).map(() => []) // 0-9
for (let j = 0; j < arr.length; j++) {
let v = Math.floor(arr[j] / Math.pow(10, i)) % 10
tmp[v].push(arr[j])
}
// console.log(tmp)
arr = tmp.flat()
// console.log(arr);
}
return arr
}
// let arr = [32, 645, 3, 230, 40, 99, 3, 999, 9, 0, 66, 48, 273, 69, 63];
let arr = []
for (let i = 0; i < 1000000; i++) {
arr.push(Math.floor(Math.random()*1000))
}
console.time("sort")
sort(arr)
console.timeEnd("sort") // 90ms
let arr1 = [32, 645, 3, 230, 40, 99, 3, 999, 9, 0, 66, 48, 273, 69, 63];
sort(arr1);
// 按位，排序过程
// [230, 40, 0, 32, 3, 3, 273, 63, 645, 66, 48, 99, 999, 9, 69]
// [0, 3, 3, 9, 230, 32, 40, 645, 48, 63, 66, 69, 273, 99, 999]
// [0, 3, 3, 9, 32, 40, 48, 63, 66, 69, 99, 230, 273, 645, 999]