# 面试必考排序算法最详细介绍，包含动画演示、大厂真题（每天一遍，面试必过）

• 前言
• 六大排序算法
• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 总结
• 一图解释所有
• 关于时间复杂度
• 关于稳定性
• 大厂面试真题

## 六大排序算法

### 冒泡排序

``````# 冒泡排序
def bubbleSort(alist):
n = len(alist)
for i in range(n-1, 0, -1):
for j in range(0, i):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
return alist
``````

``````# 冒泡排序
def bubbleSort(alist):
n = len(alist)
exchange = False
for i in range(n-1, 0, -1):
for j in range(0, i):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
exchange = True
# 如果发现整个排序过程中没有交换，提前结束
if not exchange:
break
return alist
``````

### 选择排序

``````# 选择排序
def selectionSort(alist):
n = len(alist)

for i in range(n - 1):
# 寻找[i,n]区间里的最小值
min_index = i
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
alist[i], alist[min_index] = alist[min_index], alist[i]
return alist
``````

### 插入排序

``````# 插入排序
def insertionSort(alist):
for i in range(1,len(alist)):
currentvalue=alist[i]
position=i
while alist[position-1]>currentvalue and position>0:
alist[position]=alist[position-1]
position=position-1
alist[position]=currentvalue
return alist
``````

``````   # 插入排序
def insertionSort(blist):
n = len(blist)
for i in range(1, n):
# 寻找a[i]合适的插入位置
temp = blist[i]
for j in range(i, 0, -1):
if (temp < blist[j-1]):
blist[j] = blist[j-1]
else:
break
blist[j-1] = temp
return blist
``````

``````for j in range(i, 0, -1):
``````

### 希尔排序

``````# 希尔排序
def shellSort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap):
gapInsetionSort(alist, i, gap)
gap = gap // 2
return alist

# # start子数列开始的起始位置， gap表示间隔

def gapInsetionSort(alist,startpos,gap):
#希尔排序的辅助函数
for i in range(startpos+gap,len(alist),gap):
position=i
currentvalue=alist[i]

while position>startpos and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position=position-gap
alist[position]=currentvalue
``````

### 归并排序

``````# 归并排序
def mergeSort(alist):
n = len(alist)
__mergeSort(alist, 0, n-1)
return alist

# 对arr[l...r]的范围进行排序
def __mergeSort(alist, start, end):
#当数列的大小比较小的时候，数列近乎有序的概率较大
if (end-start <= 15):
insertionSortHelp(alist, start, end)
return

if start >= end:
return
# 存在风险，start+end可能越界
mid = (start + end) // 2
# mid = start + (end - start) // 2
__mergeSort(alist, start, mid)
__mergeSort(alist, mid + 1, end)
#优化
if alist[mid] > alist[mid+1]:
merge(alist, start, mid, end)

# 合并有序数列alist[start....mid] 和 alist[mid+1...end]，使之成为有序数列
def merge(alist, start, mid, end):
# 复制一份
blist = alist[start:end+1]
l = start
k = mid + 1
pos = start

while pos <= end:
if (l > mid):
alist[pos] = blist[k-start]
k += 1
elif (k > end):
alist[pos] = blist[l-start]
l += 1
elif blist[l-start] <= blist[k-start]:
alist[pos] = blist[l-start]
l += 1
else:
alist[pos] = blist[k-start]
k += 1
pos += 1

def insertionSortHelp(alist,l, r):
for i in range(l+1,r+1):
currentvalue=alist[i]
position=i
while alist[position-1]>currentvalue and position>l:
alist[position]=alist[position-1]
position=position-1
alist[position]=currentvalue
return alist
``````

``````# 自底向上的归并算法
def mergeBU(alist):
n = len(alist)
#表示归并的大小
size = 1
while size <= n:
for i in range(0, n-size, size+size):
merge(alist, i, i+size-1, min(i+size+size-1, n-1))
size += size
return alist

