1.冒泡排序
function bubbleSort(arr){
for(var i =0 ;i < arr.length; i++){
for(var j = i+1; j < arr.length - 1; j++){
if(arr[i] > arr[j]){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));
改進(jìn)冒泡排序： 設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置锨络。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可输拇。
function bubbleSort(arr){
var i = arr.length-1;
while(i>0){
var pos = 0;
for(var j = 0; j < i; j++){
if(arr[j] > arr[j+1]){
pos = j;
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
i = pos;
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));
傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半闯睹。
function bubbleSort(arr){
var low = 0,
hight = arr.length - 1;
var tmp,j;
while(low < hight){
for(j = low; j < hight; ++j){
if(arr[j] > arr[j+1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
--hight;
for(j = hight; j > low; --j){
if(arr[j] < arr[j-1]){
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
++low;
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));
算法分析
- 最佳情況：T(n) = O(n)
當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí) - 最差情況：T(n) = O(n^2)
當(dāng)輸入的數(shù)據(jù)是反序時(shí) - 平均情況：T(n) = O(n^2)
2.選擇排序
(1)算法簡(jiǎn)介
選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法休玩。它的工作原理：首先在未排序序列中找到最蓄蹰埂（大）元素铝宵，存放到排序序列的起始位置首懈，然后翎冲，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最写共恰（大）元素，然后放到已排序序列的末尾府适。以此類推羔飞，直到所有元素均排序完畢。
(2)算法描述和實(shí)現(xiàn)
n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果檐春。具體算法描述如下：
<1>.初始狀態(tài)：無序區(qū)為R[1..n]逻淌，有序區(qū)為空；
<2>.第i趟排序(i=1,2,3…n-1)開始時(shí)疟暖，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）卡儒。該趟排序從當(dāng)前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]田柔，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)骨望；
<3>.n-1趟結(jié)束硬爆，數(shù)組有序化了。
function selectionSort(arr){
var len = arr.length;
var tmp,minIndex;
for(var i = 0; i < len - 1; i++){
minIndex = i;
for(var j = i + 1;j < len ;j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
tmp = arr[i];;
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));
(3)算法分析
- 最佳情況：T(n) = O(n^2)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(n^2)
3.插入排序
(1)算法簡(jiǎn)介
插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法擎鸠。它的工作原理是通過構(gòu)建有序序列缀磕，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描劣光，找到相應(yīng)位置并插入袜蚕。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序）绢涡，因而在從后向前掃描過程中牲剃，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間雄可。
(2)算法描述和實(shí)現(xiàn)
一般來說凿傅，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
<1>.從第一個(gè)元素開始数苫，該元素可以認(rèn)為已經(jīng)被排序聪舒；
<2>.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描文判；
<3>.如果該元素（已排序）大于新元素过椎，將該元素移到下一位置；
<4>.重復(fù)步驟3戏仓，直到找到已排序的元素小于或者等于新元素的位置疚宇；
<5>.將新元素插入到該位置后；
<6>.重復(fù)步驟2~5赏殃。
function insertionSort(arr){
for(var i = 1; i < arr.length; i ++){
var k = arr[i];
var j = i - 1;
while(j >= 0 && arr[j] > k){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = k;
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log( insertionSort(arr));
改進(jìn)插入排序： 查找插入位置時(shí)使用二分查找的方式
function sort(arr){
for(var i = 1; i < arr.length; i ++){
var k = arr[i];
var left = 0,
right = i - 1;
while(left <= right){
var middle = parseInt((right + left) / 2);
if(k < arr[middle]){
right = middle - 1;
}else{
left = middle + 1;
}
}
for(var j = i - 1;j >= left; j--){
arr[j+1] = arr[j];
}
arr[left] = k;
}
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(sort(arr));
(3)算法分析
- 最佳情況：輸入數(shù)組按升序排列敷待。T(n) = O(n)
- 最壞情況：輸入數(shù)組按降序排列。T(n) = O(n^2)
- 平均情況：T(n) = O(n^2)
4.歸并排序
(1)算法簡(jiǎn)介
歸并排序是建立在歸并操作上的一種有效的排序算法仁热。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用榜揖。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并抗蠢，得到完全有序的序列举哟；即先使每個(gè)子序列有序，再使子序列段間有序迅矛。若將兩個(gè)有序表合并成一個(gè)有序表妨猩，稱為2-路歸并。
(2)算法描述和實(shí)現(xiàn)
具體算法描述如下：
<1>.把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列秽褒；
<2>.對(duì)這兩個(gè)子序列分別采用歸并排序壶硅；
<3>.將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列威兜。
function mergeSort(arr){
var len = arr.length;
if(len < 2){
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0,middle),
right = arr.slice(middle);
return merge(mergeSort(left),mergeSort(right));
}
function merge(left,right){
var result = [];
while(left.length && right.length){
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length){
result.push(left.shift());
}
while(right.length){
result.push(right.shift());
}
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
(3)算法分析
- 最佳情況：T(n) = O(n)
- 最差情況：T(n) = O(nlogn)
- 平均情況：T(n) = O(nlogn)
