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

首頁

web前端

js教程

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

黄舟

Apr 15, 2017 am 09:31 AM

javascript演算法選擇排序

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

下面模擬建堆的過程：

堆排序對於記錄數較少的檔案並不值得提倡，但是對於n較大的檔案還是挺有效的。

以上是JavaScript實作選擇排序演算法的實例分析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

Python vs. JavaScript：選擇合適的工具May 08, 2025 am 12:10 AM

選擇Python還是JavaScript取決於項目類型：1)數據科學和自動化任務選擇Python；2)前端和全棧開發選擇JavaScript。 Python因其在數據處理和自動化方面的強大庫而備受青睞，而JavaScript則因其在網頁交互和全棧開發中的優勢而不可或缺。

Python和JavaScript：了解每個的優勢May 06, 2025 am 12:15 AM

Python和JavaScript各有優勢，選擇取決於項目需求和個人偏好。 1.Python易學，語法簡潔，適用於數據科學和後端開發，但執行速度較慢。 2.JavaScript在前端開發中無處不在，異步編程能力強，Node.js使其適用於全棧開發，但語法可能複雜且易出錯。

JavaScript的核心：它是在C還是C上構建的？May 05, 2025 am 12:07 AM

javascriptisnotbuiltoncorc; sanInterpretedlanguagethatrunsonenginesoftenwritteninc.1）JavascriptwasdesignedAsignedAsalightWeight，drackendedlanguageforwebbrowsers.2）Enginesevolvedfromsimpleterterpretpretpretpretpreterterpretpretpretpretpretpretpretpretpretcompilerers，典型地，替代品。

JavaScript應用程序：從前端到後端May 04, 2025 am 12:12 AM

JavaScript可用於前端和後端開發。前端通過DOM操作增強用戶體驗，後端通過Node.js處理服務器任務。 1.前端示例：改變網頁文本內容。 2.後端示例：創建Node.js服務器。

Python vs. JavaScript：您應該學到哪種語言？May 03, 2025 am 12:10 AM

選擇Python還是JavaScript應基於職業發展、學習曲線和生態系統：1)職業發展：Python適合數據科學和後端開發，JavaScript適合前端和全棧開發。 2)學習曲線：Python語法簡潔，適合初學者；JavaScript語法靈活。 3)生態系統：Python有豐富的科學計算庫，JavaScript有強大的前端框架。

JavaScript框架：為現代網絡開發提供動力May 02, 2025 am 12:04 AM

JavaScript框架的強大之處在於簡化開發、提升用戶體驗和應用性能。選擇框架時應考慮：1.項目規模和復雜度，2.團隊經驗，3.生態系統和社區支持。

JavaScript，C和瀏覽器之間的關係May 01, 2025 am 12:06 AM

引言我知道你可能會覺得奇怪，JavaScript、C 和瀏覽器之間到底有什麼關係？它們之間看似毫無關聯，但實際上，它們在現代網絡開發中扮演著非常重要的角色。今天我們就來深入探討一下這三者之間的緊密聯繫。通過這篇文章，你將了解到JavaScript如何在瀏覽器中運行，C 在瀏覽器引擎中的作用，以及它們如何共同推動網頁的渲染和交互。 JavaScript與瀏覽器的關係我們都知道，JavaScript是前端開發的核心語言，它直接在瀏覽器中運行，讓網頁變得生動有趣。你是否曾經想過，為什麼JavaScr