六大排序
冒泡排序
思想
冒泡排序是一个简单的排序算法，这个排序算法的核心之处在于每个相邻的元素都进行比较，如果不是按顺序的形式，就交换彼此。这个算法不适用于大数据量的排序，因为它的平均时间复杂度和最差时间复杂度都是O(n^2)。
下图是一个没有排序好的数组：
img
首先，冒泡排序会比较前面两个数字，判断他们哪个会更大些。
img
在我们的例子中，14 和 33 已经是按照从小到大的顺序排列的了。所以我们不需要对这两个元素进行操作。接下来我们比较33和27。
img
我们发现，33和27并不是按照从小到大的顺序排列的，这两个数字就需要交换。
img
交换后的新数组的排列形式如下所示：
img
这时，我们需要继续比较 33 和 35。由于 35 大于 33，也就是从小到大的顺序排列的，所以不需要交换。
img
最后，我们比较下两个数，35 和 10
img
我们知道 35 和 10 并不是按照从小到大的顺序排列的，需要交换
img
最终，我们会对这两个数字进行交换，然后一次循环结束，我们发现达到的效果是，最大的数在数组的最后。下一次再进行冒泡排序的时候，就不需要对最后的元素比较了。
img
按照新的元素 14， 27， 33， 10。再次循环上面的过程，直到排序完成。
在第二次循环之后，这个数组的样子应该是：
img
第三次循环后的样子：
img
第四次：
img
以上就是一个冒泡排序的过程。
python实现
# 冒泡排序
def maopao(array):
for i in range(len(array)):
for j in range(len(array)-i-1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
if __name__ == '__main__':
array = [1, 2, 5, 8, 4, 19, 30, 3, 7, 9]
maopao(array)
print(array)
插入排序
思想
插入排序，在插入排序中，会维护一个始终排好序的子序列。比如说，低值部分一直维护成为一个排序的序列。一个元素想要被插入到这个已经排好序的子序列，就必须要找到属于它的特定的位置，然后插入到那个位置。插入排序的时间复杂度依然是O(n^2)。
同样， 我们使用一个没有排序的数组来演示插入排序。
img
插入排序会比较前两个元素，14 和 33.
img
我们发现，这两个元素已经是升序排列了，到目前为止，14已经在排序序列内了。
img
然后插入排序向前挪动一个元素，比较 33 和 27
img
我们发现他们不是升序排列的，所以我们需要将他们排列成升序的形式。
img
交换33和27，然后27也要和之前已经排好序的那一部分进行比较，目前我们的排好序的序列只有14，而27比14大，所以不需要做交换。第二个元素添加进排好序的序列后的图片如下所示：
img
现在我们的排序序列中有的就是14和27，接下来需要比较的是33和10
img
发现不是升序排列，
img
将10 和 33 交换
img
此时还需要再次比较10和已经排序的序列内的元素，发现10比27小，
img
不是升序排列，交换10和27
img
再向前我们发现，14 和 10 也不是按照升序排列。
img
我们再次交换10和14，经过这三次的循环，我们能够得到一个有序的子序列：
img
这个过程持续下去，一直到所有的元素都被包含在这个子元素内部。这样就实现了将一个数组内的数字排序的功能。
python实现
def InsertSort(arr):
for i in range(1, len(arr)):
for j in range(i-1, -1, -1):
if arr[i] < arr[j]:
arr[i], arr[j] = arr[j], arr[i]
i -= 1
else:
break
# 改进版本
def InsertSort2(arr):
for i in range(len(arr)):
while i >= 1 and arr[i] < arr[i-1]:
arr[i], arr[i-1] = arr[i-1], arr[i]
i -= 1
if __name__ == '__main__':
arr = [9, 25, 6, 4, 29, 10, 23, 45, 7, 30, 12]
InsertSort(arr)
print(arr)
选择排序
思想
选择排序同样是一个比较简单的排序算法，这个算法也是要维护两个部分的数组。第一个部分的数组是已经排好序的数组，另一部分是没有排好序的数组。初始的时候是排好序的部分是空，没有排序的部分是整个数组。
选择排序的主要的工作流程就是，在没排好序的数组中，找到最小的那个值，然后和没排好序的最左边的那个数字进行交换。这样再将最左边的那个元素纳入到已经排好序的那个队列中，就能够将排好序的序列增大一个元素，而没排好序的序列减少一个元素。插入排序的时间复杂度依然是O(n^2)，不适合大量数据的排序。
再次应用我们之前的那个没有排序的数组来看选择排序的过程。
img
一开始，没排序的最左边是14这个元素，然后寻找整个没有排序的数组中哪个是最小的元素，发现是10这个元素
img
交换10和14，在交换之后，排序的序列就出现了，只有一个元素是10.
img
然后继续选取没有排序的数组的最左侧，是33，然后寻找整个没有排序的数组，发现最小的那个值是14。
img
我们将33和14交换位置，然后就完成了第二次循环。生成了包含两个元素的有序数组，和剩下的无序数组
img
然后循环这个过程， 我们就得到了所有的数据都是有序数组，无序数组为空的情况。整个数组排序完成。
img
以上就是选择排序的所有思想。
希尔排序
思想
希尔排序是一种高效的排序方式，它是基于插入排序的一种排序算法。它相比插入排序能够有效的避免大量的移动操作。
这种算法使用插入排序，只是比较的时候使用的是很远的数据进行比较，然后将它们排序。这个比较远的距离是通过下面的计算式子得出的：
h = h * 3 + 1
这种算法的时间复杂度是 O(n^2) ~ O(n*log2n).
下面介绍这个希尔排序：
我们先通过之前的例子再次看下希尔排序的工作方式。首先是计算h的值，h是从1开始的，带入上面的公式发现，h=4. 然后就发现 4 这个值小于数组长度 8.
然后继续计算h的值，带入上面的公式得出，h=13. 大于了数组的长度8.由此可知，我们的初始距离就应该选择4. 那么下面的数组就能够被分成四组分别排序。{35, 14}, {33, 19}, {42, 27}, {10, 44}
img
然后就是比较每组内的这两个数，如果发现不是升序排列的，就交换这两个数字。那么第一次交换以后的模样应该如下所示：
img
那下一次的h的值就是1了，所以我们按照间隔1分组，就会分成一组，那么就是按照上面的数组进行插入排序，如下图：
img
在上面的结束以后，我们发现，只用到了四次交换就完成了功能。
python实现
def ShellSort(arrList):
arrLen = len(arrList)
h = 1
while h < arrLen//3:
h = h * 3 + 1
while h >= 1:
for i in range(h, arrLen):
j = i
while j >= h and arrList[j] < arrList[j-h]:
arrList[j], arrList[j-h] = arrList[j-h], arrList[j]
j -= h
h = h // 3
if __name__ == '__main__':
arr = [5, 1, 8, 9, 23, 56, 3, 65, 4, 10, 30]
ShellSort(arr)
print(arr)
归并排序
思想
归并排序是用到了分治的思想，分治的思想是将一个大问题拆分成很多的小问题，然后再将已经处理完成的小问题合并成整个的大问题。在这个过程中，大问题就得到了解决。在大数据方面的 Map-Reduce 就是这样的分治的思想。
归并排序首先将数组等分，然后排序等分后的数组，最后再将排好序的两个数组合并成一个排好序的数组。归并排序的时间复杂度是O(n log n)
为了能够更好的理解归并排序，我们来看下面的数组：
img
依然是上次我们用到的没有排序的数组，上面总共有八个数字，等分后就会变成每组四个数字。这样的等分一直持续到只剩下一个数字的情况。
img
由于还没有将数组等分到只有一个元素的情况，所以我们继续等分。
img
此时，每个分组中只有两个数字，还是可以继续等分。
img
在这个时候，等分结束。因为所有的分组都只能分到这种程度，没有数组还能继续等分了。
然后我们将数组进行俩俩合并，首先我们需要比较两个数组中的每一个数据，然后将这些数据放入一个新的数组中，新数组就是有序的。这里比较的过程就是 14 和 33 是升序的，不需改变。27 和 10 是降序的，需要先放入10，再放入27. 35 和19也是降序的，需要先放入19， 再放入27. 最后，42 和 44 是升序的，不需改变。
img
再下一次将前两个合并到一个数组中，后面两个合并到一个数组中。过程是：前两个数组合并，先判断14 和 10，发现 14 要 大于10，所以在新生成的数组中将 10 写在第一个位置上。然后比较14 和 27 发现14小，将 14 写在新生成的数组的第二个位置。在比较33 和 27，发现27 小，将27写在新生成的数组中。由于第二个数组写入完成，所以将第一个数组的剩余部分写入新生成的数组。第三组和第四组合并过程也是类似：19 vs. 42 => 19, 35 vs. 42 => 35, 一个结束另一个写入剩余的部分=>42, 44
img
最后，经过最终的merge操作，生成的数组就是下面的这个模样：
img
python实现
def MergeSort(array):
arrlen = len(array)
# 将数组切分成两部分
if arrlen <= 1:
return array
midindex = arrlen // 2
# 将数组进行递归切分
leftarr = MergeSort(array[:midindex])
rightarr = MergeSort(array[midindex:])
# 对切分的数据进行排序
resarry = MergeCore(leftarr, rightarr)
return resarry
def MergeCore(leftArray, rightArray):
# 定义左右数组指针
leftindex = 0
rightindex = 0
# 定义指针边界
leftlen = len(leftArray)
rightlen = len(rightArray)
# 定义空数组
reslist = []
# 进行排序:比较两边每一个数的大小,小的放入空数组内
while leftindex < leftlen and rightindex < rightlen:
if leftArray[leftindex] < rightArray[rightindex]:
reslist.append(leftArray[leftindex])
leftindex += 1
else:
reslist.append(rightArray[rightindex])
rightindex += 1
# 将两边剩余的数组放置到新数组中
reslist.extend(leftArray[leftindex:])
reslist.extend(rightArray[rightindex:])
return reslist
if __name__ == '__main__':
array = [13, 4, 53, 8, 12, 48, 34, 1, 23, 6]
res = MergeSort(array)
print(res)
快速排序
思想
快速排序是一个非常高效的排序算法，目前的应用非常广泛， 同时也是面试的常客。学好快速排序，能够对找到工作有很大的帮助。同时，也有很多面试题也会用到这种思想。
快速排序也是一种分治的思想，但是它于归并算法更加好是因为归并算法会用到辅助数组，其空间复杂度是O(n). 而快速排序不需要用到新的数组空间，它的空间复杂度是O(1).
快速排序的核心是：选定一个值作为轴心值，然后将数组分成两个部分，一部分是大于这个轴心值，另一部分是小于这个轴心值的。然后将这个轴心值前的部分继续使用快速排序，将这个轴心值的后半部分继续使用快速排序。直到指剩下了一个元素的时候是不需要交换的。快速排序非常适用于大数据量的排序，因为它既不占用多余的空间，又能达到时间复杂度是O(nlogn).
下面，快速排序的步骤：
img
第一步：选择最大的index作为轴心
第二步：选择两个指分别指向最左边左边和除了轴心的最右边。
第三步：两个指针分别是left和right。左边的只想低索引。右边的指向高索引。
第四步：当左边的索引的值小于轴心，那就向右移动索引。
第五步：当右边的索引的值大于轴心，那就向左移动索引。
第六步：当第四步和第五步都不符合时，交换彼此。
第七步：如果 left >= right, 那么left就是新的轴心的位置，将轴心与之交换。
python实现
def partition(array, leftIndex, rightIndex):
i = leftIndex - 1
for j in range(leftIndex, rightIndex):
if array[j] < array[rightIndex]:
array[j], array[i+1] = array[i+1], array[j]
i += 1
array[i+1], array[rightIndex] = array[rightIndex], array[i+1]
return i+1
def QuickSort(array, leftIndex=0, rightIndex=None):
if len(array) <= 1:
return array
if rightIndex == None:
rightIndex = len(array) - 1
if leftIndex < rightIndex:
# 寻找中间值,使用partition来得到数组的中间值,并将数组分治
pivot = partition(array, leftIndex, rightIndex)
QuickSort(array, leftIndex, pivot - 1)
QuickSort(array, pivot + 1, rightIndex)
if __name__ == '__main__':
array = [123,23,5,89,47,45,12,3,9,8,14,7]
QuickSort(array)
print(array)
