数据结构排序算法详解

1、冒泡排序（Bubble Sort）

原理：越小的元素会慢慢“浮”到数据序列的顶端，一次比较两个元素，根据比较的大小顺序调换。
算法描述：

1. 比较相邻得两个元素，如果前者比后者大，则交换两者得位置
2. 对每一对相邻的元素都重复步骤1，一直到最后一对元素对比完，这样序列尾端会选出最大的元素
3. 对除了最后一个元素的其他所有的元素重复步骤1，2
4. 重复不以上3个步骤，直到数据序列变成有序
   动图描述：
   
   代码实现：

 // 冒泡排序
    BubbleSort(arr) {
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) { //相邻的元素进行比较
            let temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }
      return arr;
    },

2、选择排序（Selection Sort）

原理：首先在未排序序列中找到最小（大）元素，将其放到序列的起始位置，之后继续在剩下未排序序列中查找最小（大）元素，然后将其放到序列的起始位置，重复此操作直到所有元素都排序完毕
算法描述：

1. 初始时已排序列为空，无序序列为[1,2,3…n]
2. 第i次循环排序时，已排序列为[1,2,3…i-1]，未排序列[i,i+1…n]，此趟是从无序序列中查找最小（大）目标元素，并该目标元素与无序序列的第一个交换，使得已排序列增加一个生成新的已排序列，未排序列减少一个生成新的无序序列
3. 第n-1次循环结束，序列变成有序序列
   动图演示：
   
   代码演示

 // 选择排序 例如：[10,7,11,16,5,]
    SelectionSort(arr) {
      let len = arr.length;
      let minIndex, temp;
      for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < arr[minIndex]) {
            minIndex = j; // 下标为4值最小  minIndex = 4
          }
        }
        temp = arr[minIndex]; //temp =arr[4]=5 arr[4]= arr[0]=10  arr[0]=5
        arr[minIndex] = arr[i];
        arr[i] = temp;
      }
      console.log(arr);
      return arr;
    },

2、插入排序（Insertion Sort）

原理：是通过构建有序序列，对于没有排序的数据，从已经排序好的数据序列中从后往前扫描，直到找到相应的位置插入

算法描述：

1. 从第一个元素开始，该元素被认为已排好序
2. 取出下一个元素（新元素），从已排好序列数据中从后向前扫描
3. 如果该元素（从后向前扫描的已排序数据）大于新元素，则将该元素移到下一个位置
4. 重复步骤3（循环），直到找到已排序列中小于或等于新元素的位置
5. 将新元素插入该位置
6. 重复2-5步骤
   动图演示：
   
   代码实现：

 insertionSort(arr) {
      for (let i = 1; i < arr.length; i++) {
        let current = arr[i]; // 当前要插入的元素
        let preIndex = i - 1; // 已排序部分的最后一个索引
        // 将已排序部分中大于 current 的元素向右移动
        while (preIndex >= 0 && arr[preIndex] > current) {
          arr[preIndex + 1] = arr[preIndex];
          preIndex = preIndex - 1;
        }
        arr[preIndex + 1] = current; // 将 current 放到正确的位置
      }
      return arr;
    },

代码运行简单解释，例如arr=[12, 11, 13, 5, 6]
i=1时，是前两个元素进行比较，为了更明显从i=2解释

4、快速排序（Quick Sort）

原理：选择未排序列中得某个元素作为‘基数’，将所有小于‘基数’得元素放到左边，大于‘基数’得元素放到右边，将原序列数据分为左子数组和右子数组，再分别递归左右子数组直到变成有序序列数据

算法图画描述：

1. 选择一个基数，默认选择第一个元素作为基数，定义两个指针分别指向数组得头部和尾部
2. 移动右指针，从右往左找到第一个小于基数的元素
3. 移动左指针，从左往右找到第一个大于基数的元素
4. 交换两个元素的位置，使得小于基数的元素在左边，大于基数的元素在右边
5. 交换后继续移动右指针寻找小于基数的元素
6. 右指针停止后，开始移动左指针寻找大于基数的元素
7. 当两个指针重合时停止查找元素，将基数与两个子数组的分界线元素交换
8. 查找结束，当前数组满足左子数组 <= 基数 <= 右子数组

代码实现：

 	quickSort(arr, begin, end) {
      if (begin >= end) return;
      const part = this.partitionData(arr, begin, end);
      this.quickSort(arr, begin, part - 1); //重新排列左子数组
      this.quickSort(arr, part + 1, end); //重新排列右子数组
      return arr;
    },
    //数组分割排序
    partitionData(arr, begin, end) {
      let key = begin; //默认将第一个元素设置为基数
      let left = begin;
      let right = end;
      while (left < right) {
        while (left < right && arr[right] >= arr[key]) right--; //右指针从右往左查找比基数小的元素
        while (left < right && arr[left] <= arr[key]) left++;
        // 左指针找到比基数大的元素 与 右指针找到比基数小的元素 互相交换
        this.swapData(arr, right, left);
      }
      // 左右指针重合时，将基数与分界线元素交换
      this.swapData(arr, key, left);
      return left;
    },

    // 交换两个元素
    swapData(arr, right, left) {
      const temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
    },
    
    //快排函数调用
	useSort(){
    	const arr = [10, 6, 7, 11, 8, 12, 5, 9, 4];
   	 	const _arr = this.quickSort(arr, 0, arr.length - 1);
    	console.log(_arr); //[4, 5, 6, 7, 8, 9, 10, 11, 12]
	}