六种方法数组排序
发布时间：2022-10-13 11:01:01 所属栏目：PHP教程 来源：
导读： 请用多种方法解决如下题目：
给出正整数数组 array = [2,1,5,3,8,4,9,5] 请写出一个函数 sort，使得 sort(array) 得到从小到大排好序的数组 [1,2,3,4,5,5,8,9] 新的数组可以是在 array 自身上改的，也可
给出正整数数组 array = [2,1,5,3,8,4,9,5] 请写出一个函数 sort，使得 sort(array) 得到从小到大排好序的数组 [1,2,3,4,5,5,8,9] 新的数组可以是在 array 自身上改的，也可
|
请用多种方法解决如下题目： 给出正整数数组 array = [2,1,5,3,8,4,9,5] 请写出一个函数 sort，使得 sort(array) 得到从小到大排好序的数组 [1,2,3,4,5,5,8,9] 新的数组可以是在 array 自身上改的，也可以是完全新开辟的内存。不得使用 JS 内置的 sort API 答： （1）使用选择排序和循环： let sort = (numbers) => { for(let i=0; i<numbers.length -1; i++){ let index = minIndex(numbers.slice(i))+ i if(index!==i){swap(numbers, index, i) } } return numbers } ? let swap = (array, i ,j) =>{ let temp = array[i] array[i] = array[j] array[j] = temp } let minIndex = (numbers) =>{ let index = 0 for(let i=1; i<numbers.length; i++){ if(numbers[i] < numbers[index]){ index = i } } return index } ? let array = [2,1,5,3,8,4,9,5] sort(array) （2）使用选择排序和递归： let sort = (numbers) => { if(numbers.length >2){ let index = minIndex(numbers) let min = numbers[index] numbers.splice(index, 1) // 从 numbers 里删掉 min return [min].concat(sort(numbers)) }else{ return numbers[0]<numbers[1] ? numbers : numbers.reverse() } } let minIndex = (numbers) => numbers.indexOf(min(numbers)) let min = (numbers) => { if(numbers.length > 2){ return min( [numbers[0], min(numbers.slice(1))] ) }else{ return Math.min.apply(null,numbers) } } ? let array = [2,1,5,3,8,4,9,5] sort(array) （3）快速排序 Quick sort 以某某为基准，小的去前，大的去后。 let sort = 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.push(arr[i]) }else {right.push(arr[i])} } return sort(left).concat( [pivot], sort(right) ) } ? let array = [2,1,5,3,8,4,9,5] sort(array) （4）归并排序 Merge sort 左一半，右一半排好，然后左右合并。 let sort = arr =>{ let k = arr.length if(k===1){return arr} let left = arr.slice(0,Math.floor(k/2)) let right = arr.slice(Math.floor(k/2)) return merge(sort(left),sort(right)) } let merge = (a,b)=>{ if(a.length === 0) return b if(b.length === 0)return a return a[0] > b[0] ? [b[0]].concat(merge(a,b.slice(1))) : [a[0]].concat(merge(a.slice(1), b)) } ? let array = [2,1,5,3,8,4,9,5] sort(array) （5）计数排序 就像整理扑克牌一样，发现一张牌就+1；引入哈希表记录。 let sort = arr =>{ let hashTable = {}, max = 0, result = [] for(let i=0; i<arr.length; i++){ //遍历数组 if(!(arr[i] in hashTable)){ hashTable[arr[i]] = 1 }else{ hashTable[arr[i]] += 1 } if(arr[i] > max) {max = arr[i]} } for(let j=0; j<=max; j++){ // 遍历哈希表 if(j in hashTable){ for(let i=0; i < hashTable[j]; i++){ // 解决出现多次 result.push(j) } } } return result } ? let array = [2,1,5,3,8,4,9,5] sort(array) （6）循环嵌套 sort = arr => { // 外层循环控制用于从头到尾的比较加交换到底有多少轮 for(let i=0;i<arr.length-1;i++){ // 内存循环用来完成每一轮遍历中的重复比较加交换 for(let j=0;j<arr.length-1;j++){ if(arr[j]>arr[j+1]){ // 交换二者 [arr[j], arr[j+1]] = [arr[j+1], arr[j]] } } } // 返回数组 return arr } ? let array = [2,1,5,3,8,4,9,5] sort(array) 当然解决的办法有很多PHP数组排序，能理解这些算法的思想的话，我相信对我们都会有很大的益处。 （编辑：百客网 - 百科网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