DIV CSS 佈局教程網

用 JavaScript 手寫快速排序算法
編輯:JavaScript基礎知識     

簡述:JavaScript 沒有現成的數字比較排序函數,為了對一組數字排序,這裡自己實現了一個快速排序。

涉及知識點:

1. 用正則表達式從字符串中提取正負數字
2. 字符串轉數字後放回列表
3. JS 中對象(Sort 類)的聲明與定義
4. Sort 類構造函數、成員函數的定義方式(prototype)
5. 快速排序算法本身

代碼:

<!DOCTYPE html>
<html>
<title>Quick Sort</title>
<head>
<script type = "text/javascript">
/************* 從輸入中提取數字 *************/
function getNumList(){
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);
};

/***************** 主程序 *****************/
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 類 *****************/
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++;
this.Swap(basePos,j);
}
}
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>

思路解析:Partition 是快速排序的核心。它選定第一個元素作為基準值(baseValue),遍歷其餘元素,把比基準小的元素逐步交換到左側,最後將基準值放到正確位置——左邊都比它小,右邊都比它大,並返回基準的最終位置。QuickSort 再對基準左右兩段遞歸地重複這一過程,直到區間只剩一個元素為止。Swap 則封裝了兩元素交換的細節。

輸入一串數字後點擊執行,即可看到排序結果:

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved