数据结构排序算法详解

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]=5arr[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解释