溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了JS前端面試必備——基本排序算法原理與實現方法。分享給大家供大家參考，具體如下：
排序算法是面試及筆試中必考點，本文通過動畫方式演示，通過實例講解，最后給出JavaScript版的排序算法
算法描述：
1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟 3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復步驟 2~5
現有一組數組 arr = [5, 6, 3, 1, 8, 7, 2, 4]
[5] 6 3 1 8 7 2 4 //第一個元素被認為已經被排序 [5,6] 3 1 8 7 2 4 //6與5比較，放在5的右邊 [3，5，6] 1 8 7 2 4 //3與6和5比較，都小，則放入數組頭部 [1,3,5,6] 8 7 2 4 //1與3,5,6比較，則放入頭部 [1,3，5，6，8] 7 2 4 [1,3，5，6,7，8] 2 4 [1，2,3，5，6,7，8] 4 [1，2,3，4，5，6,7，8]
編程思路：雙層循環，外循環控制未排序的元素，內循環控制已排序的元素，將未排序元素設為標桿，與已排序的元素進行比較，小于則交換位置，大于則位置不動
function insertSort(arr){
var tmp;
for(var i=1;i<arr.length;i++){
tmp = arr[i];
for(var j=i;j>=0;j--){
if(arr[j-1]>tmp){
arr[j]=arr[j-1];
}else{
arr[j]=tmp;
break;
}
}
}
return arr
}
時間復雜度O(n^2)
算法描述：直接從待排序數組中選擇一個最小（或最大）數字，放入新數組中。
[1] 5 6 3 8 7 2 4 [1,2] 5 6 3 8 7 4 [1,2,3] 5 6 8 7 2 4 [1,2,3,4] 5 6 8 7 [1,2,3,4,5] 6 8 7 [1,2,3,4,5,6] 8 7 [1,2,3,4,5,6,7] 8 [1,2,3,4,5,6,7,8]
編程思路：先假設第一個元素為最小的，然后通過循環找出最小元素，然后同第一個元素交換，接著假設第二個元素，重復上述操作即可
function selectSort(array) {
var length = array.length,
i,
j,
minIndex,
minValue,
temp;
for (i = 0; i < length - 1; i++) {
minIndex = i;
minValue = array[minIndex];
for (j = i + 1; j < length; j++) {//通過循環選出最小的
if (array[j] < minValue) {
minIndex = j;
minValue = array[minIndex];
}
}
// 交換位置
temp = array[i];
array[i] = minValue;
array[minIndex] = temp;
}
return array
}
時間復雜度O(n^2)
算法描述：
1. 把 n 個記錄看成 n 個長度為 l 的有序子表
2. 進行兩兩歸并使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表
3. 重復第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。
5 6 3 1 8 7 2 4 [5,6] [3,1] [8,7] [2,4] [5,6] [1,3] [7,8] [2,4] [5,6,1,3] [7,8,2,4] [1,3,5,6] [2,4,7,8] [1,2,3,4,5,6,7,8]
編程思路：將數組一直等分，然后合并
function merge(left, right) {
var tmp = [];
while (left.length && right.length) {
if (left[0] < right[0])
tmp.push(left.shift());
else
tmp.push(right.shift());
}
return tmp.concat(left, right);
}
function mergeSort(a) {
if (a.length === 1)
return a;
var mid = Math.floor(a.length / 2)
, left = a.slice(0, mid)
, right = a.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
時間復雜度O(nlogn)
算法描述：
5 6 3 1 8 7 2 4 pivot | 5 6 3 1 9 7 2 4 | storeIndex 5 6 3 1 9 7 2 4//將5同6比較，大于則不更換 | storeIndex 3 6 5 1 9 7 2 4//將5同3比較，小于則更換 | storeIndex 3 6 1 5 9 7 2 4//將5同1比較，小于則不更換 | storeIndex ... 3 6 1 4 9 7 2 5//將5同4比較，小于則更換 | storeIndex 3 6 1 4 5 7 2 9//將標準元素放到正確位置 | storeIndex pivot
上述講解了分區的過程，然后就是對每個子區進行同樣做法
function quickSort(arr){
if(arr.length<=1) return arr;
var partitionIndex=Math.floor(arr.length/2);
var tmp=arr[partitionIndex];
var left=[];
var right=[];
for(var i=0;i<arr.length;i++){
if(arr[i]<tmp){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort(left).concat([tmp],quickSort(right))
}
上述版本會造成堆棧溢出，所以建議使用下面版本
原地分區版：主要區別在于先進行分區處理，將數組分為左小右大
function quickSort(arr){
function swap(arr,right,left){
var tmp = arr[right];
arr[right]=arr[left];
arr[left]=tmp;
}
function partition(arr,left,right){//分區操作，
var pivotValue=arr[right]//最右面設為標準
var storeIndex=left;
for(var i=left;i<right;i++){
if(arr[i]<=pivotValue){
swap(arr,storeIndex,i);
storeIndex++;
}
}
swap(arr,right,storeIndex);
return storeIndex//返回標桿元素的索引值
}
function sort(arr,left,right){
if(left>right) return;
var storeIndex=partition(arr,left,right);
sort(arr,left,storeIndex-1);
sort(arr,storeIndex+1,right);
}
sort(arr,0,arr.length-1);
return arr;
}
時間復雜度O(nlogn)
算法描述：
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
3. 針對所有的元素重復以上的步驟，除了最后一個。
4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。5.
5 6 3 1 8 7 2 4 [5 6] 3 1 8 7 2 4 //比較5和6 5 [6 3] 1 8 7 2 4 5 3 [6 1] 8 7 2 4 5 3 1 [6 8] 7 2 4 5 3 1 6 [8 7] 2 4 5 3 1 6 7 [8 2] 4 5 3 1 6 7 2 [8 4] 5 3 1 6 7 2 4 8 // 這樣最后一個元素已經在正確位置，所以下一次開始時候就不需要再比較最后一個
編程思路：外循環控制需要比較的元素，比如第一次排序后，最后一個元素就不需要比較了，內循環則負責兩兩元素比較，將元素放到正確位置上
function bubbleSort(arr){
var len=arr.length;
for(var i=len-1;i>0;i--){
for(var j=0;j<i;j++){
if(arr[j]>arr[j+1]){
var tmp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp
}
}
}
return arr;
}
時間復雜度O(n^2)
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
PS：這里再為大家推薦一款關于排序的演示工具供大家參考：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
