時(shí)間復(fù)雜度:算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),描述了算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度越低,效率越高。
自我理解:一個(gè)算法,運(yùn)行了幾次時(shí)間復(fù)雜度就為多少,如運(yùn)行了n次,則時(shí)間復(fù)雜度為O(n)。
1.冒泡排序
解析:1.比較相鄰的兩個(gè)元素,如果前一個(gè)比后一個(gè)大,則交換位置。
2.第一輪的時(shí)候最后一個(gè)元素應(yīng)該是最大的一個(gè)。
3.按照步驟一的方法進(jìn)行相鄰兩個(gè)元素的比較,這個(gè)時(shí)候由于最后一個(gè)元素已經(jīng)是最大的了,所以最后一個(gè)元素不用比較。
function sort(elements){ for(var i=0;ielements[j+1]){ var swap=elements[j]; elements[j]=elements[j+1]; elements[j+1]=swap; } } } } var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8]; console.log('before: ' + elements); sort(elements); console.log(' after: ' + elements);
2.快速排序
解析:快速排序是對(duì)冒泡排序的一種改進(jìn),第一趟排序時(shí)將數(shù)據(jù)分成兩部分,一部分比另一部分的所有數(shù)據(jù)都要小。然后遞歸調(diào)用,在兩邊都實(shí)行快速排序。
function quickSort(elements) { if (elements.length <= 1) { return elements; } var pivotIndex = Math.floor(elements.length / 2); var pivot = elements.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < elements.length; i++){ if (elements[i] < pivot) { left.push(elements[i]); } else { right.push(elements[i]); } } return quickSort(left).concat([pivot], quickSort(right)); }; var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5]; alert(quickSort(elements));
3.插入排序
解析:
(1) 從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序
(2) 取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描
(3) 如果該元素(已排序)大于新元素,將該元素移到下一位置
(4) 重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置
(5)將新元素插入到下一位置中
(6) 重復(fù)步驟2
insertSort: function(elements) { var i = 1, j, step, key, len = elements.length; for (; i < len; i++) { step = j = i; key = elements[j]; while (--j > -1) { if (elements[j] > key) { elements[j + 1] = elements[j]; } else { break; } } elements[j + 1] = key; } return elements; }
2.二分查找
解析:二分查找,也為折半查找。首先要找到一個(gè)中間值,通過與中間值比較,大的放又,小的放在左邊。再在兩邊中尋找中間值,持續(xù)以上操作,直到找到所在位置為止。
(1)遞歸方法
function binarySearch(data,item,start,end){ var end=end || data.length-1; var start=start || 0; var m=Math.floor((start+end)/2); if(item==data[m]){ return m; }else if(item
(2)非遞歸方法
function binarySearch(data, item){ var h = data.length - 1, l = 0; while(l <= h){ var m = Math.floor((h + l) / 2); if(data[m] == item){ return m; } if(item > data[m]){ l = m + 1; }else{ h = m - 1; } } return false; } var arr=[34,12,5,123,2,745,32,4]; binarySearch(arr,5);
聲明:本網(wǎng)頁內(nèi)容旨在傳播知識(shí),若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系,我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com