- 什么是算法
- 輸入：一個算法必須有零個或以上輸入量
- 輸出：一個算法應(yīng)有一個或以上輸出量
- 明確性：算法的描述必須無歧義详恼，實(shí)際運(yùn)行結(jié)果是確定的
- 有限性：必須在有限個步驟內(nèi)結(jié)束
- 有效性：又稱可行性迎吵，能夠被執(zhí)行者實(shí)現(xiàn)
- 遇到思路障礙怎么辦
- 抽象的問題轉(zhuǎn)化為具體的問題
- 沒見過的問題轉(zhuǎn)化為見過的問題
冒泡排序：高的往后排
- 比較相鄰的兩個元素士飒，第一個比第二個大庸队，則交換兩個
- 對每一對相鄰元素做同樣工作喊暖，這樣最大值被固定到最后
- 重頭開始新一輪的比較试伙，得到新的最大值姚淆，這樣得到倒數(shù)第二位
-
以此類推
12926249-e6ffd5b328c0c2e1.gif
function swap(array,a,b){
var temp
temp = array[a]
array[a] = array[b]
array[b] = temp
}
function sort(array){
var i,j
for(i = 0;i<array.length;i++){
//排了第i次
for(j=0;j<array.length-1-i;j++){
if(array[j] <= array[j+1]){
}else{
swap(array,j,j+1)
}
}
}
return array
}
console.log(sort([3,5,6,2,5,2,4]))
每次最高的排最后
選擇排序：每次選擇最小的兽愤，最小的往前站
- 在序列中找到最小元素(大)彼念，存放在序列的起始位置
- 未排序的序列中繼續(xù)找最小元素挪圾，然后放序列中的第二行
-
以此類推
12926249-1552111813abc71d.gif
function swap(array,a,b){
var temp
temp = array[a]
array[a] = array[b]
array[b] = temp
}
function sort(array){
var i,j,indexMin
for(i=0;i<array.length;i++){
indexMin = i
for(j=i+1;j<array.length;j++){
//找到最小值，將j的值賦給indexMin
if(array[j] < array[indexMin]){
indexMin = j
}
}
swap(array,i,indexMin)
}
return array
}
console.log(sort([3,5,6,2,5,2,4]))
插入排序：撲克牌算法
- 起一張牌逐沙，第二張牌要是小的話放前面
-
第三張牌比較有序區(qū)的元素哲思，比較后插入到合適的位置，以此類推
12926249-e63cb677a8f42840.gif
歸并排序：領(lǐng)導(dǎo)算法 最底層
快速排序：自私算法：前面比我矮吩案。后面比我高
- 1.取出一個元素為基準(zhǔn)
- 2.對數(shù)列進(jìn)行以此比較排序棚赔，比基準(zhǔn)小的放基準(zhǔn)前面，大的放基準(zhǔn)后面徘郭，此操作結(jié)束后靠益，基準(zhǔn)位于數(shù)列中間
-
3.然后分別對基準(zhǔn)兩邊的區(qū)，進(jìn)行以上操作
12926249-d6cb24f0bc157677.gif
var times=0;
var quickSort=function(arr){
//如果數(shù)組長度小于等于1無需判斷直接返回即可
if(arr.length<=1){
return arr;
}
var midIndex=Math.floor(arr.length/2);//取基準(zhǔn)點(diǎn)
var midIndexVal=arr.splice(midIndex,1);//取基準(zhǔn)點(diǎn)的值,splice(index,1)函數(shù)可以返回數(shù)組中被刪除的那個數(shù)arr[index+1]
var left=[];//存放比基準(zhǔn)點(diǎn)小的數(shù)組
var right=[];//存放比基準(zhǔn)點(diǎn)大的數(shù)組
//遍歷數(shù)組崎岂，進(jìn)行判斷分配
for(var i=0;i<arr.length;i++){
if(arr[i]<midIndexVal){
left.push(arr[i]);//比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組
}
else{
right.push(arr[i]);//比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組
}
console.log("第"+(++times)+"次排序后："+arr);
}
//遞歸執(zhí)行以上操作,對左右兩個數(shù)組進(jìn)行操作捆毫，直到數(shù)組長度為<=1；
return quickSort(left).concat(midIndexVal,quickSort(right));//連接數(shù)組
};
console.log(quickSort(arr));
隨機(jī)快速排序法:比快排效率高一些
桶排序
桶排序的工作原理：假設(shè)輸入數(shù)據(jù)服從均勻分布冲甘，將數(shù)據(jù)分到有限數(shù)量的桶里绩卤，每個桶分別排序
缺點(diǎn)：占內(nèi)存
基數(shù)排序：
先從低位排序，然后收集江醇，再慢慢高位排序濒憋，以此類推
12926249-6adaf9386e1e816d.gif
