关于算法的问题
冒泡排序
第一次循环，从第一位开始，与后一位的进行比较，如果前一位比后一位大则交换两个的值，一直比对到最后一位，这样最后一个值就是最大的值了，下一次循环就没有必要和最后一项比了，所以每次循环都要减少一次对比
- 代码如下
function bubbleSort(arr) {
var change = function (index1, index2) {
var temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
var len = arr.length
if (len <= 1) return arr
for (var i = 0; i < len - 1; i++) { // 表示有len-2轮外循环
for (var j = 0; j < len - 1 - i; j++) { // 每完成一轮则减少一次内循环，因为最后一个的位置是排好的
if (arr[j] > arr[j + 1]) {
change(j, j + 1)
}
}
}
return arr
}
选择排序
第一次循环，找出最小的值排序到第一位上，这样下一次循环的时候就不用从第一位开始比较了，因为他已经是里面最小的了，下一次循环也就是找最小的值然后排在第二位上，以此来进行排序
- 代码如下
function chooseSort(arr) {
var len = arr.length
if (len <= 1) return arr
var max = 0
for (var i = 0; i < len; i++) {
max = i
for (var j = i; j < len; j++) { // 内循环然后找出最小的index然后与i位置上的值进行交换
if (arr[j] > arr[max]) {
max = j
}
}
if (max != i) {
var change = arr[i]
arr[i] = arr[max]
arr[max] = change
}
}
return arr
}
插入排序
每次循环获取固定的插入项，插入项和其前面的值进行比较，插入比他小的值的后面，若比较的过程中比插入值大，则比较项向后挪空出位置给插入项，依次比较后插入插入值即可
- 代码如下
function insertSort(arr) {
var len = arr.length,j,insert
if (len < 0) return 0
for (var i = 1; i < len; i++) {
j = i
insert = arr[i] // 获取插入值
while (insert < arr[j - 1] && j > 0) { // 比较插入值和前面的值进行比较
arr[j] = arr[j-1]
j--
}
arr[j] = insert
}
return arr
}
选择排序
第一次循环，找出最小的值排序到第一位上，这样下一次循环的时候就不用从第一位开始比较了，因为他已经是里面最小的了，下一次循环也就是找最小的值然后排在第二位上，以此来进行排序
- 代码如下
function chooseSort(arr) {
var len = arr.length
if (len <= 1) return arr
var max = 0
for (var i = 0; i < len; i++) {
max = i
for (var j = i; j < len; j++) { // 内循环然后找出最小的index然后与i位置上的值进行交换
if (arr[j] > arr[max]) {
max = j
}
}
if (max != i) {
var change = arr[i]
arr[i] = arr[max]
arr[max] = change
}
}
return arr
}
归并排序
要进行归并首先要分离，将一个一个的大数组，从“中”分开，一直分裂到全是只有一个元素的数组，然后依次比较后合并。
- 代码如下
// 归并利用了递归，将无序的数组进行分割，成一个一个的小数组，重新归并成一个排好序的大数组
function mergeSort(arr) {
var len = arr.length
if (len === 1) return arr
var mid = ~~(len / 2),
left = arr.slice(0, mid),
right = arr.slice(mid)
console.log(left,right,'分组')
return merge(mergeSort(left),mergeSort(right))
}
function merge(left, right) {
console.log(left,right,'合并')
var result = []
while(left.length && right.length) { // 一个一个值进行抽离对比，小的放进去，首先两边的数组排好序
if(left[0] <right[0]) {
result.push(left.shift()) //数组不断的从新抽离分配
} else {
result.push(right.shift())
}
}
result = result.concat(left,right)
console.log(result,'结果')
return result
}
var arr1 = [2,4,1,5,3,6]
mergeSort(arr1)
// 分组顺序 左left 右right
// [2, 4, 1] [5, 3, 6]
// [2] [4, 1]
// [4] [1]
// [5] [3, 6]
// [3] [6]
// [2, 4, 1] [5, 3, 6] "分组"
// [2] [4, 1] "分组"
// [4] [1] "分组"
// [4] [1] "合并" 4>1 => [1] => [1,4]
// [2] [1, 4] "合并" 2>1 => [1] => 2<4 => [1,2] => [1,2,4]
// [5] [3, 6] "分组"
// [3] [6] "分组"
// [3] [6] "合并" 3<6 => [3,6]
// [5] [3, 6] "合并" 5<3 => [3] => 5<6 => [3,5] => [3,5,6]
// [1, 2, 4] [3, 5, 6] "合并" 1<3 => [1] => 2<3 => [1,2] => 4>3 => [1,2,3] => 4<5 => [1,2,3,4] => [1,2,3,4,5,6]
// [1, 2, 3, 4, 5, 6]
快速排序
设置一个基准，大于基准在右边，小于基准在左边，然后在不断的去分化分好的数组，直到只剩下一个元素的数组
- 代码如下
// 使用递归
function quickSort(arr) {
var len = arr.length
var left = []
var right = []
if (len <= 1) return arr
var mid = ~~(len / 2)
for (var i = 0; i < len; i++) {
if (i === mid) continue
if (arr[i] < arr[mid]) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(arr[mid],quickSort(right))
}
网友评论