冒泡排序
基本思想就是逐个比较
JS:
bubleSort(arr) {
var len = arr.length
for (let outer = len; outer >= 2; outer--) {
for (let inner = 0; inner <= outer - 1; inner++) {
if (arr[inner] > arr[inner + 1]) {
;[arr[inner], arr[inner + 1]] = [arr[inner + 1], arr[inner]]
}
}
}
return arr
},
使用：
const arr = [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
console.log('bubleSort', this.bubleSort(arr))
// bubleSort (10) [1, 1, 2, 11, 12, 32, 126, 321, 477, 565]
选择排序
选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后
JS:
selectSort(arr) {
var len = arr.length
for (let i = 0; i < len - 1; i++) {
for (let j = i; j < len; j++) {
if (arr[j] < arr[i]) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
}
return arr
},
使用：
const arr = [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
console.log('selectSort', this.selectSort(arr))
// selectSort(10) [1, 1, 2, 11, 12, 32, 126, 321, 477, 565]
插入排序
就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，继续接，可能是中间数，就插在中间....依次
- 首先将待排序的第一个记录作为一个有序段
- 从第二个开始，到最后一个，依次和前面的有序段进行比较，确定插入位置
JS:
function insertSort(arr) {
for(let i = 1; i < arr.length; i++) { //外循环从1开始，默认arr[0]是有序段
for(let j = i; j > 0; j--) { //j = i,将arr[j]依次插入有序段中
if(arr[j] < arr[j-1]) {
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
} else {
break;
}
}
}
return arr;
}
使用：
const aaa = [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
console.log('insertSort', this.insertSort(aaa))
// // insertSort(10) [1, 1, 2, 11, 12, 32, 126, 321, 477, 565]
时间复杂度
时间复杂度
如果所有排序都像上面的基本方法一样，那么对于大量数据的处理，将是灾难性的，只是排个序，都用了O(n²)。 好吧，所以接下来这些高级排序算法，在大数据上，可以大大的减少复杂度。
快速排序
快排是处理大数据最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直至所有数据都是有序的。
简单说： 找到一个数作为参考，比这个数字大的放在数字左边，比它小的放在右边； 然后分别再对左边和右变的序列做相同的操作:
- 选择一个基准元素，将列表分割成两个子序列；
- 对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值的后面；
- 分别对较小元素的子序列和较大元素的子序列重复步骤1和2
JS:
quickSort(arr) {
if (arr.length <= 1) {
return arr
}
const left = []
const right = []
const current = arr.splice(0, 1)
for (let i = 0; i < arr.length; i++) {
if (arr[i] < current) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return this.quickSort(left).concat(current, this.quickSort(right))
},
使用的方法：
const aaa = [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
console.log('quickSort', this.quickSort(aaa))
// quickSort (10) [1, 1, 2, 11, 12, 32, 126, 321, 477, 565]
希尔排序
希尔排序是插入排序的改良算法，但是核心理念与插入算法又不同，它会先比较距离较远的元素，而非相邻的元素
三层循环的内两层完全就是一个插入排序，只不过原来插入排序间隔为1，而希尔排序的间隔是变换的n， 如果把n修改为1，就会发现是完全一样的了
JS:
shellSort(arr) {
console.log(arr)
const gap = [3, 2, 1]
for (let i = 0; i < gap.length; i++) {
let n = gap[i]
for (let j = i + n; j < arr.length; j++) {
for (let k = j; k > 0; k -= n) {
if (arr[k] < arr[k - n]) {
;[arr[k], arr[k - n]] = [arr[k - n], arr[k]]
console.log(
`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k - n]}`
)
} else {
continue
}
}
}
}
return arr
},
// (10) [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
// 当前序列为[11,565,126,12,1,2,477,32,1,321] 交换了12和11
// 当前序列为[11,1,126,12,565,2,477,32,1,321] 交换了565和1
// 当前序列为[11,1,2,12,565,126,477,32,1,321] 交换了126和2
// 当前序列为[11,1,2,12,32,126,477,565,1,321] 交换了565和32
// 当前序列为[11,1,2,12,32,1,477,565,126,321] 交换了126和1
// 当前序列为[11,1,1,12,32,2,477,565,126,321] 交换了2和1
// 当前序列为[11,1,1,12,32,2,321,565,126,477] 交换了477和321
// 当前序列为[1,1,11,12,32,2,321,565,126,477] 交换了11和1
// 当前序列为[1,1,11,2,32,12,321,565,126,477] 交换了12和2
// 当前序列为[1,1,11,2,32,12,126,565,321,477] 交换了321和126
// 当前序列为[1,1,11,2,32,12,126,477,321,565] 交换了565和477
// 当前序列为[1,1,2,11,32,12,126,477,321,565] 交换了11和2
// 当前序列为[1,1,2,11,12,32,126,477,321,565] 交换了32和12
// 当前序列为[1,1,2,11,12,32,126,321,477,565] 交换了477和321
使用：
const arr = [12, 565, 126, 11, 1, 2, 477, 32, 1, 321]
console.log('shellSort', this.shellSort(arr))
// shellSort(10) [1, 1, 2, 11, 12, 32, 126, 321, 477, 565]
