一、冒泡排序（Bubble Sort）
原理：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。（从头到尾，从尾到头都可以）
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
动画：
冒泡排序.gif
图片说明第一次排序：
冒泡排序.png
图片说明所有排序：
冒泡排序.png
Python实现：
def BubbleSort(matrix):
for i in range(len(matrix) - 1):
for j in range(len(matrix)-i-1):#要用到j+1，防止溢出，减掉1
if matrix[j] > matrix[j + 1]:
matrix[j], matrix[j + 1] = matrix[j + 1], matrix[j]
return matrixB
从左到右找到依次找到较大的元素，如果左边的元素比右边的元素大，交换这两个元素。一共循环了len（matrix）-1次。
优化:
如果一个已经排好的数组，用这个算法还是要比较很多次。
所以增加一个flag，赋值为True，在一次循环中，如果没有两个元素进行交换，说明数组是已经排好序的，在当前循环结束时，flag的值没有发生改变依旧为True，可直接break出循环。
def BubbleSort(matrix):
flag = True
for i in range(len(matrix) - 1):
for j in range(len(matrix) - i - 1):
if matrix[j] > matrix[j + 1]:
matrix[j], matrix[j + 1] = matrix[j + 1], matrix[j]
flag = False
if (flag): break
return matrix
时间复杂度分析：
外层的for时间复杂度为O（n）
里层的时间复杂度分析如下：
因为里层的起点是0，结束是len（matrix）-i-1，（以下用n代替len（matrix））当i == 0 时，里层循环是n-1次，i == 1时，循环为n-1次，当i == n-1时，需要0次。把i为（0，n-1）时所有的循环次数加起来就是从0加到n-1，值为首项加尾项乘以项数除以二，即（0+n-1）n/2，这个的时间复杂度我O（n）。所有里层的循环时间复杂度为O（n）。
所以时间复杂度为O（n^2）
最差情况是需要交换n^2次，最好情况是不需要交换。
空间复杂度：
不需要额外的空间。所以O（1）
稳定性：
冒泡排序是一个稳定的排序方式，比如matrix = [25, 25, 3, 9, 23, 44, 29]时，出现了两个25，在冒泡排序结束后，从左边数的第一个25，在排序结束时，依旧是从左数的第一个25，它不会出现在第二个25的右面。（因为在元素相等的时候没有进行交换）
二、选择排序（Selction Sort）
原理：
第一次循环找出最大值（最小值），记录其下标，把他与最末尾（首）的元素交换，第二次找到第二大的，与倒数第二末尾的元素进行交换。第一次循环的范围是（0，数组长度-1），第二次是（0，数组长度-2）
动画：
选择排序.gif
图片说明：
选择排序.jpg
Python实现：
def SelectionSort(matrix):
n = len(matrix)
for i in range(n):
index = 0
for j in range(n - i):
if matrix[j] > matrix[index]:
index = j
matrix[n - i - 1], matrix[index] = matrix[index], matrix[n - i - 1]
return matrix
时间复杂度分析：
两次for循环：O（n^2），进行了O（n）次交换。
空间复杂度：
不需要额外的空间。所以O（1）
稳定性：
不稳定。
三、插入排序（Insert Sort）
原理：
相当于打牌时候摸牌，如数组[25, 5, 3, 9, 23, 44, 29]，第一张摸到的牌是25，第二张摸到了5，与25比较大小，放在25前面，依次摸完所有的牌，也就排序结束了。
动画：
插入排序.gif
图片说明：
插入排序.jpg
Python实现：
def InsertSort(matrix):
n = len(matrix)
for i in range(1, n):
cur = i
pre = cur - 1
while pre >= 0 and matrix[cur] < matrix[pre]:
if matrix[cur] < matrix[pre]:
matrix[pre], matrix[cur] = matrix[cur], matrix[pre]
cur = pre
pre = cur - 1
return matrix
定义一个cur来存储当前的下标，因为pre是cir-1，所以循环从1开始。
def InsertSort(matrix):
n = len(matrix)
for i in range(1, n):
cur = i
while cur - 1 >= 0 and matrix[cur] < matrix[cur - 1]:
if matrix[cur] < matrix[cur - 1]:
matrix[cur - 1], matrix[cur] = matrix[cur], matrix[cur - 1]
cur -= 1
return matrix
把pre用cur-1代替了。
也可以：
def InsertSort(matrix):
for i in range(1, len(matrix)):
tmp = i
while i > 0:
if matrix[i] < matrix[i - 1]:
matrix[i], matrix[i - 1] = matrix[i - 1], matrix[i]
i -= 1
else:
break
return matrix
时间复杂度分析：
两个嵌套的循环，时间复杂度是O(n^2)。
虽然时间复杂度也是O(n^2)，但是第二层循环不需要与所有元素进行比较，所以在性能上优于冒泡排序和选择排序。
空间复杂度：
没有额外的存储空间，是原地排序算法O（1）。
稳定性：
稳定
四、希尔排序（Shell Sort）
原理：
实际上是插入排序的扩展，把数组分成几组，比如数组[25, 5, 3, 9, 23, 44, 29]，数组长度n为7，取gap = n/2，把数组的[i]和[i+gap]作为一组，比较[i]和[i+gap]的大小，如果[i]>[i+gap]，交换[i]和[i+gap]，如果[i]<[i+gap]，则继续比较[i+1]和[i+gap+1]，把数组里的所有元素都比较完之后，再把gap的值减小，可以减1，也可以把gap/2，继续比较，直至最后一次把数组中的所有元素作为一个整体排序。
动画：
希尔排序.gif
图片说明：
希尔排序.png
Python实现：
def ShellSort(matrix):
n = len(matrix)
gap = n // 2
while gap > 0:
for i in range(gap, n):
for tmp in range(i, gap - 1, -gap):
if matrix[tmp] < matrix[tmp - gap]:
matrix[tmp], matrix[tmp - gap] = matrix[tmp - gap], matrix[tmp]
if gap == 2:
gap = 1
else:
gap //= 2
return matrix
五、计数排序（Count Sort）
使用范围：
数组长度有限，较小。
出现的重复数字比较多，并且这些数值较为集中。
原理：
抽屉原理：遍历数组，把相同的值都放到同一个抽屉中，遍历结束后，按照值从小到大的顺序依次取出，即排列完成。
动画：
计数排序.gif
图片说明：
计数排序.png
Python实现：
def CountSort(matrix):
max = matrix[0]
min = matrix[0]
for i in matrix: #找到list中的最大元素和最小元素
if i > max:
max = i
if i < min:
min = i
tmp = [0] * (max - min + 1) # 定义一个新的数组，长度为最大值减最小值加一
for i in range(len(matrix)): #把原来数组中每个数字出现了多少次存在新数组中
tmp[matrix[i] - min] += 1
index = 0
for j in range(len(tmp)): #
while tmp[j] > 0:
matrix[index] = min + j
index += 1
tmp[j] -= 1
return matrix
时间复杂度分析：
第一个循环：O（n）
第二个循
环：O（n）
第三个循环：O（n），虽然有两个for但是实际上是从头到尾把元素都拿出来，只走了一遍所以时间复杂度还是O（n）
所以时间复杂度为O（n）
稳定性：
不稳定
六、归并排序（Merge Sort）
原理：
把数组从中间分成前后两个数组，再把前后两个数组每个数组再分，分到最小，然后对前后两部分分别排序，再将排好序的两部分合并在一起。
图片说明：
归并排序.jpg
Python实现：
def MergeSort(matrix):
matrix = devide(matrix)
return matrix
def devide(matrix):
if len(matrix) <= 1:
return matrix
m = len(matrix) // 2
a = devide(matrix[:m])
b = devide(matrix[m:])
return merge(a, b)
def merge(num1,num2):
num = []
while len(num1) > 0 and len(num2) > 0:
if num1[0] > num2[0]:
num.append(num2[0])
num2.remove(num2[0])
else:
num.append(num1[0])
num1.remove(num1[0])
if len(num1) == 0:
num += num2
else:
num += num1
return num
时间复杂度：
时间复杂度是 O(nlogn)，要优于 O(n^2)。
空间复杂度：
空间复杂度是 O(n)。
稳定性：
稳定
七、快速排序（Quick Sort）
原理：
数组的一个元素赋给下标赋给first，末尾下标赋给last，把数组从左到右第一个元素的值赋给pivot，从数组末尾往前找到第一个比pivot值小的数，赋给matrix[first]，再从first往后找到第一个比pivot大的值，当first与last相遇时，把pivot的值赋给matrix[first]或matrix[last]，然后递归。
Python实现：
def QuickSort(matrix, i, j):
if i >= j or i < 0 or j > len(matrix)-1:
return
else:
first = i
last = j
pivot = matrix[i]
while first < last:
while first < last and matrix[last] > pivot:
last -= 1
matrix[i] = matrix[last]
while first < last and matrix[first] < pivot:
first += 1
matrix[last] = matrix[first]
matrix[first]= pivot
QuickSort(matrix, i, first - 1)
QuickSort(matrix, first + 1, j)
return matrix
快排参考链接：
https://blog.csdn.net/u010005281/article/details/80084994
文章参考：
硬核！C语言八大排序算法，附动图和详细代码解释！
这或许是东半球分析十大排序算法最好的一篇文章
十大经典排序算法（动图演示）
数据结构与算法系列（五）基于选择的排序算法
网友评论