一、排序简介
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
稳定性：冒泡直接归并。
二、冒泡排序
参考冒泡排序
冒泡排序算法的运作如下：
- 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
对于图片上的直观理解，建议看冒泡排序中代码后面的图片。
需要注意的地方：
- 1、因为是需要比较两个元素，所以在索引时用到了alist[i+1]的情况，因此在为了不让index超出范围，应该让for循环中的passnum-1。
- 2、每一次循环，最大的元素都已经排到列表最后了，下一次循环就可以减短列表长度了，因此在循环结束以后需要加上passnum -= 1。
代码实现：
def bubbleSort(alist):
#构造一个倒序列表，从而限制了每次遍历一次以后的循环长度
passnum = len(alist)
while passnum > 0:
for i in range(passnum-1):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum -= 1
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
三、选择排序
选择排序也是一种简单直观的排序算法。（以从小到大的排序为例。）
1、初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；
2、然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
具体操作图片见 选择排序
选择排序与冒泡排序的区别：
- 冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小元素放到合适的位置
- 选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
由于选择排序需要记住的是当前最大元素的位置，因此需要设置一个index_max的变量并令初始值为0 ，接下来就要比较每个元素，循环一次，就能得到最大值的index了。
接下来就是交换元素的操作。
另外，这里的for循环中passnum应该保持不变。
代码实现：
def selectionSort(alist):
#构造一个倒序列表，从而限制了每次遍历一次以后的循环长度
passnum = len(alist)
while passnum > 0:
index_max = 0
for i in range(passnum):
if alist[i]>alist[index_max]:
index_max = i
temp = alist[passnum-1]
alist[passnum-1] = alist[index_max]
alist[index_max] = temp
passnum -= 1
alist = [54,26,93,17,77,31,44,55,20]
selectSort(alist)
print(alist)
四、插入排序
插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。
如下图：
对于一个列表[5,4,2,10,7],在用插入排序到达[2,4,5,10,7]的结果时，对于最后一个元素7，从后向前进行比较，比10小，就与10交换位置，直到前面一位的元素比7小为止。
注意，在从后向前扫描的过程中，需要不断地交换两个元素的位置。
从图像上直观理解插入排序
伪代码：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
代码：
按照伪代码，此处需要加两个循环：
- 1、一个是for循环，按照插入排序的思想，需要对列表中每个元素执行一次插入操作，从左到右。
- 2、一个是while循环，执行比较与换位操作。
若是前一个元素nums[cur-1]大于当前元素nums[cur]，则二者互换位置
1、while循环结束条件：
当cur指向的元素为0即列表开头时，停止循环
当cur元素小于等于第cur-1的元素时，目的已经达到，执行break语句。
2、while循环改变语句：
每循环一次，cur指针就要减1，与前面的前面的元素进行比较
代码实现：
def Insertionsort(nums):
for i in range(len(nums)):
cur = i
while cur >= 1:
if nums[cur-1] > nums[cur]:
temp = nums[cur - 1]
nums[cur - 1] = nums[cur]
nums[cur] = temp
cur -= 1
else:
break
return nums
print(Insertionsort([6, 5, 4, 1, 8, 7, 2, 4 ]))
五、希尔排序
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
于是，我们提出一个想法，（针对第二点）对于每个元素，每次不再只移动一位，而是“大踏步”的移动。（针对第一点）经过“大踏步”的移动以后，顺序相对好很多，此时再进行插入排序，效果会好很多。
针对上面你的想法，我们再具体的提出一些改进。
比如，对于一个有9个元素的list，我们取gap为3，先对index为0,3,6的元素进行插入排序，再对1,4,7的子列表插入排序，再对2,5,8的子列表进行插入排序。
经过对这三个子列表进行排序以后，我们发现此时的列表相对好了很多：
此时再进行插入排序，只需要再经过三次的替换就行了：
另外我们注意到，gap == 子列表数。比如，我们设定gap为3，那么子列表的数目也就是3。怎么理解呢，也很好理解：从第0位元素出发，3为gap向右走到头是sublist1，同理从第1位出发， 第2位出发，可以得到sublist2，sublist3。这三个子列表就已经把整个list给遍历完了。
也就是说，对于一个gap，我们会得到gap个子列表，而这gap个子列表的起始元素列表是
start_list = [x for i in range(gap)]
我们可以通过上面的理解，得到要进行插入排序的每个子列表的起始元素。
我们再定义一个插入排序函数，就是上一节的插入排序代码，只不过gap不再是1了。传入列表nums，子列表的起始元素start，gap，我们便可以对这个子列表进行插入排序。
而这里的希尔排序，我们不是固定了gap，我们先采用最大的gap（即len(nums)//2），然后依次将gap除以2，直到gap为1进行最后的插入排序。比如上面例子中，我们采用的是长度为9 的list，那么我们先用gap为4，此时就有四个子列表，我们对这四个子列表调用插入排序的函数。下次gap为2，就有2个子列表，再调用插入排序的函数。。。
代码思路
- 所以需要一个while循环，循环对不同的gap进行分列表以及排序操作，循环结束条件为gap等于0.
- while里再需要一个for循环，按照上面所说对gap子列表调用插入排序函数。
- 定义一个传入start，gap，nums，能进行插入排序的函数。
代码实现：
def shellSort(nums):
#gap初始化为最大的gap，然后在while循环中不断整除2，减小gap
gap = len(nums)//2
while gap > 0:
#对gap个子列表调用插入排序函数
for startposition in range(gap):
gapInsertionSort(nums,startposition,gap)
print("After increments of size",gap,
"The list is",nums)
gap = gap // 2
#输入nums，起始位置，gap，就可以选出子列表，并且进行插入排序
def gapInsertionSort(nums,start,gap):
for i in range(start,len(nums),gap):
cur = i
while cur >= gap:
if nums[cur - gap] > nums[cur]:
temp = nums[cur - gap]
nums[cur - gap] = nums[cur]
nums[cur] = temp
cur -= gap
else:
break
nums = [54,26,93,17,77,31,44,55,20]
shellSort(nums)
print(nums)
六、归并排序
参考归并排序
最易于理解的白话：首先考虑下如何将将二个有序数列合并
- 1、这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。
- 2、然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
比如，13跟24678合并。
1跟2比较，1小于2，那么list.append(1)。
3跟2比较，2小于3，那么list.append(2)
3跟4比较，3小于4，那么list.append(3)
left数列已经为空，那么就把right的数列都append到list中。
那么归并排序呢，一样的道理。但是不一样的地方就是，一开始不是两个有序list，而是是一整个无序list，为了满足“两个，有序”的要求，我们分两步：
- 1、先把list分成left和right两个无序的部分
- 2、把这两个无序的部分，调用函数排成两个有序的部分
这里的两个无序的部分怎么排序成有序的部分呢。就是递归调用归并排序函数了。 - 3、对两个有序的部分，进行上面的merge操作即可。
其中递归的地方就是，上面的第二步中，上面的
代码思路
- 写一个对两个有序list进行归并的函数merge。传入两个有序list，返回一个合并好的list。
- 写一个递归调用自身的归并排序函数mergesort，传入一个无序list，调用merge，返回一个有序list。内容如下
1、把无序列表分成两个无序列表
2、对上面两个无序列表递归调用归并排序函数mergesort，能够返回两个有序的子列表。
3、对上一步返回的两个有序子列表，调用merge函数。
把一个list一路递归到每个list长度为1的时候，返回两个长度为2的有序list，合并后再返回两个长度为4的有序list，再合并。。一直到返回len(nums)的list。
具体细节图片参考归并排序
代码实现：
def MergeSort(lists):
#递归结束条件，list小于等于1
if len(lists) <= 1:
return lists
#把无序list分成两个部分
num = int( len(lists)/2 )
#对这两个无序list，递归调用归并排序函数
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
#对于返回的两个有序list，调用merge函数
return Merge(left, right)
#按照合并两个有序list的论述，定义一个合并函数
def Merge(left,right):
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += right[r:]
result += left[l:]
return result
print(MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))
七、堆排序
对于堆的理解，参考树4，二叉树的特例——堆
三、快速排序
3.1、大致理解快速排序的方针
3.1.1、以中间数为基准，先把一个list分成两个大小两个区域
对于一个无序list，取index为0的元素作为中间数，然后执行分区函数，让比中间数小的点都在中间数左边，比中间数大的点都在中间数右边。此时得到了一个看似有序其实无序的list：
- 有序体现在此时list分成了两个区域，左边的都比中间数小，右边的都比中间数大。
- 无序体现在，而这两个区域，又都是无序的list
3.1.2、对上述的两个区域，递归调用快速排序
我们对这两个无序的list再次调用分区函数，此时会得到四个看似有序而又无序的list，接着调用分区函数，直到最终list长度为2时，再调用一次分区函数，那么一定是左边有序并且小于右边，因此此时所有的子列表都是有序的，那么此时一整个list也就是一个有序的list了。
3.2、快速排序的细节问题
3.2.1、分区函数怎么分区
我们取index为0的元素为中间数，left指针代表其指向的元素应该在中间数左边，即小于中间数；right代表其指向的元素应该在中间数右边，大于中间数。而实际情况不会这么完美，于是我们进行下面这样的操作，如下图：
无序列表为nums，对于我们要执行分区函数的列表调用分区函数：
- 一开始我们选54作为中间节点，定义left指针指向index为1的元素，right指向列表的最后一个元素。左右指针开始汇合；
- 一开始左指针指向元素为26，小于54，说明这个元素的位置是正确的，则左指针加1向右移动，指向96时，这个元素位置是错误的，暂时停止left的移动
- 同理，我们移动右指针，直到找到错误的元素，为20
- 对这两个位置错误的元素，调换位置，然后再接着移动左右指针。
移动过程中发现位置错误的元素，继续调换位置。
直到最后这种情况：
此时左指针指向77停止，右指针指向31停止，但是此时左指针大于右指针了，说明他俩指向了两人已经工作过的区域了，此时不用再调换位置了。直接替换右指针指向元素与中间数，就能得到一个，已经分好区域的list了。左右两个区域。
3.2.2、怎么调用递归函数使得能够继续分区
上面我们其实会得到两个小的无序的区域，以什么划分这两个区域呢（注意中间数不用再掺和进去了），就是中间元素的index啊。于是：
- 左边的无序区域为nums[first:index-1]
- 右边的无序区域为nums[index+1,last]
于是对这两个区域再调用递归函数即可。
3.3、代码思路：
3.3.1、定义快排函数quickSort()
根据上面所说，递归调用的函数，需要传入三个参数，一个是列表nums，还有两个是用来划分需要快排区域的参数first和last。
而一开始我们只能传入一个参数就是列表nums。
因此我们定义一个辅助函数quickSortHelper()，既能用来递归调用快排操作，又能传入三个参数。
初始化中，传入的三个参数分别是nums，first = 0，last = len(nums) - 1
3.3.2、定义递归调用函数partition()
此函数传入三个参数，列表nums，以及用来划分要对列表进行快排操作的区域指针，first和last
执行此函数后，函数会将要分区的列表区域进行分区。
- 1、递归结束条件是first小于last
- 2、函数改变条件，每次传入的需要排序的区域指针都会不断改变，直到first大于last截止
函数里面调用一次分区函数，返回中间数的index，用来改变下次调用递归函数的first与last。
其中左半部分区域为first，index-1.右半部分为index+1，last - 递归调用，上一步，得到递归调用的区域，直接递归调用两次快排函数即可。
3.3.3、定义分区函数
此函数传入三个参数，列表nums，以及用来划分要对列表进行快排操作的区域指针，first和last
1、用一个“大”while循环来执行错误元素换位的情况，循环结束的条件为左指针大于右指针。
2、里面再用“小”while循环来执行移动指针的情况，当指针指向元素相对中间数“正确”时，就继续执行循环移动指针。
需要用到两个while，一个控制左指针，一个控制右指针。3、当上述两个“小”while循环结束时，说明左右指针都指向了相对错误的元素，此时分为两种情况：
1、左指针小于右指针：说明此时分区工作还没结束，对两个元素进行换位（上面的图1跟图2），继续执行元素换位的“大”while。
2、左指针大于右指针：说明此时的分区工作已经结束了，对右指针指向的元素与中间数进行换位（上面的图3），并且结束最外面的while循环。4、循环结束，可以返回中间数的index了，留着下一次递归调用函数的时候使用。
图片理解参考 快速排序
代码实现:
def quickSort(alist):
quickSortHelper(alist, 0, len(alist) - 1)
def quickSortHelper(alist, first, last):
if first < last:
splitpoint = partition(alist, first, last)
# 得到中点正确的位置，限制下面两个递归的边界
quickSortHelper(alist, first, splitpoint - 1)
quickSortHelper(alist, splitpoint + 1, last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
#如果左指针小于右指针，并且左指针指向的元素小于等于中间数，那么左指针就继续走
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
#如果左指针小于等于右指针，并且右指针指向元素大于等于中间数，右指针就继续走
while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
rightmark = rightmark -1
#左指针大于右指针时，done为True，结束循环
if rightmark < leftmark:
done = True
#经过上面的指针操作以后，如果左指针还是小于右指针，则替换二者指向元素
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
#done为True，结束循环，替换中间元素与右指针指向元素的位置
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
##返回此时中点的位置，用于下次递归分类划分左右部分
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
