前端总结算法之十大排序

一，冒泡排序

1, 相邻之间相比较，左边比右边大的话，交换位置。
2，第一轮下来,已经把最大的值选出来，并排在最后位，这样剩下需排序的的数组减1，依次类推。

function sort(arr) {
    for(let i = 0, l = arr.length - 1; i < l; i++) {
        for(let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
}
let list = [5,4,8,2,1,9,7,3,6]
sort(list)
console.log(list)

二，快速排序

1，找一个基准点(一般是中间数)
2，和基准值比较，比基准值小放leftList，比基准值大放rightList
3，递归执行上述操作，直到arr.length <= 1

function sort(arr) {
    if (arr.length <= 1) return arr
    let midIndex = Math.floor(arr.length/2)
    let midVal = arr[midIndex] // 基准值，一般取中间数
    arr.splice(midIndex, 1)

    let leftList = []
    let rightList = []

    for(let i = 0, l = arr.length; i < l; i++) {
        if (arr[i] < midVal) {
            leftList.push(arr[i])
        } else {
            rightList.push(arr[i])
        }
    }

    return sort(leftList).concat(midVal, sort(rightList))
}

let list = [5,4,8,2,1,9,7,3,6]
let newList = sort(list)
console.log(newList)

三，选择排序

1，找到数组中最小值的索引
2，把最小值排到第一位来。以此类推

function sort(arr) {
    if (arr.length <= 1) return arr

    let minIndex
    for(let i = 0, l = arr.length - 1; i < l; i++) {
        minIndex = i
        for(let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        if (i !== minIndex) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
}

let list = [5,4,8,2,1,9,7,3,6]
sort(list)
console.log(list)

四，插入排序

类似我们打扑克牌，牌从左向右的排序，抽出一张牌插到合适的位置放。
1，抽出位置1的牌，与位置0比较，当位置0的牌比1大时, 先把0的值填入位置1。剩下0位置插入。
2，抽出位置2的牌，与前面位置1比较，当位置1比2大时，先把1的值填入2位置，位置1空出。往下一层比较，找到合适的位置。依次类推。

function sort(arr) {
  let perIndex, current
  for(let i = 1, l = arr.length; i < l; i++) {
    perIndex = i - 1
    current = arr[i] // 抽出的位置值，当前位置为i === perIndex+1
    while(perIndex >= 0 && arr[perIndex] > current){
      arr[perIndex + 1] = arr[perIndex]  // 先把位置1的值填入2位置，空出位置1
      perIndex--  // 往下一层，此时perIndex位置为0，假设arr[0] < current时，循环结束，所以位置1(perIndex+1)的值为current
    }
    arr[perIndex+1] = current
  }
}
let list = [5, 4, 8, 2, 1, 9, 7, 3, 6]
sort(list)
console.log(list)

五，希尔排序

1，按一定的间隔对数组进行分组，一般以数组长度一半 gap = length / 2 (ps:也可以是3,4,无强性要求)
(假如：数组长度为10的话gap = 10 / 2 = 5，也就是，位置0和5为一组，位置1和6位一组...,组里的值进行插入排序)
2，以gap的一半进行缩小 gap = gap / 2
（此时：gap = Math.floor(5 / 2) = 2 向下取整，也就是，位置0和位置2为一组，位置1和3为一组..,组里的值进行插入排序）
3，当gap === 1时，此时所有元素为一组，此时运行的就是我们一般的插入排序了。
这样处理的好处是：希尔排序的优化使得原本 O(n^2) 的时间复杂度一下降为 O(nlogn)

function sort(arr) {
  for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {  // 循环组递减
    // 内循环与插入排序写法一致,只是每次移动的步长为gap
    for(let i = gap; i < arr.length; i++) {
      let temp = arr[i]
      let j = i - gap;  // 例如 gap = 4, 则j = 0, 0 和4位置之间的比较
      for(j; j >= 0 && temp < arr[j]; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
}
let list = [5, 4, 8, 2, 1, 9, 7, 3, 6]
sort(list)
console.log(list)

六，归并排序

采用分治思想
1，先把数组从中间分开，
[5, 4, 8, 2, 1, 9, 7, 3, 6, 0]
[5, 4, 8, 2, 1] [9, 7, 3, 6, 0]
[5, 4, 8] [2, 1] [9, 7, 3] [6, 0]
[5, 4] [8] [2] [1] [9, 7] [3] [6] [0]
[5] [4] [9] [7]
2，分别比较合并
[4, 5]
[4, 5, 8] [1, 2]
[1, 2, 4, 5, 8]
...

function sort(arr) {
  if(arr.length < 2) return arr

  let mid = Math.floor(arr.length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid)
      
  return merge(sort(left), sort(right))
}

function merge(left, right) {
  const result = []
  while(left.length && right.length) {
    if(left[0] <= right[0]){
      result.push(left.shift())  // 相当于result.push(left[0]);left.shift()
    } else {
      result.push(right.shift())
    }
  }
  
  while(left.length) result.push(left.shift())
  while(right.length) result.push(right.shift())

  return result
}
let list = [5, 4, 8, 2, 1, 9, 7, 3, 6, 0]
console.log(sort(list))

七，堆排序

堆排序.gif

1，构建堆，堆顶是最大的元素（子结点的键值或索引总是小于（或者大于）它的父节点）
2，把最大的元素交换到堆顶，然后把堆顶跟交换到数组后面，数组减1，依次重复。

// 构建最大堆
function buildHeap(arr) {
    for(let i = Math.floor(arr.length / 2); i >= 0; i--) {
        adjustHeap(arr, i, arr.length)
    }
}
function adjustHeap(arr, i, len) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i  // 最大值位置

    // 3个节点的交换，找出最大做顶节点
    if (left < len && arr[left] > arr[largest]) {
        largest = left
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right
    }

    // 顶节点发生了变化，交换位置
    if (largest != i) {
        swap(arr, i, largest)
        adjustHeap(arr, largest, len)
    }
}
// 交换位置
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}
// 取值排序
function sort(arr) {
    buildHeap(arr)  // 构建堆
    for(let i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i)  // 堆顶0肯定是最大的元素，先排到后面，然后数组长减1
        adjustHeap(arr, 0, i)  // 数组长减1后，调整堆
    }
}
let list = [5, 4, 8, 2, 1, 9, 7, 3, 6, 0]
sort(list)
console.log(list)

八，桶排序

采用分治思想(ps:把数组分成若干小份，排好每小份，在拼接起来)
1, 定义一个桶的大小（一个桶能装下几个值）
2，根据数组的长度，计算需要几个桶，每个桶都是小的数组，组成二维数组
3，往桶里放数据
4，每个桶的数组使用插入排序
5，把每个桶的数据拼接起来

/*
    arr = 待排序数组
    bucketSize = 桶的大小，bucketSize = 5 一个桶装5个数
*/
function sort(arr, bucketSize = 5) {
    if (arr.length < 2) return arr

    const buckets = createBucket(arr, bucketSize)
    return sortBuckets(buckets)
}
// 划分桶存二维数组
function createBucket(arr, bucketSize) {
    let minValue = arr[0]
    let maxValue = arr[0]
    for(let i = 1; i < arr.length; i++) {
        if (arr[i] < minValue) {
            minValue = arr[i]
        }
        if(arr[i] > maxValue) {
            maxValue = arr[i]
        }
    }
    // 桶个数
    let bucketCount = Math.ceil((maxValue - minValue)/bucketSize)

    // 创建二维数组来存储
    const buckets = []
    for(let i = 0; i <= bucketCount; i++) {
        buckets[i] = []
    }
    // 把数据放进桶
    for(let i = 0, l = arr.length; i < l; i++) {
        let buckerIndex = Math.floor((arr[i] - minValue) / bucketSize)
        buckets[buckerIndex].push(arr[i])
    }
    return buckets
}

function sortBuckets(buckets) {
    let sortArray = []
    for(let i = 0, l = buckets.length; i < l; i++) {
        if (buckets[i] != null) {
            let sorted = inserSort(buckets[i])
            sortArray = [...sortArray, ...sorted]
        }
    }
    return sortArray
}
// 插入排序
function inserSort(arr) {
    if (arr.length < 2) return arr
    for(let i = 0, l = arr.length; i < l; i++) {
        let key = arr[i]
        let j = i - 1
        while (j >=0&&arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}

let list = [5,4,8,2,1,9,7,3,6]
console.log(sort(list))

九，计数排序

1，找出最大和最小元素。
2，统计每个元素出现的次数，以元素的值为索引，次数为value。
3,对所有计数开始累加，从min开始,每一项和前一项相加（加起来最后一个的值是数组的长度,用于下一步值的填充）
4，反向填充目标数组，将每个元素i放在新数组的第C[i]项，每放一个元素，计数-1

function sort(arr) {
    let len = arr.length,
        bucket = [],
        min = arr[0],
        max = arr[0],
        newArr = []

    for(let i = 0; i < len; i++) {
        min = min <= arr[i] ? min : arr[i] // 找出最小值
        max = max >= arr[i] ? max : arr[i] // 找出最大值
        bucket[arr[i]] = bucket[arr[i]] ? bucket[arr[i]]+1 : 1 // 收集值为索引
    }

    // 对所有计数累加
    for(let j = min; j < max; j++) {
        bucket[j + 1] = (bucket[j + 1] || 0) + (bucket[j] || 0)
    }

    for(let k = len - 1; k >= 0; k--) {
        newArr[bucket[arr[k]] - 1] = arr[k]
        bucket[arr[k]]--
    }
// 也可以这样的填充
// for(let k = 0; k <= max; k++) {
//     while (bucket[k]-- > 0) {
//         newArr.push(k)
//     }
// }

    return newArr
}
let list = [2, 2, 3, 8, 7, 1, 2, 7, 3, 9, 8, 1, 4, 2, 4, 6, 9, 2]
console.log(sort(list))

十，基数排序

适用，例如当你的数很大，如手机号码，的排序
1， 先按排序个位数，以各位的值为key, 这个的值为value, 进行按各位的排序
2，排好个位数后，用排好的数组在按十位数排，以十位数的值为key, 这个值为value, 进行按十位的排序，依次类推

/*
    arr = 待排序数组
    max = 最大位数
*/
function sort(arr, max) {
    const buckets = []
    let unit = 10
    let base = 1
    for(let i = 0; i < max; i++, base *= 10, unit *= 10 ){
        //先排好个位，在排十位...
        for(let j = 0; j < arr.length; j++) {
            let index = Math.floor((arr[j]%unit) / base)  // 过滤出个位数，十位数，...

            if (buckets[index] == null) {
                buckets[index] = []
            }
            buckets[index].push(arr[j])
        }
        let pos = 0
        let value
        for(let j = 0, l = buckets.length; j < l; j++) {
            if (buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                    arr[pos++] = value
                }
            }
        }
    }
}

let list = [15,24,38,16,22,15,49,71,43]
sort(list, 2)
console.log(list)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,456评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,370评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,337评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,583评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,596评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,572评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,936评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,595评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,850评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,371评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,951评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2赞 342