關(guān)于算法的問題
冒泡排序
第一次循環(huán)，從第一位開始，與后一位的進行比較，如果前一位比后一位大則交換兩個的值，一直比對到最后一位，這樣最后一個值就是最大的值了，下一次循環(huán)就沒有必要和最后一項比了，所以每次循環(huán)都要減少一次對比
- 代碼如下
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++) { // 表示有l(wèi)en-2輪外循環(huán)
for (var j = 0; j < len - 1 - i; j++) { // 每完成一輪則減少一次內(nèi)循環(huán)，因為最后一個的位置是排好的
if (arr[j] > arr[j + 1]) {
change(j, j + 1)
}
}
}
return arr
}
選擇排序
第一次循環(huán)，找出最小的值排序到第一位上，這樣下一次循環(huán)的時候就不用從第一位開始比較了，因為他已經(jīng)是里面最小的了，下一次循環(huán)也就是找最小的值然后排在第二位上，以此來進行排序
- 代碼如下
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++) { // 內(nèi)循環(huán)然后找出最小的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
}
插入排序
每次循環(huán)獲取固定的插入項，插入項和其前面的值進行比較，插入比他小的值的后面，若比較的過程中比插入值大，則比較項向后挪空出位置給插入項，依次比較后插入插入值即可
- 代碼如下
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
}
選擇排序
第一次循環(huán)，找出最小的值排序到第一位上，這樣下一次循環(huán)的時候就不用從第一位開始比較了，因為他已經(jīng)是里面最小的了，下一次循環(huán)也就是找最小的值然后排在第二位上，以此來進行排序
- 代碼如下
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++) { // 內(nèi)循環(huán)然后找出最小的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
}
歸并排序
要進行歸并首先要分離，將一個一個的大數(shù)組，從“中”分開，一直分裂到全是只有一個元素的數(shù)組，然后依次比較后合并。
- 代碼如下
// 歸并利用了遞歸，將無序的數(shù)組進行分割，成一個一個的小數(shù)組，重新歸并成一個排好序的大數(shù)組
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) { // 一個一個值進行抽離對比，小的放進去，首先兩邊的數(shù)組排好序
if(left[0] <right[0]) {
result.push(left.shift()) //數(shù)組不斷的從新抽離分配
} else {
result.push(right.shift())
}
}
result = result.concat(left,right)
console.log(result,'結(jié)果')
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]
快速排序
設(shè)置一個基準，大于基準在右邊，小于基準在左邊，然后在不斷的去分化分好的數(shù)組，直到只剩下一個元素的數(shù)組
- 代碼如下
// 使用遞歸
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))
}
