剑指offer已经刷完一遍了，今天开始学习整理一下排序算法。争取每天整理两个。
参考博客：http://www.cnblogs.com/feixuelove1009/p/6143539.html
2018.10.19
一、排序的概念和分类
1、排序的稳定性：
经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。
举个例子，要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。
该图有个错的地方，简单选择排序是不稳定的算法。
2、内排序和外排序：
内排序：排序过程中，待排序的所有记录全部放在内存中
外排序：排序过程中，使用到了外部存储。
通常讨论的都是内排序。
3、影响内排序算法性能的三个因素：
时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数
空间复杂度：主要是执行算法所需要的辅助空间，越少越好。
算法复杂性：主要是指代码的复杂性。
二、冒泡排序
冒泡排序（Bubble sort）：时间复杂度O(n^2)
交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。
先定义一个交换元素位置的函数：
class SQList():
def __init__(self, nums):
self.nums = nums
def swap(self, i, j):
'''将nums数组的第i个元素和第j个元素交换位置'''
self.nums[i] , self.nums[j] = self.nums[j], self.nums[i]
return
冒泡排序是最简单的一种排序方法。
可以细分为以下三种：
1、简单排序
简单排序的思想很简单，将第一个元素与后面所有元素依次进行比较，如果第一个元素更大，则交换两元素的位置，经过一轮比较后，第一个元素就是该列表中最小的数，然后再用第二个元素依次与后面的元素比较。时间复杂度为O(n^2)。
def simple_sort(self):
'''简单排序'''
for i in range(len(self.nums)):
for j in range(i+1, len(self.nums)):
if self.nums[i] > self.nums[j]:
self.swap(i, j)
return self.nums
2、冒泡排序
冒泡排序虽然也是两两比较，但是跟简单排序不一样，冒泡排序是每两个相邻的元素比较，如果大小相反则交换，如果从数组第一个元素开始比较的话，经过一轮后，最大的数就排到了数组的最后一位，然后再接着排第二大的数。时间复杂度为O(n^2)。
def simple_bubble(self):
'''简单冒泡排序'''
j = 0
while j <= len(self.nums)-1:
for i in range(len(self.nums)-j-1):
if self.nums[i] > self.nums[i+1]:
self.swap(i, i+1)
j += 1
return self.nums
3、改进版冒泡排序
改进的冒泡排序的思路跟冒泡排序是一样的，不过增加了一个提前中止的条件，如果在某一轮比较中，没有任何两个元素交换位置，那么此时的序列已经是有序的，可以提前中止。时间复杂度为O(n^2)。
def bubble(self):
'''改进版冒泡排序'''
j = 0
while j <= len(self.nums)-1:
flag = False
for i in range(len(self.nums)-j-1):
if self.nums[i] > self.nums[i+1]:
self.swap(i, i+1)
flag = True
if not flag:
return self.nums
j += 1
return self.nums
冒泡排序整理完了，下面开始第二大排序算法
三、简单选择排序
冒泡排序是每次比较如果位置错了就会交换一次位置，换了很多次位置后才确定了一个元素的位置。那么我们可不可以只用一次交换就确定一个元素的位置呢？当我们要排第一个位置的元素时，我们可以找到第一个以后所有元素的最小值，再和第一个位置比较，如果位置错误，那么就交换位置。那样我们虽然遍历了整个列表，但是只用了一次交换函数，虽然时间复杂度跟冒泡排序一样，但是只调用了一次交换函数，所以相对冒泡排序还是有一定程度的改进。时间复杂度为O(n^2)
def select_sort(self):
'''简单选择排序'''
for i in range(len(self.nums)-1):
temp = [None, -1]
for j in range(i, len(self.nums)):
if not temp[0]:
temp = [self.nums[j], j]
if self.nums[j] < temp[0]:
temp = [self.nums[j], j]
if temp[0] < self.nums[i]:
self.swap(i, temp[1])
return self.nums
2018.10.20
四、直接插入排序
直接插入排序的思想是将一个新的元素插入到前面排好序的序列中。时间复杂度为O(n^2)
def insert_sort(self):
'''插入排序'''
for i in range(1, len(self.nums)):
j = i - 1
temp = self.nums[i]
while j >= 0 and temp < self.nums[j]:
self.nums[j+1] = self.nums[j]
j -= 1
self.nums[j+1] = temp
return self.nums
抄原文一张图
五、希尔排序
希尔排序是对直接插入排序的改进版，其核心思想是将原始数据集分割成若干个子序列，然后再对子序列分别进行插入排序，使子序列基本有序，最后再对全体进行一次插入排序。
这里最关键的是跳跃和分割的策略，也就是我们要怎么分割数据，间隔多大的问题。通常将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过：increment = int(increment/3)+1来确定“增量”的值。
第一遍没看明白，后来查了其它的资料，才完全明白是怎么回事。以下内容来自博客：https://www.cnblogs.com/chengxiao/p/6104371.html
希尔排序的时间复杂度为：O(n^(3/2))
根据这个思路自己写的代码:
def shell_sort(self):
def insertSortPerGap(nums, gap):
for i in range(1, len(nums)):
j = i - gap
temp = nums[i]
while j >= 0 and temp < nums[j]:
nums[j+gap] = nums[j]
j -= gap
nums[j + gap] = temp
return
gap = int(len(self.nums)/2)
while gap>=1:
insertSortPerGap(self.nums, gap)
gap = int(gap/2)
return self.nums
2018.10.21
六、堆排序
参考的也是写希尔排序的博客：https://www.cnblogs.com/chengxiao/p/6129630.html
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最好、最坏、平均时间复杂度为O(nlogn)，它是不稳定排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
我们用简单的公式来描述一下堆的定义就是(索引从0开始)：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。将其与末尾元素进行交换，此时末尾就是最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，就能得到一个有序序列。
一般升序采用大顶堆，降序采用小顶堆
所以堆排序的关键就在于如何将一个序列构造成一个堆。可以从最后一个非叶子结点开始，从左至右，从下至上进行调整。根据完全二叉树的性质，可以知道最后一个非叶子结点的索引就是len(array)//2 - 1(根结点索引为0)，那么它之前的所有结点都是非叶子结点，只需要按照这个顺序去构造大顶堆或小顶堆就可以了。
以下自己用python实现的代码：
def heap_sort(self):
def heap_adjust(nums, length):
index_root = int(length // 2 - 1)
while index_root >= 0:
index_kid1 = index_root * 2 + 1
index_kid2 = index_root * 2 + 2
if nums[index_root] < nums[index_kid1]:
self.swap(index_root, index_kid1)
if index_kid2 <= length - 1:
if nums[index_root] < nums[index_kid2]:
self.swap(index_root, index_kid2)
index_root -= 1
length = len(self.nums)
while length >= 2:
heap_adjust(self.nums, length)
self.swap(0, length - 1)
length -= 1
return self.nums
七、归并排序
思想比较简单，参考https://www.cnblogs.com/chengxiao/p/6194356.html
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
这张图大概能看出整个流程了。
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
很遗憾的是，归并算法我没写出来😔。合并的操作写出来了，但是前面那个递归调用的时候有点乱，没写出来，但其实就是个跟二叉树差不多的操作过程。参考别人的代码再重新码了一遍。
def merge_sort(self):
def msort(nums):
if len(nums) <= 1:
return nums
mid = len(nums)//2
left = msort(nums[:mid])
right = msort(nums[mid:])
return merge(left+right)
def merge(numbers):
temp = [0] * len(numbers)
i = 0
j = len(numbers) // 2
index = 0
while i < len(numbers) // 2 and j < len(numbers):
if numbers[i] < numbers[j]:
temp[index] = numbers[i]
index += 1
i += 1
else:
temp[index] = numbers[j]
index += 1
j += 1
if i < len(numbers) // 2:
temp[index:] = numbers[i:len(numbers) // 2]
else:
temp[index:] = numbers[j:]
numbers = temp
return numbers
return msort(self.nums)
2018.10.22
今天就只剩最后一个快速排序了。
八、快速排序
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。
快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。
核心的交换代码我自己写的比较复杂，以下是我自己写的：
def splitByK(numbers):
times = 0
leftindex = 0
rightindex = len(numbers) - 1
k = numbers[0]
while rightindex > leftindex:
if times % 2 == 0:
if numbers[rightindex] < k:
numbers[leftindex] = numbers[rightindex]
times += 1
leftindex += 1
else:
rightindex -= 1
if times % 2 == 1:
if numbers[leftindex] >= k:
numbers[rightindex] = numbers[leftindex]
times += 1
rightindex -= 1
else:
leftindex += 1
numbers[rightindex] = k
然后参考别人的代码思路，重新码了一遍：
def partition(nums):
leftindex = 0
rightindex = len(nums) - 1
k = nums[0]
while leftindex < rightindex:
while leftindex < rightindex and nums[rightindex] > k:
rightindex -= 1
swap(nums, leftindex, rightindex)
while leftindex < rightindex and nums[leftindex] < k:
leftindex += 1
swap(nums, leftindex, rightindex)
最后是完整代码:
def quick_sort(self):
def partition(nums, leftindex, rightindex):
leftindex = leftindex
rightindex = rightindex
k = nums[leftindex]
while leftindex < rightindex:
while leftindex < rightindex and nums[rightindex] > k:
rightindex -= 1
self.swap(leftindex, rightindex)
while leftindex < rightindex and nums[leftindex] < k:
leftindex += 1
self.swap(leftindex, rightindex)
return leftindex
def qsort(nums, low, high):
if low < high:
pivot = partition(nums, low, high)
qsort(nums, 0, pivot)
qsort(nums, pivot+1, high)
qsort(self.nums, 0, len(self.nums)-1)
return self.nums
快速排序的时间性能取决于递归的深度。
当pivot_key恰好处于记录关键码的中间值时，大小两区的划分比较均衡，接近一个平衡二叉树，此时的时间复杂度为O(nlog(n))。
当原记录集合是一个正序或逆序的情况下，分区的结果就是一棵斜树，其深度为n-1，每一次执行大小分区，都要使用n-i次比较，其最终时间复杂度为O(n^2)。
在一般情况下，通过数学归纳法可证明，快速排序的时间复杂度为O(nlog(n))。
但是由于关键字的比较和交换是跳跃式的，因此，快速排序是一种不稳定排序。
同时由于采用的递归技术，该算法需要一定的辅助空间，其空间复杂度为O(logn)。
最后再补充一点各个排序的应用场景，参考：https://blog.csdn.net/mbuger/article/details/67643185
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。
