快捷導(dǎo)航

JavaScript實(shí)現(xiàn)快速排序(自已編寫)

更新時間：2012年12月19日 11:13:15 作者：

用到j(luò)avascript的排序一組數(shù)字，js沒有直接的數(shù)字比較的函數(shù)可以調(diào)用，所以自己寫了一個快速排序,需要的朋友可以了解下

簡述：
用到j(luò)avascript的排序一組數(shù)字，js沒有直接的數(shù)字比較的函數(shù)可以調(diào)用，所以自己寫了一個快速排序
知識點(diǎn)：
1. 正則表達(dá)式提取正負(fù)數(shù)字的string
2. str 轉(zhuǎn)數(shù)字放回列表
3. js的對象Sort類的聲明及定義
4. Sort類構(gòu)造函數(shù)、成員函數(shù)定義方式（prototype)
5. 快速排序算法
代碼：

復(fù)制代碼代碼如下:

 
<!DOCTYPE html> 
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />. 
<html> 
<title>Quick Sort</title> 
<head> 
<script type = "text/javascript"> 
/*************Get Number From Input***********/ 
function getNumList(){ 
var result = ""; 
var nums = document.getElementById('numbers').value; 
var reg = /([-][1-9][0-9]*)|([1-9][0-9]*)/g; 
var numStrList = nums.match(reg); 
var numList = new Array(); 
if(numStrList != null){ 
for(var i = 0;i < numStrList.length;i++){ 
var intNumber = parseInt(numStrList[i]); 
numList.push(intNumber); 
} 
} 
return MainProgram(numList); 
}; 

/*****************Main*************************/ 
function MainProgram(numList){ 
var sort = new Sort(numList); 
var sortedList = sort.getSortedList(); 
if(sortedList == null) 
document.getElementById('result').innerHTML = "WRONG INPUT"; 
else{ 
document.getElementById('result').innerHTML = sortedList.join(','); 
} 
} 

/**************Sort Class***********************/ 
var Sort = function(list){ 
this.resultList = list; 
}; 

Sort.prototype.Partition = function(start,end){ 
var baseValue = this.resultList[start]; 
var basePos = start; 
for(var j = start + 1;j <= end;j++){ 
if(baseValue > this.resultList[j]){ 
basePos++; //move the base position 
this.Swap(basePos,j); 
} 
} 
// move the base value to the correct place , before are smaller , behind are bigger 
this.Swap(start,basePos); 
return basePos; 
} 

Sort.prototype.QuickSort = function(start,end){ 
if(start < end){ 
var basePos = this.Partition(start,end); 
this.QuickSort(start,basePos - 1); 
this.QuickSort(basePos + 1, end); 
} 
}; 

Sort.prototype.Swap = function(pos1,pos2){ 
var temp = this.resultList[pos1]; 
this.resultList[pos1] = this.resultList[pos2]; 
this.resultList[pos2] = temp; 
} 

Sort.prototype.getSortedList = function(){ 
this.QuickSort(0,this.resultList.length - 1); 
return this.resultList; 
}; 

</script> 
</head> 
<body> 
<B> Quick Sort</B> 
<br> 
<br> 
<input type= "text" id = 'numbers' value = '' /> 
<input type = 'button' value = "exec" onclick = 'getNumList()'/> 
<br> 
<br> 
<B>SORTED LIST: <B> <b id = 'result'></b> 
</body> 
</html> 