JavaScript實現的選擇排序算法實例分析

2019-11-19 16:49:24

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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）。但是它不穩定，（排序的穩定性是指如果在排序的序列中，存在前后相同的兩個元素的話，排序前和排序后他們的相對位置不發生變化）。

下面模擬建堆的過程：