算法之排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法之排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3098字,纯文字阅读大概需要5分钟。
内容图文
![算法之排序](/upload/InfoBanner/zyjiaocheng/739/e6e96e07edd74456aecd6995c8844bd7.jpg)
1. 时间复杂度就是while的次数,二分查找O(h)=O(log2n)
2. 冒泡排序(O(n^2) 、稳定)
它重复地走访过要排序的数列,依次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
function bubbleSort(arr){ const len = arr.length; for(let i = 0; i < len; i++){ for(let j = 0; j < len - 1 - i; j++){ if(arr[j] > arr[j + 1]){ [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; } } } return arr; }
3. 快排(O(nlogn))
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
var quickSort = function(arr){ if(arr.length <= 1) {return arr;} const midIndex = Math.floor(arr.length / 2); const mid = arr.splice(midIndex, 1)[0]; const left = [], right = []; arr.forEach(function(item){ if(item < mid){ left.push(item); }else{ right.push(item); } }) return quickSort(left).concat([mid], quickSort(right)); }
4. 选择排序 (O(n^2))
每次从待排序的数据中选出最小(或最大)的一个元素,存放在序列的起始位置,第二次从第二个开始,后面依次类推,直到全部待排序的数据元素排完。
function selectionSort(arr){ const first = arr[0]; for(var i=0;i<arr.length-1;i++){ let minIndex = i; for(var j=i+1;j<arr.length;j++){ if(arr[minIndex]>arr[j]){ minIndex = j; } } if(minIndex !== i){ const tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } return arr; }
5. 归并排序(O(nlogn) 、稳定)
先分解再合并,将有序子序列进行合并。
function mergeSort(arr){ if(arr.length <= 1){ return arr; } const midIndex = Math.floor(arr.length/2); const leftArr = arr.slice(0, midIndex); const rightArr = arr.slice(midIndex); return merge(mergeSort(leftArr), mergeSort(rightArr)); } function merge(left, right) { var result = []; while(left.length > 0 && right.length > 0) { if(left[0] < right[0]) { result.push(left.shift()); }else{ result.push(right.shift()); } } return result.concat(left).concat(right); }
6. 堆排序(O(nlogn))
堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。
7. 直接插入排序(O(n^2) 、稳定)
每次将一个待排序的记录,按照其关键字的大小插入到有序队列的合适位置里,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。
function insertionSort(arr) { let len = arr.length, preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; } return arr; }
8. 希尔排序(O(n^2))
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组。
function shellSort(arr) { let len = arr.length, temp, gap = 1; while(gap < len / 3) { gap = gap * 3 + 1; } 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; }
转载于:https://www.cnblogs.com/colima/p/7339427.html
内容总结
以上是互联网集市为您收集整理的算法之排序全部内容,希望文章能够帮你解决算法之排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。