JavaScript实现七种排序：冒泡、简单选择、快速排序

2021-4-28    前端达人

冒泡

n 次比较相邻两数并交换找到最值，然后 n-1 次比较找到次值……较小的数字像气泡一样浮出。
这里我引入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 次比较相邻两数后最多只交换一次将最值放到位置上，然后 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){ //如果数组只有一个元素 return; } while(l!=r){//两者相遇，意味着一直到找到basic的位置 while(arr[r] > basic && l < r){ //l<r随时注意严格控制哨兵不能错过，从右边向左找第一个比key小的数，找到或者两个哨兵相碰，跳出循环 r--; } while(arr[l] <= basic && l < r){ //这里的=号保证在本轮循环结束前，key的位置不变，否则的话跳出循环，交换l和left的位置的时候，left位置的上元素有可能不是key l++; } //1、两个哨兵到找到了目标值。2、j哨兵找到了目标值。3、两个哨兵都没找到(key是当前数组最小值) 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.lanlanwork.com )是一家专注而深入的界面设计公司，为期望卓越的国内外企业提供卓越的UI界面设计、BS界面设计 、 cs界面设计 、 ipad界面设计 、 包装设计 、 图标定制 、 用户体验 、交互设计、 网站建设 、平面设计服务

« 设计方向和优化方向寻找方法 Java程序的逻辑控制和方法 »

分类

日历

链接

个人资料

蓝蓝设计的小编 http://www.lanlanwork.com

存档