# 合并有序数列alist[start....mid] 和 alist[mid+1...end]，使之成为有序数列
def merge(alist, start, mid, end):
# 复制一份
blist = alist[start:end+1]
l = start
k = mid + 1
pos = start

while pos <= end:
if (l > mid):
alist[pos] = blist[k-start]
k += 1
elif (k > end):
alist[pos] = blist[l-start]
l += 1
elif blist[l-start] <= blist[k-start]:
alist[pos] = blist[l-start]
l += 1
else:
alist[pos] = blist[k-start]
k += 1
pos += 1
``````

### 快速排序

• 从数列中挑出一个元素，称为"基准"（pivot）。
• 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
• 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

``````def __quickSort(alist, l, r):

#当数列的大小比较小的时候，数列近乎有序的概率较大
# if (r - l <= 15):
#     insertionSortHelp(alist, l, r)
#     return

if l >= r:
return
# p = partition(alist, l, r)
p = partitionQS(alist, l, r)

__quickSort(alist, l, p-1)
__quickSort(alist, p+1, r)

# 在alist[l...r]中寻找j,使得alist[l...j] <= alist[l], alist[j+1...r] >alist[l]
def partition(alist, l, r):
pos = randint(l, r)
alist[pos], alist[l] = alist[l], alist[pos]
v = alist[l]
# v = alist[l]
j = l
i = l + 1
while i <= r:
if alist[i] <= v:
alist[j+1],alist[i] = alist[i],alist[j+1]
j += 1
i += 1
alist[l], alist[j] = alist[j], alist[l]
return j
``````

• 当数列近乎有序的时，由于每次选取的都是第一个数，所以造成数列分割的极其不等，此时快排蜕化成 的算法， 此时只要随机选取基准点即可
• 当数列中包含大量的重复元素的时候，这一版的代码也会造成"分割不等“的问题，此时需要将重复元素均匀的分散的自数列旁
• 使用三路快排

## 总结

### 关于时间复杂度

• 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
• 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
• O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
• 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

### 关于稳定性

• 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
• 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

## 大厂面试真题

