冒泡排序&選擇排序
冒泡排序
從第一個數開始從左往右，它會把相鄰的兩個數進行比較；
如果左邊的數比右邊的數大，那么它就會立即交換順序繼續往后比較；
如果左邊的數比右邊的小，那么右邊的數就會去往后繼續比較；
這樣第一輪比較下來會確定最大的值
第二輪下來確定第二大的值
依次類推…
完成排序
假設有n個數需要用冒泡排序進行排列如何實作？
分析：
n個數，那么我們需要進行 n-1 輪的比較，因為最后一個數可以不用比較了；
第一輪里面需要比較n-1次（因為假設有n個數，我們從第一個開始的數得跟另外n-1個數進行比較）；
往后的每一輪都比前一輪少比較一次（每次比較都確定了一個數，往后的數就少比較一個）；
那么我們可以有兩層回圈，外層回圈控制比較的輪數，內層回圈控制比較的次數
// 使用冒泡排序將陣列進行排序
var arr = [6,8,9,8,5,7,1,3,2]
// 根據剛才的分析，假設這個陣列有n個數，其實就是arr.length個數
// 需要進行arr.length-1輪的比較
// 第一輪里面需要比較length-1次
// 往后每一輪都比前一輪少一次，讓變數再回圈之后--運算
// 外層回圈控制比較輪數,從1開始的話就是到length-1
/* for (var i = 1; i <= arr.length - 1; i++) {
}
*/
// 規范點寫我們需要從0開始(做一個合格的程式員，從0開始計算),那么就是到length-2
for (var i = 0; i < arr.length-2; i++) {
// 內層回圈控制比較次數
// 假設arr.length = 5 ,如下分析
// arr.length i 比較次數
// 5 0 4
// 5 1 3
// 5 2 2
// arr.length i arr.length-i-1
for (var j = 0; j < arr.length - i - 1; j++) {
// 相鄰的兩個數進行比較 arr[j]和arr[j+1]進行比較
if (arr[j] > arr[j+1]){
// 交換
var temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
console.log(arr) // [1,2,3,5,6,7,8,8,9]
選擇排序
選擇排序在排序的程序中他會記錄下標；
就是說我們從第一個數開始，以它為基準數，從左往右一個一個去進行比較；
當遇到比自己還小的數，那么就會記錄這個數的下標；
當這一輪比較結束，那么久確定了一個最小值的下標；然后將這個最小值跟基準值做交換；
以此類推…
完成排序
var arr = [3,5,2,7,1,9,4]
// 一共有arr.length個數，那么總的回圈輪數：arr.length-1
for (var i = 0; i < arr.length - 1; i++) {
// 先假設當前最小值的下標為i
var min = i
// 用假設的最小值去跟后面的值一一比較
// 如果遇到后面的值比假設的最小值還要小
// 那么假設的最小值的下標就應該重新賦值為后面最小值的下標
// 當一輪下來就可以的得到最小值的索引，這時候再交換
// 內層回圈從i+1開始，每一趟都要比較到最后一個
for (var j = i + 1; j < arr.length; j++) {
// 判斷arr[min]是否大于arr[j],如果大于了，說明arr[j]才是最小值
// min就應該重新賦值為j
if (arr[min] > arr[j]){
min = j
}
}
// 內層回圈結束以后，當前這一輪的最小值就被找到了
// 讓arr[i]和arr[min]交換
if (i != min) {
var temp = arr[i]
arr[i] = arr[min]
arr[min] = temp
}
}
console.log(arr) // [1,2,3,4,5,7,9]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240965.html
標籤：其他