边界如此之复杂，思路如此之诡谲。
时间复杂度O（nlogn）空间复杂度O（1）
堆排序：
1.把数组中的元素插入到大根堆，大根堆只保证堆顶元素为最大值，但是整体不保证有序。
2.把堆顶元素与最后一个元素交换，同时堆长度heapsize减一
3.把交换过后的0到heapsize的元素大根堆化，再重复第二步，直到heapsize的元素为1
建立堆的时间复杂度O(n)
1.heapsert函数是用来建立插入元素同时保证大根堆结构，
当前值从最后一个位置开始，每次与父节点比较大小，如果当前值比父节点大，则交换父节点直到当前值小于等于父节点。父节点为(index-1)//2
2.heapify函数是用来把当前长度内的元素大根堆化
当前值从根开始，每次与左右孩子中的较大值做交换，当当前没有做交换时则停止。
左孩子为2index+1，右孩子为2index+2
def heapSort(arr):
for i in range(len(arr)):
heapInsert(arr, i) #先把所有值插入到大根堆中
heapsize = len(arr)
heapsize = heapsize -1
swap(arr,0,heapsize) #把堆顶最大值换到数组末尾
while heapsize > 0:
heapify(arr, 0, heapsize) #再次整理为大根堆，方便下次插入
heapsize = heapsize - 1
swap(arr,0,heapsize) #把堆顶最大值换到数组末尾
def heapify(arr,index,heapsize):
lchild = 2*index+1
largest = 0
while(lchild < heapsize):
if lchild + 1 < heapsize and arr[lchild + 1] > arr[lchild] :
largest = lchild+1
else:
largest = lchild
if(arr[largest] > arr[index]):
largest = largest
else:
largest = index
if(largest == index):
break
swap(arr,largest,index)
index = largest
lchild = 2*index + 1
def heapInsert(arr,index):
rootIdx = (index -1) >> 1
while arr[rootIdx] < arr[index]:
swap(arr,rootIdx, index)
if(rootIdx==0):
break
index = rootIdx
rootIdx = (index -1) >> 1
def swap(arr, i , j):
arr[i],arr[j]=arr[j],arr[i]
lst=[6,5,4,3,5,2,8]
heapSort(lst)
print(lst)
_____________________________________________________________
output: [2, 3, 4, 5, 5, 6, 8]
排序中的稳定性是指，排序过后，在原始数组中相对次序不改变。
1.冒泡排序可以实现稳定性：遇到相同值时，则让下一个值进行移动。
2.插入排序也可以实现稳定性，方法与冒泡类似，遇到相同值时，让前面的一个值再往前找
3.选择排序做不到稳定性
4.归并排序可以实现稳定性，归并排序划分为左右两个区域，我们可以规定在归并的时候，遇到相同值时，让左边的先拷贝下来，再拷贝右边的值。
5.堆排序做不到稳定性
6.快速排序也做不到稳定性
现实世界的业务需要稳定性，保证原始信息不被抹去。
总结一下：
具有稳定性的排序：冒泡排序，插入排序，归并排序
不具有稳定性的排序：选择排序，堆排序，快速排序
工程中的综合排序：
如果是基础数据类型，则在工程中选择快排，基础类型的稳定性无意义，都是数字3，在前在后是一样的。
如果是自定义的数据额结构，则在工程中是快速排序，保证稳定性。
如果长度小于60，则用插入排序
京公网安备 11010502036488号