- // 1. 插入排序
- // 从第一个元素开始, 该元素可以认为已经被排序;
- // 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
- // 如果该元素 (已排序) 大于新元素, 将该元素移到下一位置;
- // 重复步骤 3, 直到找到已排序的元素小于或者等于新元素的位置;
- // 将新元素插入到该位置后;
- // 重复步骤 2~5
- function insertSort (arr) {
- var _arr = [].concat(arr)
- var len = _arr.length
- for (var i = 1; i < len; i++) {
- var key = _arr[i]
- var j = i - 1
- while (j >= 0 && _arr[j] > key) {
- _arr[j + 1] = _arr[j]
- j--
- }
- _arr[j + 1] = key
- }
- return _arr
- }
- console.log(insertSort([2, 3, 4, 1, 4, 7, 9, 8])) // [ 1, 2, 3, 4, 4, 7, 8, 9 ]
- // 2. 快速排序
- // 1.先从数列中取出一个数作为基准数
- // 2.分区过程, 将比这个数大的数全放到它的右边, 小于或等于它的数全放到它的左边
- // 3.再对左右区间重复第二步, 直到各区间只有一个数
- function quickSort (arr) {
- if (arr.length < 2) {
- return arr
- }
- var left = [],
- right = [],
- mid = arr.splice(Math.floor(arr.length / 2), 1)
- for (var i = 0; i < arr.length; i++) {
- if (arr[i] < mid) {
- left.push(arr[i])
- } else {
- right.push(arr[i])
- }
- }
- return bubbleSort(left).concat(mid, bubbleSort(right))
- }
- console.log(quickSort([1, 4, 2, 3, 8, 10, 6, 5])) // [ 1, 2, 3, 4, 5, 6, 8, 10 ]
- // 3. 冒泡排序
- // 比较相邻的前后二个数据, 如果前面数据大于后面的数据, 就将二个 数据交换
- // 这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后, 最大的一个数据就沉到数组第 N-1 个位置
- // N=N-1, 如果 N 不为 0 就重复前面二步, 否则排序完成
- function bubbleSort (arr) {
- for (var i = 0; i < arr.length - 1; i++) {
- for (var j = 0; j < arr.length - i - 1; j++) {
- if (arr[j] > arr[j + 1]) {
- var temp = arr[j]
- arr[j] = arr[j + 1]
- arr[j + 1] = temp
- }
- }
- }
- return arr
- }
- // 4. 选择排序
- // 比如在一个长度为 N 的无序数组中, 在第一趟遍历 N 个数据, 找出其中最小的数值与第一个元素交换, 第二趟遍历剩下的 N-1 个数据, 找出其中最小的数值与第二个元素交换第 N-1 趟遍历剩下的 2 个数据, 找出其中最小的数值与第 N-1 个元素交换, 至此选择排序完成
- function selectSort (arr) {
- var min, temp
- for (var i = 0; i < arr.length - 1; i++) {
- min = i
- for (var j = i + 1; j < arr.length; j++) {
- if (arr[j] < arr[min]) {
- min = j
- }
- }
- temp = arr[i]
- arr[i] = arr[min]
- arr[min] = temp
- }
- return arr
- }
- console.log(selectSort([1, 4, 2, 5, 8, 6, 7]))// [ 1, 2, 4, 5, 6, 7, 8 ]
来源: http://www.bubuko.com/infodetail-2518332.html