sort
kingcwt2023-09-01前端算法 基础数据结构 排序
sort
冒泡排序【bubbleSort】
特点：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
大白话总结
JavaScript 代码
const bubbleSort = (nums) => {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
let temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums;
};
const res = bubbleSort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]);
console.log(res);
Go 代码
package main
import "fmt"
func bubbleSort(nums []int) []int {
numsLen := len(nums)
for i := 0; i < numsLen-1; i++ {
for j := 0; j < numsLen-1-i; j++ {
if nums[j] > nums[j+1] {
temp := nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
}
}
}
return nums
}
func main() {
res := bubbleSort([]int{22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70})
fmt.Printf("%d/n", res)
}
选择排序【selectionSort】
特点：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 重复以上步骤，直到所有元素均排序完毕。
大白话总结 在未排序的数组里面，找到最小的元素，第一次默认把第一个作为最小的元素的索引存下来，一轮下来之后把数组中最小的那个元素的索引找到，然后在当前这一轮结束后，和当前这一轮的索引的值和找到的最小值进行交换位置，以此重复 n-1 轮后，最终排序完成，具体实现看下面代码
JavaScript 代码
const selectionSort = (nums) => {
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
let temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
return nums;
};
console.log(selectionSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 19, 50, 48]));
Go 代码
package main
import "fmt"
func selectionSort(nums []int) []int {
for i := 0; i < len(nums)-1; i++ {
minIndex := i
for j := i + 1; j < len(nums); j++ {
if nums[j] < nums[minIndex] {
minIndex = j
}
}
temp := nums[i]
nums[i] = nums[minIndex]
nums[minIndex] = temp
}
return nums
}
func main() {
res := selectionSort([]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 19, 50, 48})
fmt.Printf("%d\n", res)
}
插入排序【insertionSort】
特点：
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
大白话总结
在遍历时，定义一个初始已排序的索引，默认为第一项，然后把遍历的每一项这个值和前面已经排序的值进行比较，如果前面已经排序的值大于当前项的值，则让已经排序的这一项向后挪一位。直到比较不大于的时候放到已经排序的这个值的后面一位，重复往上步骤。具体代码如下：
JavaScript 代码
const insertionSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let preIndex = i - 1;
let current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
};
console.log(
insertionSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 19, 50, 48]),
"11"
);
Go 代码
package main
import "fmt"
func insertionSort(arr []int) []int {
for i := 1; i < len(arr); i++ {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex--
}
arr[preIndex+1] = current
}
return arr
}
func main() {
res := insertionSort([]int{4, 2, 1, 3})
fmt.Printf("%d\n", res)
}
希尔排序【shellSort】
希尔排序是对插入排序的一种改进，简单来说就是把当前数组按 gap 间隔值，分成若干个子序列，然后对若干个子序列进行插入排序，然后在对 gap 间隔值进行缩减，直到为 1，然后进行插入排序，这个时候元素之前的位置以达到最优，需要注意的是，间隔排序是按 gap 间隔值和当前值减去间隔值进行排序，并不是紧按着的两个元素进行排序，理解上可能有点费劲。耐心看。下面是具体的实现代码和参考的插图，作为理解。
JavaScript 代码
const shellSort = (arr) => {
let len = arr.length;
let gap = Math.floor(len / 2);
while (gap >= 1) {
for (let i = gap; i < len; i++) {
let item = arr[i];
let j = i;
while (arr[j - gap] > item && j > gap - 1) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = item;
}
gap = Math.floor(gap / 2);
}
return arr;
};
let arr = [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15];
console.log(shellSort(arr));
Go 代码
package main
import "fmt"
func shellSort(arr []int) []int {
leg := len(arr)
gap := leg / 2
for gap >= 1 {
for i := gap; i < leg; i++ {
item := arr[i]
j := i
for j > gap-1 && arr[j-gap] > item {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = item
}
gap = gap / 2
}
return arr
}
func main() {
res := shellSort([]int{81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15})
fmt.Println(res)
}
