---

title: 排序算法 date: 2019-12-05 15:26:08

tags:

算法和数据结构是相互依存的.

前端的数据结构主要用数组和对象.js 没有指针,无法使用链表.

排序算法

冒泡排序(体育委员两两对比)

时间复杂度：O(n)

需求: 数组 a=[3,2,4,5,1,6]从小到大排列打印出来.

方法: 找出最大的放在最右边,然后排前 5 个.然后依次把最大的放在最右边.

选择排序(体育老师点人)

时间复杂度：O(n)

方法: 选出最小的一个放在最前面.然后看剩下的.

剩下的最小的再放前面.

插入排序(排扑克牌)

时间复杂度：O(n)

声明空数组.取第一张牌,第二个数字和数组中比较,比最后一个大,就放后面,比最后一个小,就往前放.

基数排序(桶排序)(整理扑克牌)

优点：

和计数排序不同的是一个桶里可放多个数字，效率高，计数排序的改良版，时间复杂度：O(N+C)

缺点：

需要 hash 工具，和计数排序不同的是每个桶里都是无序的，还要再排一次序

用途：

高考总分排序，每 100 分放在一个桶里，数字很分散的时候不好用，可用基数排序（比如从几十到几千）

有重复的数.类似于 4 张 1,4 张 2,4 张 3.拿到 1 放到最前面,2 依次,如果还是 1,放在 1 那一摞.每一种放一摞.最后排序.

快排

优点：

效率高,时间复杂度：O(n*log2n)

缺点：

有时候比计数排序慢

挑选一个数,放中间,比它小的放左边,比它大的放右边.它的位置就固定了.

看前面的部分,再挑一个数,比它小的放左边,比它大的放右边.后面的部分,再挑一个数,比它小的放左边,比它大的放右边.又有两个数固定了.