常见的排序算法之JavaScript实现（一）

阳光穿透心脏的1/2处 2023-02-26 14:23 48阅读 0赞

### 目录 ###

*   *   *  1. 冒泡排序
         *  2. 插入排序
         *  3. 选择排序
         *  4. 归并排序
         *  5. 快速排序

最常见的排序算法有以下几种：

*  冒泡排序
 *  插入排序
 *  选择排序
 *  归并排序
 *  快速排序

下面就来看一下每一种排序算法的实现思路。

### 1. 冒泡排序 ###

**实现思路：** 冒泡排序的思路就是重复比较两个相邻的元素，如果两项的大小顺序不对，就进行交换，反之不动。直到所有元素的顺序都正确才结束。  
![在这里插入图片描述][20200716003911461.gif]

**实现：**

但是，上面的实现思路执行效率会很低。因为需要遍历N遍所有的元素，即使还没遍历完就已经排完序，他还会继续执行。我们需要给他设置一个限制条件，来使它只遍历完就停止。

我们可以知道，N轮循环之后，最后N个数一定是想要的顺序，所以，可以控制内层循环的比较次数来体积效率：

**算法分析：**

*  最优的时间复杂度为：O( n )
 *  最差的时间复杂度为：O( n2 )
 *  平均的时间复杂度为：O( n2 )

我们可以看到最优的时间复杂度为O( n ) ，这是情况是数组本身就是有序的情况，上面的代码无法实现，我们需要稍微的改造：

### 2. 插入排序 ###

**实现思路：**

*  从第一个元素开始，将其认作为一个有序的序列
 *  取出下一个元素，与已经排序好的元素序列从后向前扫描
 *  如果该元素小于已经排序好的元素，就将排序好的元素后移
 *  重复上一步，直到找到已经排序好的元素小于等于新元素的位置
 *  将新元素插入到该元素之后
 *  重复上述步骤

![在这里插入图片描述][20200716004021400.gif]  
**实现：**

**算法分析：**

*  最优的时间复杂度为：O( n )
 *  最差的时间复杂度为：O( n2 )
 *  平均的时间复杂度为：O( n2 )

### 3. 选择排序 ###

**实现思路：** 首先在未排序的序列中找到最小（或最大）的元素，并将其放在排序序列的其实位置，然后再在未排序的是序列中查找最小的元素，放在已排序的数组的末尾，重复上述步骤，直到所有元素排序完毕。  
![在这里插入图片描述][20200716005224252.gif]  
**实现：**

**算法分析：**

*  最优的时间复杂度为：O( n2 )
 *  最差的时间复杂度为：O( n2 )
 *  平均的时间复杂度为：O( n2 )

### 4. 归并排序 ###

**实现思路：**

*  将一个长度为n 的数组分割为两个长度为n/2的子序列
 *  将两者子序列继续分割，直至不能分割为止
 *  将相邻的两个元素进行排序，之后将两个相邻子序列排序，直至排序完成

![在这里插入图片描述][20200716150100859.gif]  
**实现：**

function mergeSort(arr){ 
      const len = arr.length
      if(len<=1){ 
        return arr
      }
      const mid = Math.floor(len/2)
      const leftArr = mergeSort(arr.slice(0, mid))
      const rightArr = mergeSort(arr.slice(mid, len))
      return mergeArr(leftArr, rightArr)
    }
    
    function mergeArr(arr1, arr2){ 
      const res = []
      const len1 = arr1.length
      const len2 = arr2.length
      while(len1 > 0 && len2 > 0){ 
        if(arr1[0] <= arr2[0]){ 
           res.push(arr1.shift())
        }else{ 
           res.push(arr2.shift())
        }
      }
      while(len1>0){ 
         res.push(arr1.shift())
      }
      while(len2>0){ 
         res.push(arr2.shift())
      }
      return res
    }

**算法分析：**

*  平均的时间复杂度为：O( nlog(n))

### 5. 快速排序 ###

**实现思路：**

快速排序的基本思想和归并排序一致，也是分治的思想，但是不会真正的切割数组，而是在原有数组内部进行排序。具体的思路如下：

*  在数组中挑出一个元素，作为基准元素
 *  重新排列数组，将所有元素中比基准值小的放在基准值左边，比基准值大的放在基准值的右边
 *  将两侧的元素重复上述步骤，直至排序完成

**实现：**

function quickSort(arr, left, right){ 
      const len = arr.length, 
      let partitionIndex,
      let left = 0, right = len-1
      
      if(left < right){ 
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
      }
      return arr
    }
    // 选取基准值
    function partition(arr, left, right){ 
      let pivotValue = arr[Math.floor(left + (right-left)/2)]
      let i = left
      let j = right
      while(i <= j){ 
        while(arr[i] < pivotValue){ 
          i++
        }
        while(arr[j] > pivotValue){ 
          j--
        }
        if(i <= j){ 
          swap(arr, i, j)
          i++
          j--
        }
      }
      return i
    }
    // 元素交换
    function swap(arr, i, j){ 
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }

**算法分析：**

*  最优的时间复杂度为：O(nlog(n))
 *  最差的时间复杂度为：O( n2 )
 *  平均的时间复杂度为：O(nlog(n))

[20200716003911461.gif]: /images/20230209/25f83c4b3be24c2da95d2760afc2ab95.png
[20200716004021400.gif]: /images/20230209/aeafa758e5f34f61b903f9af8def1561.png
[20200716005224252.gif]: /images/20230209/f2ce411998a34e2dad9ec8f833036bc3.png
[20200716150100859.gif]: /images/20230209/b66ed462d42c4c9d9ab50dab9f2d55b3.png