JavaScript实现的几种排序

一时失言乱红尘 2022-05-21 02:51 169阅读 0赞

## 1.冒泡排序 ##

原理：冒泡排序的过程就是将数组中相邻的两个元素进行比较，如果前面的元素比后面的元素要大交换位置，否则位置不变；举个栗子：有数组 arr = \[3,5,4,2,1\];  
第一轮循环：3和5比较，3小于5两者位置不变，接下来5和4比较，5大于4，两者交换位置，接着5和2比较，5>2两者交换位置，继续5和1 比较 5>1两者交换位置，一轮后得到的数组是\[3,4,2,1,5\];把大的元素放到数组的最末尾，这种就像水泡样一层一层的像后移动，就是冒泡排序了；  
代码实现：

// 记录循环次数 let count = 0 // 位置交换函数 const change = function (arr, n1, n2) { // 用es6的实现交换 [arr[n1], arr[n2]] = [arr[n2], arr[n1]] //let temp = arr[n1] //arr[n1] = arr[n2] //arr[n2] = temp } // 冒泡排序 const bubbleSort = function (soucre) { let len = soucre.length for (let i = 0;i < len - 1; i++) { for (let j = 0; j < len - 1 - i;j++) { count ++ if (soucre[j] > soucre[j+1]) { change(soucre, j, j+1) } } } return soucre } //验证 console.log(bubbleSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9] console.log(count) // 21

## 2.选择排序 ##

选择排序和冒泡排序类似也是依次对相邻的数进行两两比较。不同之处在于，他不是每次两两相邻比较后交换位置，他是先找出最大（最小）将它放到正确的位置，然后再寻找次最大（最小）放在正确的位置；  
举个栗子：有数组 arr = \[3,5,4,2,1\];  
先假设第一个元素是最小值，并定义一个minidx=0变量记录最小（最大）值的位置，for循环和其他元素进行比较，3和5进行比较，5>3此时不做处理，4也是一样处理，当3和2比较时，3>2，此时将minidx赋值为2的位置，接下来用arr\[minidx\]和剩余的元素比较遇到比他小的就用minidx记录小值的位置；最后将最小的位置值和初始给的值位置进行互换（当然是初始的值和一轮循环下来的minidx位置不一样才互换）；所以一轮循环下来结果是arr = \[1,5,4,2,3\]  
代码实现：

// 记录循环次数 let count = 0 // 选择排序 const selectSort = function (soucre) { let len = soucre.length let minidx; for (let i = 0; i < len; i ++) { minidx = i for (let j = i + 1; j < len; j++) { count ++ if (soucre[minidx] > soucre[j]) { minidx = j } } if (minidx !== i) { change(soucre,i,minidx) } } return soucre } console.log(selectSort([3,6,2,4,9,1,8,23,45,16,14])) // [1, 2, 3, 4, 6, 8, 9, 14, 16, 23, 45] console.log(count) // 55

## 3.插入排序 ##

原理：将数组分为已排序和未排序，将第一个元素看作是已排序的元素，而其他是未排序的，从未排序的里面取出一元素和已排序元素进行比较，并插入到正确位置，这样已排序部分增加一个元素，而未排序的部分减少一个元素。直到排序完成  
举个栗子：有数组 arr = \[1,5,4,2,3\],第一次假设元素1 是已排序部分，5,4,2,3为未排序，取出元素5加入已排序部分，5>1，已排序部分为1,5；而未排序部分为4,2,3；如此往复完成排序；  
代码实现：

## 4.归并排序 ##

原理： 将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成  
代码实现：

const mergeSort = function mergeSort(source) { 
            let len = source.length
            if (len < 2) {
                return source
            }
            let mid = Math.floor(len/2)
            let left = source.slice(0,mid)
            let right = source.slice(mid)
            return merge(mergeSort(left), mergeSort(right))
        }
        function merge(left, right) { 
            let result = []
            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    result.push(left.shift())
                } else {
                    result.push(right.shift())
                }
            }
            while (left.length){
                result.push(left.shift())
            }
            while (right.length){
                result.push(right.shift())
            }
            return result
        }
        console.log(mergeSort([4,8,1,3,5,9,6])) // [1,3,4,5,6,8,9]

## 5.快速排序 ##

原理：快速排序是目前公认的速度快高效的排序方式，时间复杂度O(nlogn)是比较理想的状态，他的实现过程是，先在数组找到一个基点，把大于这个基点的值放到右侧，小于基点的值放到左侧，再将右侧的和左侧的也按照这种方式再次分配，直到完成排序  
举个栗子：有一个数组 arr = \[1,5,4,2,3\];假设我们找数组的中间点作为基点也就是4，那一轮循环后结果就是\[1,2,3,4,5\] ->\_->怎么这么巧，一轮就OK，果然是快速排序，就是快 哈哈，当然程序不会这么做，他是严谨的，他还会去分\[1,2,3\]只是这个实际上已经是排好了的；  
代码实现：粗糙一点的

const quire = function quire(source) {
            if(source.length < 2) return source
            let left = []
            let right = []
            let len = source.length
            let key = source[Math.floor(len/2 -1)]
            for (let i = 0;i<len;i++) {
                if (source[i] < key) {
                    left.push(source[i])
                } else if (source[i] > key){
                    right.push(source[i])
                }
            }
            return [].concat(quire(left),key,quire(right))
        }

上面这种方法缺点就是空间浪费，他会创建很多个left 和 right 这样的数组，造成空间的浪费，当数据量一大的话还是很恐怖的，所以我们要改进的就是，不新建中间数组，而是直接修改位移目标数组；

改进原理: 选取一个基点，从数组的两头两个指针分别向基点位移，位移的原则是，基点的左边的元素如果小于基点，那就像基点位置靠拢以为i++，如果大于基点就原地不动，基点右边的元素反过来，如果大于基点就像基点靠拢一位，j--；如果小于就原地不动；这时再比较两个原地不动的点，如果右边的不动点小于左边的值，叫互换他们的位置；

代码实现：

// 位置交换 const change = function (arr, n1, n2) { // let temp = arr[n1] // arr[n1] = arr[n2] // arr[n2] = temp // 用es6的实现交换 [arr[n1], arr[n2]] = [arr[n2], arr[n1]] } const quiregai = function quiregai(source, start, end) { let pivot = source[Math.floor((start + end)/2)] let i = start // 左边指针初始位置 let j = end // 右边指针初始位置 while(i<=j) { while (source[i] < pivot) { i ++ // 左指针右移 } while (source[j] > pivot) { j -- // 右指针左移 } if (i <= j){ change(source,i,j) // 交换两个位置的值 i++ j-- } } return i // 返回一轮循环后左指针的位置，为下一轮循环初始位置确定 } const quiregaiSort = function quiregaiSort(source, start, end) { if (source.length < 2) return source var start = start || 0 var end = end || source.length - 1 var nextStart = quiregai(source, start, end) // debugger if (start < nextStart -1) { quiregaiSort(source, start, nextStart -1 ) // 上个循环结束的左指针作为左边区块循环的右指针 } if (nextStart < end) { quiregaiSort(source, nextStart, end) // 上个循环结束的左指针作为右边区块循环的左指针 } return source } console.log(quiregaiSort([4,1,9,3,7,5,76,21,12,53,24]))