了解排序算法的原理，还是我辈的基本功，虽然暂时也不用面试，平常工作中也很少用到，但是积累下也总是好的。（默认从小到大排序）
冒泡排序
冒泡排序的基本原理很简单，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。至于为啥叫这个名字呢，是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤：
- 比较相邻的元素，如果顺序不对则交换
- 对每一对相邻的数做同样的工作，不出意外的话，最大的数会”浮“到最后的位置上
- 针对所有元素重复以上步骤，除了最后一个
- 重复步骤1-3，直到排序完成
Python实现1
2
3
4
5
6
7
8
def bubble_sort(arr):
length = len(arr) # 获取数组长度
for i in range(length):
for j in range(1,length-i): # 对所有元素重复执行
if arr[j-1] > arr[j]: # 比较相邻的元素，如果前者比后者大
arr[j],arr[j-1] = arr[j-1],arr[j] # 则交换顺序
return arr
时间复杂度为 O(n^2 ) 的一个算法，不过最好的时间复杂度是 O(n) - 数组已经有序的情况。
选择排序
这是一种特别直观简单的排序方法，即在未排序序列中找到最小的元素放在起始位置，然后从剩下未排序序列中继续找到最小的元素，然后放到已排序序列的末尾。循环直到排序完毕
算法步骤：
- 初始状态，无序区m[0,n-1],有序区n[]
- 第i趟排序，无序区m[i,n-1],有序区n[0,i-1]，则这一趟我们把其中找到的最小的元素与m[i]（无序区的第一个位置）交换
- 循环n-1趟
Python实现1
2
3
4
5
6
7
8
9
10
def select_sort(arr):
n = len(arr)
for i in range(n):
min_index = i # 第i个最小的元素的下标
for j in range(i+1,n):
if arr[j] < arr[min_index]: # 寻找最小的数
min_index = j #保存索引
arr[i],arr[min_index]= arr[min_index],arr[i]
return arr
算法复杂度O(n^2),最好最坏都是，非常稳定。
插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
- 默认第一个元素为已排序
- 取出下一个元素，从后往前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤[2,5]
Python实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def insert_sort(arr):
n = len(arr)
for i in range(1,n): # 默认第一个已经排好序
# 从后往前扫描
if arr[i] < arr[i-1]:
temp = arr[i]
index = i
for j in range(i-1,-1,-1): # range(i,-1,-1) ~ [i,0]
if temp < arr[j]: # 如果该元素大于新元素
arr[j+1] = arr[j] # 则将该元素移到下一位置
index = j # 记录下标
else:
break
arr[index] = temp
return arr
算法时间复杂度O(n^2)
希尔排序
1959年Shell发明，其实质是分组插入排序，也叫缩小增量排序。其工作原理是按一定步长 k0 把长序列划分成若干个子序列，然后分别进行插入排序，接着再按照更长的步长 k1 再度划分子序列并插入排序，直到步长为 kn 为1为止。
1 |
|
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）
快速排序
面试常考题。。
快速排序的基本思想：通过一趟排序把整个待排记录分为两个独立的部分，其中一部分的值都比另一部分小，然后递归地处理各自独立的部分，直到整个序列有序。
算法步骤：
- 从数组中选择一个数作为“基准”（ pivot ）
- 重新排序数列，所有比 pivot 小的数字在前面，比 pivot 大的数字在后面，等于 pivot 则在哪边都可以。
- 递归地（ recursive ）把小于基准值元素的子数列和大于基准值元素的子数列排序
算法实现：1
2
3
4
5
6
7
8
9
def quick_sort(arr):
if len(arr) <= 1: # 递归出口
return arr
else:
pivot = arr[0]
less = [ x for x in arr[1:] if x <= pivot ] # 小于或者等于 pivot 则放在左边
right = [x for x in arr[1:] if x > pivot ] # 大于则放在右边
return quick_sort(less) + [pivot] + quick_sort(right) # 递归调用
算法平均时间复杂度O(nlogn)
归并排序
算法采用分治法：将已有序的子序列合并，得到完全有序的序列。
合并两个有序数组的方法：比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可
基本思路是把数组分为 left 和 right ，如果这两个数组内部是有序的，那我们就可以按照合并两个有序数组的方法来获得一个排序好的数组。现在我们可以对子数组进行二分，直到细到一个元素为一个组为止，这个时候我们可以认为这个组是有序的，然后我们合并相邻数组即可。
算法步骤：
- 把长度为 n 的输入序列切分两个长为 n/2 的子序列
- 分别对子序列采用归并排序
- 将两个已经排序好的子序列合并成一个排序好的输出序列
1 |
|
算法复杂度 O(nlogn)
堆排序
pass
计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法步骤：
- 找出待排序数组中最大和最小的元素
- 统计数组中每个值为 i 的元素出现的次数，存到数组 C 的第 i 项
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组，将每个元素i放在新数组的第 C(i) 项，每放一个元素就将C(i)减去1
权当有趣看看