| 数组6大排序算法 | 您所在的位置：网站首页 › php数字排序从小到大 › 数组6大排序算法 |
数组6大排序算法
|
快速排序
核心算法： 1.取一个基准值（一般是数组中间的元素），遍历数组，比基准值大的放右边，小的放左边，相等的则不动 2.分别创建三个数组来存储元素，最后将三个数组拼接起来 3.循环调用函数，存储相等值的数组不变，其余两个数组作为函数参数 function quicksort(arr) { if (arr.length { if (item === baseValue) { commonArr.push(item) } else if (item > baseValue) { bigArr.push(item) } else { smallArr.push(item) } }) return quicksort(smallArr).concat(commonArr, quicksort(bigArr)) // 也可以写成： // return [...quicksort(smallArr),...commonArr,...quicksort(bigArr)] } 冒泡排序核心算法： 1.循环遍历数组元素 2.挨在一起的两个元素进行比较，大的放后面，这样遍历一次数组后，最大的元素将放在最后面 function bubblesort(arr) { const newArr = [...arr] // i用于控制多少轮 for (let i = 0; i < newArr.length - 1; i++) { for (let j = 0; j < newArr.length - 1 - i; j++) { // 当前值大于后面的值，则对调位置 newArr[j] > newArr[j + 1] && ([newArr[j], newArr[j + 1]] = [newArr[j + 1], newArr[j]]) } } return newArr } 选择排序核心算法： 1.循环遍历每一个元素 2.每次选择一个元素，和后面的元素比较大小，如果后面的元素更小，则交换值。 function selectSort(arr) { // 这层循环用于控制遍历的次数 for (let i = 0; i < arr.length; i++) { // minIndex用来记录最小值所对应的索引 let minIndex = i for (let j = i + 1; j < arr.length; j++) { if (arr[minIndex] > arr[j]) minIndex = j } // 如果找到更小的值，则调换位置 if (minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } return arr } 插入排序 思想一：核心算法（类似于打牌，最终手上的牌按从小到大的顺序排好）： 1.先抽出一张牌放到手上，方便后续比较 2.每次抽出一张牌，都要和手上的牌进行比较，插到合适的位置。 3.如果比手上的某一张牌大，则插入到这张牌的后面；如果比较一轮后，没有找到合适的位置，则说明它是最小的，放到最前面 function insertSort(arr) { let newArr = [] // 手里先拿一张牌 newArr.push(arr[0]) for (let i = 1; i < arr.length; i++) { const A = arr[i] // 抽出一张牌，从大到小和手里的牌进行比较 for (let j = newArr.length - 1; j >= 0; j--) { const B = newArr[j] // 比某一张牌大，则插入到这张牌的后面 if (A >= B) { newArr.splice(j + 1, 0, A) break } // 如果比较一轮后，不满足前面的条件，说明这张牌是最小的，则放到最前面 if (j === 0) newArr.unshift(A) } } return newArr } 思想二：核心算法： 1.默认数组中的第一个元素为有序数组 2.依次遍历无序数组，每次取一个元素和有序数组中所有元素作比较，如果某个元素比它大，则后移一位 function insertSort(arr) { // 认为第一个元素是有序的，所以不用遍历 for (let i = 1; i < arr.length; i++) { let key = arr[i] let j = i - 1 // 拿一个数和有序数组中的所有元素作比较 for (; j >= 0 && arr[j] > key; j--) { // 如果元素比这个数大，则元素向后移动 arr[j+1] = arr[j] } // 这个数被插到合适的位置 arr[j+1] = key } return arr } 希尔排序核心算法（相当于是插入排序的升级版，无非就是在外面多嵌套一层循环）： 1.对相隔一定值的元素进行排序（刚开始一般是数组长度的一半），使数组相对有序 2.后面不断缩小这个值，直到为1（即最后会进行一次插入排序） function shellSort(arr) { let len = arr.length let gap = Math.floor(len / 2) while (gap) { // 假设同组的第一个元素是有序的，遍历无序数组 for (let i = gap; i < len; i++) { let key = arr[i] let j = i - gap // 用无序数组中的第一个元素依次和有序数组作比较 for (; j >= 0 && key < arr[j]; j -= gap) { // 如果比某个元素小，则交换位置 arr[j + gap] = arr[j] } arr[j + gap] = key } gap = Math.floor(gap / 2) } return arr } 归并排序
核心算法： 1.先使用递归将数组划分成一个个长度为1的数组 2.将两个有序的数组合并成一个有序的数组，方法是：依次比较左右两个数组中第一个元素的大小，小的元素放到新数组的末尾，并删除该元素 function mergeSort(arr) { // 将两个有序的数组合并成一个有序的数组 function merge(leftArr, rightArr) { console.log(leftArr, rightArr); let newArr = [] while (leftArr.length && rightArr.length) { // 依次比较左右两个数组中第一个元素的大小，小的元素放到新数组中 if (leftArr[0] > rightArr[0]) { newArr.push(rightArr.shift()) } else { newArr.push(leftArr.shift()) } } return [...newArr, ...leftArr, ...rightArr] } // 数组中只有一个元素，是有序的 if (arr.length === 1) return arr let mid = Math.floor(arr.length / 2) // 将数组一分为二 let leftArr = mergeSort(arr.slice(0, mid)) let rightArr = mergeSort(arr.slice(mid)) return merge(leftArr, rightArr) } |
【本文地址】
公司简介
联系我们