排序算法
2018-11-16 本文已影响0人
_旁观者_
冒泡
从前向后遍历，如果前面的元素大于后面的，两者互换位置
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
var arr = [2,43,4545,22,4,567,56,76]
function bubble (arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i+1; j < arr.length; j++) {
if(arr[j]< arr[i]) {
let tem = arr[i]
arr[i] = arr[j]
arr[j] = tem
}
}
}
return arr
}
console.log(bubble(arr))
</script>
</body>
</html>
选择排序
从未排序的数组中遍历出最小的元素，和开始位置的元素互换位置
继续从剩下的元素中遍历出做小的，放在已排序的元素后面
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
var arr = [2,43,4545,22,4,567,56,76]
function selectSort (arr) {
let min = 0
for (let i = 0; i < arr.length; i++) {
min = i
for (let j =i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j
}
}
let tem = arr[i]
arr[i] = arr[min]
arr[min] = tem
}
return arr
}
console.log(selectSort(arr))
</script>
</body>
</html>
归并排序
mergeSort用于分割数组，直到分割成单个元素，然后会调用merge
merge作用 排序已经分割的元素
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
// 递归调用mergeSort函数，
// 递归至数组长度为1时，合并leftArr rightArr数组
var arr = [2,43,4545,22,4,567,56,76]
function mergeSort (arr) {
let length = arr.length
if (length < 2) {
return arr
}
let middle = Math.floor(length/2)
let leftArr = arr.slice(0, middle)
let rightArr = arr.slice(middle)
return merge(mergeSort(leftArr), mergeSort(rightArr))
}
function merge (leftArr, rightArr) {
let result = []
while (leftArr.length && rightArr.length) {
if (leftArr[0] <= rightArr[0]) {
result.push(leftArr.shift())
}else {
result.push(rightArr.shift())
}
}
while (leftArr.length) {
result.push(leftArr.shift())
}
while (rightArr.length) {
result.push(rightArr.shift())
}
return result
}
console.log(mergeSort(arr))
</script>
</body>
</html>
插入排序
当前元素current如果小于前一位元素，前一位元素 的索引加1
直到 当前元素current大于正在比较的元素时，跳出while循环
当前元素current位置更改为正在比较的元素
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
var arr = [2,43,4545,22,4,567,56,76]
function insert (arr) {
let current, preIndex
for (let i = 1; i < arr.length; i++) {
current = arr[i]
preIndex = i - 1
// 首先缓存当前的current 和 index，在while循环中会发生变化
// 循环直到当前的数组元素大于current时候停止，再赋值与index+1位的元素
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex]
preIndex--
}
arr[preIndex + 1] = current
}
return arr
}
console.log(insert(arr))
</script>
</body>
</html>
希尔排序
选择一个增量序列，按增量序列对序列进行排序
每趟排序的方法为插入排序，根据对应的增量 ，分为多次排序
直到趟数为1时，完成排序
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
// 参考资料 https://blog.csdn.net/weixin_37818081/article/details/79202115
// 希尔排序 (多个小的组别插入排序逐渐归为一个组别的插入方法)
var arr = [22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
// for 循环 顺序 1,gap ==> 2,gap > 0 ==> 3,console.log('for1', gap) ==> 4,gap = Math.floor(gap/3) ==> 2,gap > 0
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) { // 插入排序
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
console.log(shellSort(arr))
</script>
</body>
</html>
