JavaScript實現(xiàn)七種排序:冒泡、簡單選擇、快速排序

2021-4-28    前端達人

冒泡

n 次比較相鄰兩數(shù)并交換找到最值,然后 n-1 次比較找到次值……較小的數(shù)字像氣泡一樣浮出。
這里我引入flag排除,已經有序卻一直遍歷

function bubbleSort(arr){ const n=arr.length; let flag=1,i,j; for(i=0;i<n-1&&flag;i++){ //最壞的情況需要依次比較出最小值、次小值、次次小值 flag=0;//如果交換了就變 for(j=0;j<n-i-1;j++){ if(arr[j]>arr[j+1]){ const swap=arr[j]; arr[j]=arr[j+1]; arr[j+1]=swap; flag=1; } } } return arr; } 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

簡單選擇排序

和冒泡原理相似,但是少了很多交換,多了一個暫存最值的空間。
n 次比較相鄰兩數(shù)后最多只交換一次將最值放到位置上,然后 n-1 次比較找到次值
冒泡更適合基本有序的序列

function selectSort(arr) { const n=arr.length; let i,j,minIndex; for(i=0;i<n-1;i++){ minIndex=i;//先決定誰最小 for(j=i+1;j<n;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } if(minIndex!=i){ const swap=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=swap; } } return arr; } 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

快速排序

平均時間復雜度=O(n logn)

在這里插入圖片描述

function quick_part(arr,left,right){ //留下left和right后面遞歸 var l = left; var r = right; var basic= arr[left]; //arr[left]即basic的原位置 if(left >= right){ //如果數(shù)組只有一個元素 return; } while(l!=r){//兩者相遇,意味著一直到找到basic的位置 while(arr[r] > basic && l < r){ //l<r隨時注意嚴格控制哨兵不能錯過,從右邊向左找第一個比key小的數(shù),找到或者兩個哨兵相碰,跳出循環(huán) r--; } while(arr[l] <= basic && l < r){ //這里的=號保證在本輪循環(huán)結束前,key的位置不變,否則的話跳出循環(huán),交換l和left的位置的時候,left位置的上元素有可能不是key l++; } //1、兩個哨兵到找到了目標值。2、j哨兵找到了目標值。3、兩個哨兵都沒找到(key是當前數(shù)組最小值) if(l!=r){ //交換兩個元素的位置 const swap = arr[l]; arr[l] = arr[r]; arr[r] = swap; } } arr[left] = arr[l] //arr[left]即basic的原位置 arr[l] = basic; quick_part(arr,left,l-1); quick_part(arr,l+1,right); } function quickSort(arr){ quick_part(arr,0,arr.length-1); }



    

轉自:csdn 作者:tututu333


藍藍設計www.yvirxh.cn )是一家專注而深入的界面設計公司,為期望卓越的國內外企業(yè)提供卓越的UI界面設計、BS界面設計 、 cs界面設計 、 ipad界面設計 、 包裝設計 、 圖標定制 、 用戶體驗 、交互設計、 網站建設 平面設計服務


日歷

鏈接

個人資料

藍藍設計的小編 http://www.yvirxh.cn

存檔