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; 如此往复完成排序;
代码实现:
- const insertSort = function (source) {
- let len = source.length
- let value
- let j
- let i
- for (i = 0; i <len; i++) {
- value = source[i]
- // 已排序部分进行元素的右移一位, 并把目标值 value 插入到对应的位置
- for (j = i -1 ;j> -1 && source[j]> value; j--) {
- source[j+1] = source[j]
- }
- source[j+1] = value
- }
- return source
- }
- console.log(insertSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
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)
- 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]))
来源: http://www.qdfuns.com/article/50472/eaee000f55be6f31e8adc2673e5bfbc8.html