• 【途虎养车2021秋招Java笔试试卷A】 合并两个有序数组
• 【贝壳找房2021届校招移动端类试卷】 赛季总排名
• 【【2021】小米秋招软】 选择排序
• 【2021届阅文测试开发方向笔试卷】 合并两个排序的链表
• 【2021届阅文测试开发方向笔试卷】 挑选top10元素
• 【2021届阅文大数据方向笔试卷】 快速排序
• 【2021届阅文大数据方向笔试卷】 冒泡排序
• 【2021届阅文PHP方向笔试卷】 实现快速排序
• 【2021届阅文Java方向笔试卷】 数据多项排序
• 【2021届阅文Java方向笔试卷】 对MAP进行排序
• 【2021届阅文Java方向笔试卷】 计算参数的hash值
• 【2021届阅文C方向笔试卷】 对struct进行排序
• 【金山办公2020校招计算机视觉算法工程师笔试题（二）】 排序算法效率对比
• 【金山办公2020校招自然语言处理NLP工程师笔试题（一）】 排列顺序对算法的性能
• 【格力2020秋招后端岗笔试题】 冒泡排序原理
• 【声网2020校招-通用C++笔试题】 根据程序判断排序算法
• 【乐信2020校园招聘数据笔试题】 排序算法时间复杂度
• 【顺丰科技2019秋招安卓开发工程师笔试客观题合集】 排序算法时间复杂度
• 【顺丰科技2019秋招安卓开发工程师笔试客观题合集】 排序算法对比
• 【顺丰科技2019秋招前端开发工程师客观题合集】 快速排序原理
• 【顺丰科技2019秋招前端开发工程师客观题合集】 排序算法原理
• 【顺丰科技2019秋招人工智能与机器学习工程师笔试客观题合集】 排序算法时间复杂度
• 【小米2019秋招运维工程师笔试题（B）】 基数排序
• 【小米2019秋招系统软件开发笔试题（A）】 排序算法时间复杂度
• 【小米2019秋招系统软件开发笔试题（A）】 快速排序
• 【小米2019秋招算法笔试题（B）】 厨艺大赛奖金
• 【小米2019秋招算法笔试题（A）】 排序算法时间复杂度
• 【小米2019秋招安卓开发笔试题（A）】 选择排序
• 【小米2019秋招安全开发笔试题（A）】 比赛名次
• 【小米2019秋招前端开发笔试题（B）】 排序算法稳定性
• 【小米2019秋招前端开发笔试题（B）】 排序算法稳定性
• 【小米2019秋招前端开发笔试题（B）】 选择排序
• 【寒武纪2019秋招软件】 排序算法稳定性
• 【寒武纪2019秋招软件】 冒泡排序
• 【唯品会2019秋招算法类】 排序算法原理
• 【唯品会2019秋招算法类】 排序算法实现
• 【哔哩哔哩2019秋招技术岗（前端、运维、后端、移动端）第三套笔试题】 排序算法原理
• 【哔哩哔哩2019秋招技术岗（前端、运维、后端、移动端）第三套笔试题】 归并排序
• 【哔哩哔哩2019秋招技术岗（前端、运维、后端、移动端）第一套笔试题】 排序算法时间复杂度
• 【哔哩哔哩2019秋招技术岗（前端、运维、后端、移动端）第一套笔试题】 冒泡排序
• 【vivo2019校招图像算法工程师笔试题】 快速排序
• 【vivo2019校招图像算法工程师笔试题】 快速排序
• 【360公司-2019校招笔试-测试开发工程师客观题合集】 插入排序
• 【360公司-2019校招笔试-测试开发工程师客观题合集】 归并排序
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 排序算法原理
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 选择排序
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 排序算法时间复杂度
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 归并排序
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 快速排序
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 插入排序
• 【360公司-2019校招笔试-机器学习工程师客观题合集】 归并排序
• 【2019校园招聘算法工程师笔试题】 排序算法时间复杂度
• 【2019校园招聘前端开发工程师笔试题】 冒泡排序
• 【爱奇艺2018秋季校招算法工程师（第三场）】 冒泡排序
• 【爱奇艺2018秋季校招iOS工程师（第三场）】 排序算法时间复杂度
• 【爱奇艺2018秋季校招Android工程师（第一场）】 选择排序
• 【搜狐畅游2018游戏开】 排序算法实现
• 【搜狐畅游2018游戏开】 冒泡排序
• 【帆软软件2018届秋招笔试题-研发岗位】 排序算法时间复杂度
• 【唯品会2018校招机器学习、算法笔试题（B卷）】 排序算法实现
• 【唯品会2018校招数据结构笔试题（A卷）】 快速排序
• 【唯品会2018校招数据挖掘、机器学习笔试题（A卷）】 排序算法实现
• 【唯品会2018校招前端、java、运维、测试、数据库笔试题（B卷）】 排序算法原理
• 【唯品会2018校招前端、java、运维、测试、数据库笔试题（B卷）】 快速排序
• 【vivo2018秋招软件开发笔试题】 冒泡排序
• 【360公司-2018春招笔试-测试开发工程师客观题合集】 选择排序
• 【360公司-2018春招笔试-测试开发工程师客观题合集】 排序算法原理
• 【360公司-2018春招笔试-Java开发工程师客观题合集】 排序算法原理
• 【360公司-2018春招笔试-Java开发工程师客观题合集】 冒泡排序
• 【2018迅雷校园招聘AI工程师在线笔试A卷】 排序算法时间复杂度
• 【爱奇艺2017秋招c++开发工程师笔试卷】 排序算法稳定性
• 【搜狗2017校招C++工程师笔试试卷】 排序算法稳定性
• 【德邦2017秋招java工程师笔试试卷】 选择排序
• 【字节跳动2017前端工程师实习生笔试题】 排序算法稳定性
• 【同程2017校招前端工程师笔试试卷】 归并排序
• 【凹凸科技2017秋招java工程师笔试卷】 堆排序