数据结构排序算法详解
- 1、冒泡排序（Bubble Sort）
- 2、选择排序（Selection Sort）
- 2、插入排序（Insertion Sort）
- 4、快速排序（Quick Sort）
1、冒泡排序（Bubble Sort）
原理：越小的元素会慢慢“浮”到数据序列的顶端，一次比较两个元素，根据比较的大小顺序调换。
算法描述：
- 比较相邻得两个元素，如果前者比后者大，则交换两者得位置
- 对每一对相邻的元素都重复步骤1，一直到最后一对元素对比完，这样序列尾端会选出最大的元素
- 对除了最后一个元素的其他所有的元素重复步骤1，2
- 重复不以上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,2,3…n]
- 第i次循环排序时，已排序列为[1,2,3…i-1]，未排序列[i,i+1…n]，此趟是从无序序列中查找最小（大）目标元素，并该目标元素与无序序列的第一个交换，使得已排序列增加一个生成新的已排序列，未排序列减少一个生成新的无序序列
- 第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）
原理：是通过构建有序序列，对于没有排序的数据，从已经排序好的数据序列中从后往前扫描，直到找到相应的位置插入
算法描述：
- 从第一个元素开始，该元素被认为已排好序
- 取出下一个元素（新元素），从已排好序列数据中从后向前扫描
- 如果该元素（从后向前扫描的已排序数据）大于新元素，则将该元素移到下一个位置
- 重复步骤3（循环），直到找到已排序列中小于或等于新元素的位置
- 将新元素插入该位置
- 重复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）
原理：选择未排序列中得某个元素作为‘基数’，将所有小于‘基数’得元素放到左边，大于‘基数’得元素放到右边，将原序列数据分为左子数组和右子数组，再分别递归左右子数组直到变成有序序列数据
算法图画描述：
- 选择一个基数，默认选择第一个元素作为基数，定义两个指针分别指向数组得头部和尾部
- 移动右指针，从右往左找到第一个小于基数的元素
- 移动左指针，从左往右找到第一个大于基数的元素
- 交换两个元素的位置，使得小于基数的元素在左边，大于基数的元素在右边
- 交换后继续移动右指针寻找小于基数的元素
- 右指针停止后，开始移动左指针寻找大于基数的元素
- 当两个指针重合时停止查找元素，将基数与两个子数组的分界线元素交换
- 查找结束，当前数组满足左子数组 <= 基数 <= 右子数组
代码实现：
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]
}
