信息门户网站开发合同,广西新站seo,启迪网站建设,兰州大学网页与网站设计排序算法
一、选择排序
1.算法简介
选择排序是一个简单直观的排序方法#xff0c;它的工作原理很简单#xff0c;首先从未排序序列中找到最大的元素#xff0c;放到已排序序列的末尾#xff0c;重复上述步骤#xff0c;直到所有元素排序完毕。
2.算法描述
1#xff…排序算法
一、选择排序
1.算法简介
选择排序是一个简单直观的排序方法它的工作原理很简单首先从未排序序列中找到最大的元素放到已排序序列的末尾重复上述步骤直到所有元素排序完毕。
2.算法描述
1假设未排序序列的第一个是最大值记下该元素的位置从前往后比较 2若某个元素比该元素大覆盖之前的位置 3重复第二个步骤直到找到未排序的末尾 4将未排序元素的第一个元素和最大元素交换位置 5重复前面几个步骤直到所有元素都已经排序。
3.算法分析
选择排序的交换操作次数最好情况已经有序为0次最坏情况逆序n-1次因此交换操作次数位于0(n-1)次之间比较操作次数n-1…210为n(n-1)/2次交换元素赋值操作为3次逆序需要n-1趟交换因此赋值操作位于03(n-1)次之间。由于需要交换位置所以肯定是不稳定的。
时间复杂度均为o(n^2) 空间复杂度为o(1) 不稳定
4.代码实现
//选择排序
function selsetSort(arr){var len arr.length;for(var i0;ilen-1;i){for(var ji1;jlen;j){if(arr[i] arr[j]){//寻找最小值var temp arr[i];arr[i] arr[j];arr[j] temp;}}}return arr;
}二、冒泡排序
1.算法简介
列表每两个相邻的数进行比较如果前面的数比后面的数大则交换这两个数一轮排序完成后则无序区减少一个数有序区增加一个数。
2.算法描述
1快速排序的特点就是随机设置一个基准点比如是数组的第一个元素然后数组的其他元素就跟这个基准线进行对比比基准线大的放在左边比基准线小的放在右边 2再设置一个基准线再这样小的放左边大的放右边递归。
3.算法分析
平均时间复杂度O(nn) 、最好情况O(n)、最差情况O(nn)
空间复杂度O(1) 稳定
4.代码实现 function sort(arr){let len arr.length;for (let i 0; i len - 1 ; i) {// 用来标记在一轮冒泡过程中有无交换过let flag false;for (let j 0; j len - i; j) {if(arr[j] arr[j1]){// 交换两个数let temp arr[j];arr[j] arr[j1];arr[j1] temp;flag true;}}// 如果在一轮冒泡过程中没有交换过说明此时的列表已经是排序好的了直接结束循环if(!flag){return;}} }
let arr [2,3,1,4,8,7,9,6];
this.sort(arr;
console.log(arr); 三、插入排序
1.算法简介
所谓插入排序就是把最小的或者最大的一次次插入到最前面从而达到排序的效果
2.算法描述
刚开始将整个数组看作一个无序区每一轮拿无序区的第一数与有序区的数从后往前依次进行比较遇到更大的数则交换每一轮排序完成后有序区增加一个数无序区减少一个数。
3.算法分析
时间复杂度是O(n*n) 空间复杂度为o(1) 稳定
4.代码实现
function sort(arr){let len arr.length;for (let i 1; i len; i) {for (let j i - 1; j 0 ; j--) {if(arr[j] arr[j1]){let temp arr[j1]arr[j1] arr[j]arr[j] temp} } }
}, 四、快速排序
1.算法简介
采用“分治”的思想对于一组数据选择一个基准元素base通常选择第一个或最后一个元素通过第一轮扫描比base小的元素都在base左边比base大的元素都在base右边再有同样的方法递归排序这两部分直到序列中所有数据均有序为止。快速排序算法的性能比冒泡、选择排序都要好和归并排序一样是一个可以用于实战的算法。
2.算法描述
1快速排序的特点就是随机设置一个基准点比如是数组的第一个元素然后数组的其他元素就跟这个基准线进行对比比基准线大的放在左边比基准线小的放在右边 2再设置一个基准线再这样小的放左边大的放右边递归。
3.算法分析
时间复杂度是O(nlogn) 空间复杂度为o(logn) 不稳定
4.代码实现 function sort(arr,l,r){if(l r){let i l;let j r;let mid arr[l];while(i j){while(arr[j] mid i j){j--;}arr[i] arr[j];while(arr[i] mid i j){i;}arr[j] arr[i];}arr[i] midthis.test(arr,l,i-1)this.test(arr,i1,j)return arr}else{return}}, // 测试数据
let arr [2,3,1,4,8,7,9,6];
let res this.sort(arr,0,7);
console.log(res); 五、归并排序
1.算法简介
使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题直到它们变得足够简单以至可以直接解决为止。
2.算法描述
1将给定的列表分为两半如果列表中的元素数为奇数则使其大致相等。
2以相同的方式继续划分子数组直到只剩下单个元素数组。
3从单个元素数组开始合并子数组以便对每个合并的子数组进行排序。
4重复第 3 步单元直到最后得到一个排好序的数组。
3.算法分析
时间复杂度是O(nlogn) 空间复杂度为O(n) 稳定
4.代码实现
function sort(arr){if(arr arr.length 1){const mid Math.floor(arr.length/2)const left arr.slice(0,mid)const right arr.slice(mid);return this.merge(this.sort(left), this.sort(right))}return arr
},
function merge(leftList, rightList){const newList [];const leftLength leftList leftList.length;const rightLength rightList rightList.length;let i 0;let j 0;while (i leftLength j rightLength) {if (leftList[i] rightList[j]) {newList.push(leftList[i]);} else {newList.push(rightList[j]);}}while (i leftLength) {newList.push(leftList[i]);}while (j rightLength) {newList.push(rightList[j]);}return newList;
}, 六、堆排序
1.算法简介
堆是一种特殊的完全二叉树堆分为大根堆和小根堆满足任一节点都比其孩子节点大的一个完全二叉树就是大根堆满足任一节点都比其孩子节点小的一个完全二叉树就是小根堆。
2.算法描述
首先构造一个大根堆此时整个堆是无序区然后将堆顶的元素取出放到有序区也就是数组的最后然后将堆的最后一个元素也就是无序区的最后一个元素放到堆顶堆就少了一个元素此时通过一次向下调整重新使堆有序调整后的堆顶就是整个数组的第二大元素然后重复之前的操作依次将元素放到有序区直到堆变空便可得到排序好的数组。
3.算法分析
时间复杂度是O(nlogn) 空间复杂度为O(1) 不稳定
4.代码实现
function sort(list) {if (list list.length 1) {const len list.length;// 首先构造大根堆从最后一个不是叶子节点的节点开始遍历从后往前依次进行向下调整for (let i Math.floor((len-2)/2); i0; i--) {sift(list, i, len-1);}// 然后将堆的第一元素与有序区的第一个元素进行交换此时有序区增加一个无序区减少一个再进行一次堆的向下调整然后重复上述操作最终使整个数组有序for(let i len-1; i0; i--){const m list[0];list[0] list[i];list[i] m;sift(list, 0, i-1);} }
}/**
* 堆的向下调整
* 先从根节点开始如果孩子节点比父节点大则将该孩子节点赋值给父节点
* 然后指针指向下一层重复上面的操作直到找到孩子节点没有比父节点大的节点终止循环
* 最后将原始的根节点赋值给当前父节点
*/
function sift(li, low, high) {const tmp li[low]; // 缓存根节点let i low; // 当前的父节点最开始指向根节点let j i*21; // 当前的孩子节点最开始指向根节点的左孩子节点while (j high) {// 如果有右孩子节点且比左孩子节点大则j指向右孩子节点if (j1 high li[j1] li[j]) {j;}if (li[j] tmp) {li[i] li[j]; // 将较大的孩子节点赋值给父节点i j; // i指向下一层j i*2 1;} else {break; // 如果当前子节点没有比原始根节点大结束循环}}li[i] tmp; // 最后将原始的根节点赋值给当前父节点
}总结
