排序算法
nothing-sy2023-11-14算法 排序算法
选择排序
思路
- 初始状态下，所有元素未排序，即未排序（索引）区间为 [0,n-1]。
- 选取区间 [0,n-1]中的最小元素，将其与索引 0处元素交换。完成后，数组前 1 个元素已排序。
- 选取区间 [1,n-1]中的最小元素，将其与索引 1 处元素交换。完成后，数组前 2 个元素已排序。
- 以此类推。经过 n-1 轮选择与交换后，数组前 n-1 个元素已排序。
- 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
记住选择排序只有在选择区间找到最小值以后才会置换元素（即在外层循环置换），而不是每次内循环都置换
代码实现
/* 选择排序 */
function selectionSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
const sortedArr = selectionSort(arr);
console.log("排序后的数组：", sortedArr);
冒泡排序
思路
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
插入排序
思路（类似于抽牌然后插入到已经有序的牌中）
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置（这个内循环类似冒泡，只不过被插入的元素不参与位置替换，而是把大于被插入元素的数往后移动、冒泡）
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
代码实现
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j]; //当前要排序的temp已经存储，将已排序区域大于temp的数往后排
j--;
}
arr[j + 1] = temp;//最终不符合内循环条件后的j+1位置就是temp的插入位置（比temp大的数据已经都往后移动了1位，并占据了temp原有的索引位置）
}
return arr;
}
快速排序
思路
- 从数列中挑出一个元素，称为“基准”（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的元素可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 递归到最底部时，数列仅有一个元素，该元素就是有序的。
代码实现
TIP
下面的代码由codegeex AI提供，借助了额外的数组以简化快排的复杂程度。
// 写一个快速排序方法
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2); // 找到基准数
let pivot = arr.splice(pivotIndex, 1)[0]; // 删除基准数，并获取
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) { // 比基准数小的放在left数组
left.push(arr[i]);
} else { // 比基准数大的放在right数组
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right)); // 递归调用
}
TIP
以下是较复杂的写法，但是节省额外空间
//交换函数
function swap(nums,left,right){
let temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
function quickSort(nums,left,right){
// 子数组长度为 1 时终止递归
if (left >= right) return;
let i = left,j = right;
while(i < j){
//下面>=nums[left]是以最左侧元素为基准值，（不可以以中间元素为基准值，因为当i,j相遇的时候无法保证是在基准值左边还是右边，交换基准位置就变成了无序）
while(i < j && nums[j] >= nums[left]) {//必须加上i < j条件，如果一直找不到比基准值更小，则i,j相遇，后面的while循环不会执行，此时交换i,j其实是同一个元素交换。最终交换基准值和i,j交界索引
j-=1
}
while(i < j && nums[i] <= nums[left]) {
i+=1
}
swap(nums,i,j)
}
swap(nums,left,i)
quickSort(nums,left,i-1)
quickSort(nums,i+1,right)
return nums
}
const arr = [1,7,2,5,2,9,88]
console.log(quickSort(arr,0,arr.length-1))
归并排序
思路
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的递归思想，先递归分解数组，再合并数组。
代码实现
function mergeSort(arrs){
if(arrs.length === 1){
return arrs
}
let mid = Math.floor((arrs.length - 1)/2);
let left = arrs.slice(0,mid+1);
let right = arrs.slice(mid+1);
return sort(mergeSort(left),mergeSort(right))
}
function sort(left,right){
let res = [];
let l = 0,r = 0
while(l<left.length&& r < right.length) {
if(left[l] < right[r]){
res.push(left[l])
l++
} else {
res.push(right[r])
r++
}
}
if(l<left.length){
res.push(...left.slice(l))
} else {
res.push(...right.slice(r))
}
return res
}
var arr = [1,2,8,4,2,3,6,99,5,24,56]
var r= mergeSort(arr)
console.log(r)