GitHub：https://github.com/Pgrammerybj （进去的动动小手点个赞哈）
什么是算法？
我们举一个可能不太恰当的例子：
如果将最终写好运行的程序比作战场，我们码农便是指挥作战的将军，而我们所写的代码便是士兵和武器。
那么数据结构和算法是什么？答曰：兵法！
我们可以不看兵法在战场上肉搏，如此，可能会胜利，可能会失败。即使胜利，可能也会付出巨大的代价。我们写程序亦然：没有看过数据结构和算法，有时面对问题可能会没有任何思路，不知如何下手去解决；大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能低下；有时会借助别人开发的利器暂时解决了问题，可是遇到性能瓶颈的时候，又不知该如何进行针对性的优化。
如果我们常看兵法，便可做到胸有成竹，有时会事半功倍！同样，如果我们常看数据结构与算法，我们写程序时也能游刃有余、明察秋毫，遇到问题时亦能入木三分、迎刃而解。
故，数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。
在这里将通过以下几个排序算法来演示：
* 冒泡排序
* 选择排序
* 插入排序
* 希尔排序
* 快速排序
* 归并排序
分类演说
一、冒泡排序
1.冒泡排序算法的运作如下:
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2.交换过程图解:
冒泡排序
3.时间复杂度
- 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
- 最坏时间复杂度：O(n2)
- 稳定性：稳定
4.代码演示：
def bubble_sort1(numList):
"""冒泡排序(正向，从前到后排,时间复杂度O(n2))"""
length = len(numList)
for i in range(0, length - 1):
for j in range(0, length - 1 - i):
if numList[j] > numList[j + 1]:
numList[j], numList[j + 1] = numList[j + 1], numList[j]
def bubble_sort2(numList):
"""冒泡排序(反向，从后往前排，时间复杂度O(n2))"""
length = len(numList)
for i in range(length - 1, 0, -1):
for j in range(i):
if numList[j] > numList[j + 1]:
numList[j], numList[j + 1] = numList[j + 1], numList[j]
def bubble_sort3(numList):
"""冒泡排序(如果给出的列表就是有序的序列，那么可以这样优化,时间复杂度O(n2)，最优为O(n))"""
length = len(numList)
for i in range(length - 1, 0, -1):
is_change = False
for j in range(i):
if numList[j] > numList[j + 1]:
numList[j], numList[j + 1] = numList[j + 1], numList[j]
is_change = True
if not is_change:
return
if __name__ == '__main__':
li = [23, 23, 97, 1, 45, 775, 9, 12]
li2 = [2, 1, 97, 324, 45, 775, 0, 12]
li3 = [1, 2, 3, 4, 5, 6, 7, 8]
li4 = [2, 1, 97, 324, 45, 775, 0, 12]
print("排序前：" + str(li))
bubble_sort1(li)
print("正向排序" + str(li))
print("排序前：" + str(li2))
bubble_sort2(li2)
print("反向排序" + str(li2))
print("排序前：" + str(li3))
bubble_sort3(li3)
print("优化排序" + str(li3))
print("排序前：" + str(li4))
bubble_sort3(li4)
print("优化排序" + str(li4))
二、选择排序
1.选择排序的原理
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素， 然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
2.排序过程图解:
选择排序
3.时间复杂度
- 最优时间复杂度：O(n2)
- 最坏时间复杂度：O(n2)
- 稳定性：不稳定（考虑升序每次选择最大的情况）
4.代码演示：
def select_sort(numList):
length = len(numList)
for i in range(length - 1):
minIndex = i
for j in range(i + 1, length):
if numList[minIndex] > numList[j]:
minIndex = j
numList[i], numList[minIndex] = numList[minIndex], numList[i]
print("排序过程中：" + str(li))
if __name__ == '__main__':
li = [23, 23, 97, 1, 45, 775, 9, 12]
print("排序前：" + str(li))
select_sort(li)
print("排序后：" + str(li)
三、插入排序
1.插入排序算法的运作如下:
它是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.排序过程图解:
插入排序
3.时间复杂度
- 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
- 最坏时间复杂度：O(n2)
- 稳定性：稳定
4.代码演示：
def insert_sort(numList):
length = len(numList)
for i in range(1, length):
# for j in range(0, i):
#
# if numList[i] < numList[j]:
# numList[i], numList[j] = numList[j], numList[i]
for j in range(i, 0, -1):
if numList[j] < numList[j - 1]:
numList[j], numList[j - 1] = numList[j - 1], numList[j]
else:
break
if __name__ == '__main__':
li = [23, 23, 97, 1, 45, 775, 9, 12]
print("插入排序：")
print("排序前：" + str(li))
insert_sort(li)
print("排序后：" + str(li))
四、归并排序
1.归并排序的原理
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
2.排序过程图解
归并排序
3.时间复杂度
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 稳定性：稳定
4.代码演示
def merge_sort(numlist):
# 1.获取到需要排序的队列
length = len(numlist)
# 2.判断列表的长度，如果为1则不需排序直接返回
if length <= 1:
return numlist
# 3.获取中间点，将队列的元素分成两个部分，递归继续拆分
center_point = length // 2
# 拆分的左边的部分
left_list = merge_sort(numlist[:center_point])
# 拆分的右边的部分，继续递归，直至队列的元素为1
right_list = merge_sort(numlist[center_point:])
# 4.初始化两个控制点,和存放排序后的队列
left_point, right_point = 0, 0
result = []
# 5.循环比较左右两侧对应角标的元素大小
while left_point < len(left_list) and right_point < len(right_list):
# 左边的元素和右边的元素相比较，将小的元素添加栋队列中
if left_list[left_point] <= right_list[right_point]:
result.append(left_list[left_point])
left_point += 1
else:
result.append(right_list[right_point])
right_point += 1
# 当退出上面的while循环就说明左侧或者右侧有一方的元素已经全部取完了，此时如果另一方如果还有元素那么就将剩余的元素添加到result中
result += left_list[left_point:]
result += right_list[right_point:]
# 6.返回排序后的队列给用户
return result
if __name__ == '__main__':
num_list = [12, 87, 9, 6, 2, 876, 12, 0, 4]
print("排序前：" + str(num_list))
sortList = merge_sort(num_list)
print("排序后：" + str(sortList))
持续更新....
喜欢的朋友动动小手点个赞咯，我会继续更新相关的内容，还望多多支持。
GitHub：https://github.com/Pgrammerybj （进去的动动小手点个赞哈）
