<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<h3>数组排序</h3>
<script>
// 冒泡排序法
// 两两比较 每次比较可以把一个数字按照排序排好
// 每次比较后 下一次的可以减少一个元素的比较
// 第一次比较 有0个元素不比
// 第二次比较 有1个元素不比
// 第三次比较 有2个元素不比
// 总共需要比 数组长度-1次
var arrs = [4,9,5,23,1,90,76,54,34,59,89,78,86];
var news;
for (var i = 0;i < arrs.length - 1;i ++) {
for (var j = 0; j < arrs.length - i - 1; j ++) {
if (arrs[j] < arrs[j + 1]) {
news = arrs[j];
arrs[j] = arrs[j + 1];
arrs[j + 1] = news
}
}
}
// console.log(arrs);
//上面是 已经可以完成冒泡排序了 但是会有无端的循环
//比如 如果我们排序的数组是 【5,4,3,1,2】 如果是从大到小
//其实我们只需要一次循环就好了 但是上面的方法 仍然会有4次循环
//所以我们可以考虑加一个是否有交换的标识位 如果没有交换 结束排序
var temp;
for (var i = 0; i < arrs.length - 1; i++) {
var flag = 1;
for (var j = 0;j < arrs.length - i - 1; j ++) {
if (arrs[j] < arrs[j + 1]) {
temp = arrs[j + 1];
arrs[j + 1] = arrs[j];
arrs[j] = temp;
flag = 0;
}
}
if (flag === 1) { //如果没有元素交换 则已经有序
break;
}
}
//选择排序
//原理:每一次从待排数组中选出最小或者最大的一个元素 存放在序列的起始位置
//然后在从剩余未排序的元素中找出最大或者最小的元素 放到已排数据序列的末尾 直到排完
//选择排序比冒泡排序要少交换一些 但是时间复杂度都是O(n2) 较少时选择选择排序
var sortArr = [4,567,89,56,565,677,8,90,34];
for (var i = 0; i < sortArr.length; i ++ ) {
for (var j = i + 1; j < sortArr.length; j ++) {
if (sortArr[i] > sortArr[j]) {
var temp = sortArr[j];
sortArr[j] = sortArr[i];
sortArr[i] = temp;
}
}
}
// console.log(sortArr);
//直接插入排序
//插入排序 通过构建有序序列 对于未排序的数据 在已排序的序列中从后向前扫描 找到位置并插入
//从第一个元素开始 该元素可以认为已经被排序
//取出下一个元素 在已经排序的元素序列中从后向前扫描
//如果该元素(已排序)大于新元素 将该元素移到下一位置
//重复步骤3 直到找到已排序的元素小雨或等于新元素的位置
//将新元素插入到该位置后
//重复步骤2-5
//思路总结 需要排序的元素先额外缓存起来 然后套用内循环 使得需要调整的元素赋值给他后面的一个位置上
//形成依次挪位 最后因为内循环在判断条件不生效的时候停止 意味着找到了该元素的正确位置 然后赋值上去 完成排序
var newArrs = [4,567,89,56,565,677,8,90,34];
function insertSort(arr) {
let len = arr.length;
let preIndex,current;
for (let i = 1; i < len; i ++) {
current = arr[i];
preIndex = i - 1;
while (preIndex >= 0 && arr[preIndex] > current) {
//比较大的向后移动
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
//如果while循环没发生 那么证明current就是在当前i位置
//如果while循环发生了 代表已找到正确的位置
arr[preIndex + 1] = current;
}
return arr;
}
//二分插入排序
//二分插入排序 是一种直接在插入排序上进行的小改动的算法 与直接插排最大的区别在于查找插入位置时使用的是二分查找的方式
// 1.从第一个元素开始 认为该元素已经排序
// 2.取出下一个元素 在已排序序列中二分查找到一个比他大的元素位置
// 3.将元素插入到该位置后
// 4.重复上面两步
var binaryArrs = [4,34,56,89,565,677,8,90];
function binaryInsertSort(arr) {
var len = arr.length;
for (let i = 1; i < len; i++ ) {
var current = arr[i];
var left = 0;
var right = i - 1;
while(left <= right) {
var mid = parseInt((left + right) / 2);
if (current < arr[mid]) {
right = mid - 1;
}else {
left = mid + 1;
}
}
for (var j = i - 1;j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = current;
}
return arr;
}
console.log(binaryInsertSort(binaryArrs));
//二分查找算法 比如查找数组中某个元素的位置
//必须是在有序的序列中查找 否则不能使用
function binarQuery(arr,element) {
var left = 0;
var right = arr.length - 1;
while (left <= right) {
var mid = parseInt((left + right) / 2);
if (element < arr[mid]) {
right = mid - 1;
}else if (element > arr[mid]) {
left = mid + 1;
}else {
return mid;
}
}
}
console.log(binarQuery([1,2,3,4,5,6],5));
</script>
</body>
</html>
后续会继续补充