本文實例講述了JavaScript實現的選擇排序算法。分享給大家供大家參考，具體如下：
簡單選擇排序是人們最熟悉的比較方式，其算法思想為：從數組的開頭開始，將第一個元素和其他元素進行比較。檢查完所有元素后，最小的元素會被放到數組的第一個位置，然后算法會從第二個位置繼續。這個過程會一直進行，當進行到數組的倒數第二個位置時，所有的數據便完成了排序。
代碼如下：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript選擇排序</title>
</head>
<body>
<script type="text/javascript">
function selectSort(nums){//選擇排序
var min;//最小值
for(var outer=0;outer<nums.length-1;outer++){//外循環選中元素
min=outer;
for(var inner=outer+1;inner<=nums.length;++inner){
if(nums[inner]<nums[min]){//如果內循環中元素比選中元素小
min=inner;//將其標為最小元素
}//直到每次外循環的最小元素
swap(nums,outer,min);//最小值被調整到合適的位置
}
}
}
function swap(arr,i,j){//交換位置
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
function show(nums){//顯示數組
for(var i=0;i<nums.length;i++){
document.write(nums[i]+' ');
}
document.write('<br>');
}
var nums=[6,8,0,6,7,4,3,5,5,10];
show(nums);//6 8 0 6 7 4 3 5 5 10
selectSort(nums);
show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>
分析可得，簡單選擇排序的時間復雜度為O（n2）。選擇排序的主要操作是進行關鍵字之間的比較，因此改進簡單選擇排序應該從如何減少比較出發。其實現實生活中就有一個很好的例子，就是比賽總的錦標賽。8個人中選出冠軍其實不需要7+6+5=18場比賽，可以通過兩兩比較也就是11場比賽。這種方法叫做樹形選擇排序。
樹形選擇排序是一種按照錦標賽的思想進行選擇排序的方法，首先對n個記錄的關鍵字進行兩兩比較，然后在其中n/2個較小者之間再進行兩兩比較，直到找出最小關鍵字?？梢酝ㄟ^一個完全二叉樹來表示，由于含有n個結點的完全二叉樹的深度為log2n+1，所以排序過程中每選擇一個次小關鍵字僅需要log2n次操作，所以其時間復雜度O（nlog2n），但是這種排序有一種缺點就是占用空間大。
所以我們需要介紹一種更加優秀的排序，也就是堆排序。
附：堆排序算法
堆排序只需要一個記錄大小的輔助空間，每個待排序的記錄僅占用一個存儲空間。
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最?。┻@一特征，使得當前無序區中選取最大（或最?。╆P鍵字的記錄變得簡單。我們以大跟堆為例子，排序的基本操作如下：
首先是建堆，建堆就是不斷調整堆的過程，從len2處開始調整，一直到第一個節點，此處len是堆中元素的個數。建堆的過程是線性的過程，從len2到0處一直調用調整堆的過程，建堆的時間復雜度為O（n）。
接下來是調整堆，調整堆在建堆和堆排序的過程中都會用到，利用的思想是比較節點i和它的孩子節點left(i)和right(i)，選出三者最大（或最?。┱?，如果最大（?。┲挡皇枪濣ci而是它的一個子節點，那么交換兩個節點，然后繼續遞歸。
然后是堆排序：將堆的根節點取出，最后一個元素替換根節點，將前面len-1個節點繼續進行堆調整的過程，然后再講根節點取出，直到所有結點取出。調整堆的時間復雜度為O(log2n)
所以堆排序的時間復雜度為O（nlog2n）。堆排序是就地排序，其輔助空間為O（1）。但是它不穩定，（排序的穩定性是指如果在排序的序列中，存在前后相同的兩個元素的話，排序前 和排序后他們的相對位置不發生變化）。
下面模擬建堆的過程：
堆排序對于記錄數較少的文件并不值得提倡，但是對于n較大的文件還是挺有效的。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
