快捷導(dǎo)航

JavaScript實(shí)現(xiàn)的選擇排序算法實(shí)例分析

更新時間：2017年04月14日 11:32:38 作者：布瑞澤的童話

這篇文章主要介紹了JavaScript實(shí)現(xiàn)的選擇排序算法,結(jié)合實(shí)例形式分析了選擇排序的原理、實(shí)現(xiàn)步驟與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了JavaScript實(shí)現(xiàn)的選擇排序算法。分享給大家供大家參考，具體如下：

簡單選擇排序是人們最熟悉的比較方式，其算法思想為：從數(shù)組的開頭開始，將第一個元素和其他元素進(jìn)行比較。檢查完所有元素后，最小的元素會被放到數(shù)組的第一個位置，然后算法會從第二個位置繼續(xù)。這個過程會一直進(jìn)行，當(dāng)進(jìn)行到數(shù)組的倒數(shù)第二個位置時，所有的數(shù)據(jù)便完成了排序。

代碼如下：

<!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++){//外循環(huán)選中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果內(nèi)循環(huán)中元素比選中元素小
     min=inner;//將其標(biāo)為最小元素
    }//直到每次外循環(huán)的最小元素
    swap(nums,outer,min);//最小值被調(diào)整到合適的位置
   }
  }
 }
 function swap(arr,i,j){//交換位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//顯示數(shù)組
  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>

分析可得，簡單選擇排序的時間復(fù)雜度為O（n2）。選擇排序的主要操作是進(jìn)行關(guān)鍵字之間的比較，因此改進(jìn)簡單選擇排序應(yīng)該從如何減少比較出發(fā)。其實(shí)現(xiàn)實(shí)生活中就有一個很好的例子，就是比賽總的錦標(biāo)賽。8個人中選出冠軍其實(shí)不需要7+6+5=18場比賽，可以通過兩兩比較也就是11場比賽。這種方法叫做樹形選擇排序。

樹形選擇排序是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法，首先對n個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中n/2個較小者之間再進(jìn)行兩兩比較，直到找出最小關(guān)鍵字。可以通過一個完全二叉樹來表示，由于含有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1，所以排序過程中每選擇一個次小關(guān)鍵字僅需要log2n次操作，所以其時間復(fù)雜度O（nlog2n），但是這種排序有一種缺點(diǎn)就是占用空間大。

所以我們需要介紹一種更加優(yōu)秀的排序，也就是堆排序。

附：堆排序算法

堆排序只需要一個記錄大小的輔助空間，每個待排序的記錄僅占用一個存儲空間。

堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最?。┻@一特征，使得當(dāng)前無序區(qū)中選取最大（或最?。╆P(guān)鍵字的記錄變得簡單。我們以大跟堆為例子，排序的基本操作如下：

首先是建堆，建堆就是不斷調(diào)整堆的過程，從len2處開始調(diào)整，一直到第一個節(jié)點(diǎn)，此處len是堆中元素的個數(shù)。建堆的過程是線性的過程，從len2到0處一直調(diào)用調(diào)整堆的過程，建堆的時間復(fù)雜度為O（n）。
接下來是調(diào)整堆，調(diào)整堆在建堆和堆排序的過程中都會用到，利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i)和right(i)，選出三者最大（或最?。┱撸绻畲螅ㄐ。┲挡皇枪?jié)點(diǎn)i而是它的一個子節(jié)點(diǎn)，那么交換兩個節(jié)點(diǎn)，然后繼續(xù)遞歸。
然后是堆排序：將堆的根節(jié)點(diǎn)取出，最后一個元素替換根節(jié)點(diǎn)，將前面len-1個節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再講根節(jié)點(diǎn)取出，直到所有結(jié)點(diǎn)取出。調(diào)整堆的時間復(fù)雜度為O(log2n)
所以堆排序的時間復(fù)雜度為O（nlog2n）。堆排序是就地排序，其輔助空間為O（1）。但是它不穩(wěn)定，（排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個元素的話，排序前和排序后他們的相對位置不發(fā)生變化）。

下面模擬建堆的過程：