JavaScript實作選擇排序演算法的實例分析（圖）
- 黄舟原創
- 2017-04-15 09:31:361914瀏覽
這篇文章主要介紹了JavaScript實現的選擇排序演算法,結合實例形式分析了選擇排序的原理、實現步驟與相關操作技巧,需要的朋友可以參考下
本文實例講述了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），但這種排序有一個缺點就是佔用空間大。
所以我們需要介紹一個更優秀的排序，也就是堆排序。
附：堆排序演算法
堆排序只需要一個記錄大小的輔助空間，每個待排序的記錄僅佔用一個儲存空間。
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。我們以大跟堆為例子，排序的基本操作如下：
首先是建堆，建堆就是不斷調整堆的過程，從len2處開始調整，一直到第一個節點，此處len是堆中元素的個數。建堆的過程是線性的過程，從len2到0處一直呼叫調整堆的過程，建堆的時間複雜度為O（n）。
接下來是調整堆，調整堆在建堆和堆排序的過程中都會用到，利用的想法是比較節點i和它的孩子節點left( i)和right(i)，選出三者最大（或最小）者，如果最大（小）值不是節點i而是它的一個子節點，那麼交換兩個節點，然後繼續遞迴.
接著是堆排序：將堆的根節點取出，最後一個元素取代根節點，將前面len-1個節點繼續進行堆調整的過程，然後再講根節點取出，直到所有結點取出。 調整堆的時間複雜度為O(log2n)
所以堆排序的時間複雜度為O（nlog2n）。堆排序是就地排序，其輔助空間為O（1）。但是它不穩定，（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前 和排序後他們的相對位置不改變）。
下面模擬建堆的過程：
堆排序對於記錄數較少的檔案並不值得提倡，但是對於n較大的檔案還是挺有效的。
以上是JavaScript實作選擇排序演算法的實例分析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！