JavaScript ——十大经典排序算法汇总(整理中）

àì夳堔傛蜴生んèń 2022-11-03 04:21 188阅读 0赞

# 冒泡排序（Bubble Sort） #

冒泡排序是一次比较两个元素，如果顺序是错误的就把它们交换过来。走访数列的工作会重复地进行，直到不需要再交换，也就是说该数列已经排序完成。

// 冒泡排序（已优化）
    const bubbleSorted2 = arr=>{ 
        const length = arr.length
        if(length <=1){ 
            return
        }
        for (let i = 0;i<length-1;i++){ 
            let hasChange = false
            for (let j = 0 ;j<length - i-1;j++){ 
                if(arr[j]>arr[j+1]){ 
                    const temp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = temp
                    hasChange = true 
                }
            }
            if(!hasChange){ 
                break
            }
        }
        console.log(arr)
    }
    console.log("排序前：2,5,44,22,58,40,34,54,89")
    bubbleSorted2([2,5,44,22,58,40,34,54,89])

# 插入排序（Insertion Sort） #

插入排序算法描述的是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果。

![在这里插入图片描述][20210226193927660.gif_pic_center]

# 选择排序（Selection Sort） #

选择排序是一种简单直观的排序算法。它的工作原理是，首先将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕。

# 归并排序（Merge Sort） #

将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

# 快速排序 （Quick Sort） #

快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]

// 快速排序
    const quickSort = (arr, left, right) => { 
      let len = arr.length,
          partitionIndex;
      left = typeof left != 'number' ? 0 : left;
      right = typeof right != 'number' ? len - 1 : right;
    
      if (left < right) { 
          partitionIndex = partition(arr, left, right);
          console.log("partitionIndex-----'基准下标'---"+partitionIndex)
          quickSort(arr, left, partitionIndex - 1);
          quickSort(arr, partitionIndex + 1, right);
      }
      return arr;
    };
    
    const partition = (arr, left, right) => { 
      //分区操作
      let pivot = left, //设定基准值（pivot）
          index = pivot + 1;
      for (let i = index; i <= right; i++) { 
          if (arr[i] < arr[pivot]) { 
              swap(arr, i, index);
              index++;
          }
      }
      console.log("又开始分区-----")
      console.log("left--"+left+"-----基准是-----"+arr[pivot])
      console.log('right---'+right+"----right是-----"+arr[right])
      swap(arr, pivot, index - 1);
      
      console.log("分区完--"+arr)
      return index - 1;
    };
    
    const swap = (arr, i, j) => { 
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    };
    console.log("[11,8,3,9,7,1,2,5]")
    quickSort([11,8,3,9,7,1,2,5])

## 归并排序（Merge Sort）与快速排序的区别 ##

*  归并排序的处理过程是由下而上的，先处理子问题，然后再合并。
 *  快排正好相反，它的处理过程是由上而下的，先分区，然后再处理子问题。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]  
[参考大佬][Link 1]

[20210226193927660.gif_pic_center]: /images/20221024/4ce90dc3d6f3401cb6e30a8d452de06b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221024/386bcfb151aa4d6c84a45a18ae9895e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: /images/20221024/40dcfbe1aeb449568eebf604e5bd5a63.png
[Link 1]: https://biaochenxuying.cn/articleDetail?article_id=5d4059b896cf541789792485