JavaScript實作選擇排序演算法的實例分析（圖）-js教程-PHP中文網

JavaScript實作選擇排序演算法的實例分析（圖）

黄舟

發布： 2017-04-15 09:31:36

原創

1860 人瀏覽過

這篇文章主要介紹了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]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 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）。但是它不穩定，（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前和排序後他們的相對位置不改變）。