排序算法
给定一个整数列表，对列表进行排序。
示例：
输入：
[73, -22, 93, -43, 55, -14, 28, -22, 65, -39, 0]
输出：
[-43, -39, -22, -22, -14, 0, 28, 55, 65, 73, 93]
解答：
1. 选择排序
将列表看成前面的有序数组和后面的无序数组（初始时len(有序) = 0 , len(无序) = len(nums)）。
每一轮扫描找出无序数组中最小的元素，将其与无序数组中的第一个元素对调。
下一轮开始时，有序数组长度+1，无序数组长度-1。直到len(有序) == len(nums)。
def chooseSort(self,l,start = 0): # start为无序数组的起始下标
if l is None or len(l) in [0, 1]: return l
if start+1 == len(l) : return l
minNum = l[start]
minIndex = start
i = start
while(i < len(l)):
if l[i] < minNum :
minNum = l[i]
minIndex = i
i+=1
l[start],l[minIndex] = l[minIndex],l[start]
self.chooseSort(l,start+1)
return l
2. 插入排序
将列表看成前面的有序数组和后面的无序数组（初始时将第一个元素默认视为有序数组）。
每一轮将无序数组的第一个元素插入有序数组的恰当位置。
下一轮开始时，有序数组长度+1，无序数组长度-1。直到len(有序) == len(nums)。
def insertSort(self,l,start = 1): # start为无序数组的第一位 第0位默认有序
if l is None or len(l) in [0, 1]: return l
if start == len(l): return l
i = 0
if l[start] < l[start-1] : # start要做插入 自己不是最大的
temp = l[start] # 插入之前 保存自己
while(l[start] > l[i] ): # 最后哪怕跟自己换
i += 1
for j in range(start-1,i-1,-1): # 前面的
l[j+1] = l[j] # 统统往后挪一位
l[i] = temp # 最后插入
self.insertSort(l,start+1)
return l
3. 冒泡排序
将列表看成前面的无序数组和后面的有序数组（初始时len(无序) = len(nums) ,len(有序) = 0）
每一轮从前往后遍历整个无序数组，只有当后一个元素比自己大时，才对调两个元素的位置，
当遍历至无序数组的最后一个元素时，该元素一定是无序数组中最大的那个元素，该轮遍历结束。
这样，每一轮遍历的结果都是将当前无序数组的最大元素放至无序数组的最后一位，len（nums）-1轮之后，排序完毕。
def bubbleSort(self,l,end = None):
if l is None or len(l) in [0, 1]: return l
end = len(l)-1 if end == None else end # 假如调用有缺省，但是递归又要用到一个参数
if end == 0 : return l
i = 0
while (i <= end-1):
if (l[i] > l[i+1]): # 前面比后面大
l[i],l[i+1] = l[i+1],l[i] # 就交换
i+=1#无论如何i+1
self.bubbleSort(l,end-1)
return l
4. 归并排序
采用分治思想，将待排序数组分为两个数组，对其中的每一个数组递归地调用该排序算法，直到数组长度为1的递归出口。
最后，对两个排序完毕的有序数组进行两两合并，得到最后整个有序数组。
def mergeSort(self,l): # 递归调用归并排序
if l is None or len(l) in [0,1] : return l
#if len(l) in [0,1] : return l
return self.merge2SortedList(self.mergeSort(l[:len(l) // 2]) , self.mergeSort(l[len(l) // 2:]))
def merge2SortedList(self,l1,l2,result = None): # 对两个排序完毕的有序数组进行两两合并
result = [] if result is None else result
if l1 is None and l2 is None: return None
if l1 == [] or l1 is None:
result.extend(l2)
return result # 注意return 如果不return 下面数组越界了
if l2 == [] or l2 is None:
result.extend(l1)
return result
result.append(l1[0] if l1[0] <= l2[0] else l2[0]) # 访问了数组 特别注意l1是None或者l1是空
if result[-1] == l1[0]:
l1 = l1[1:]
else:
l2 = l2[1:]
# print(result)
self.merge2SortedList(l1, l2, result)
return result
5. 快速排序
也是采用分治思想，每一轮排序后，用一个中间数将数组分为了左右两个部分，
其中左边部分全部比中间数小，右边部分全部比中间数大。
再递归的对左右两个数组调用快速排序，直到递归出口，此时整个数组有序。
def fastSort(self,l,start = None,end = None):
if l is None or len(l) in [0,1] : return l
start = 0 if start == None else start
end = len(l) -1 if end == None else end
#if (end - start) in [0,1] : return
split = l[start]
i,j = start,end
while(i != j ):
while(i != j and l[j] >= split): # 内循环也要带上外循环的条件
j-=1
#self.swap(l,i,j)
while(i != j and l[i] <= split):
i+=1
#self.swap(l,i,j)
l[i],l[j] = l[j],l[i]
l[start],l[i] = l[i],l[start]
if i-start >= 2: # 1也可以 但是单个元素自然有序 没必要排
self.fastSort(l,start,i-1)
if end - i >= 2: # 1也可以 但是单个元素自然有序 没必要排
self.fastSort(l,i+1,end)
return l
6. 希尔排序
插入排序的变种，依次按照从大到小的步长对待排数组的子序列进行插入排序，
最后以1的步长对整个大致有序数组进行一次插入排序，得到有序数组。
def shellSort(self,l,step = None):
if l is None or len(l) in [0,1] : return l
step = len(l)//2 if step is None else step
for i in range(step):
listToInsertSort = [l[j] for j in range(i ,len(l) , step)]
listSorted = self.insertSort(listToInsertSort)
indexOflistSorted = 0
for k in range(i ,len(l) , step):
l[k] = listSorted[indexOflistSorted]
indexOflistSorted += 1
if step >= 2:
self.shellSort(l,step//2)
return l
7. 堆排序
最大堆定义：满足父结点比左右两个子结点都大这一条件的完全二叉树。
将待排数组视为一棵完全二叉树，对其作调整，使其满足（最大）堆定义，
然后每一轮将堆顶结点与堆尾结点对调（相当于将最大值放在数组最后），并将堆的长度-1 。
def heapSort(self,l): # 建立堆，每轮遍历将堆顶节点（最大）
if l is None or len(l) in [0, 1]: return l
self.buildHeap(l)
last = len(l)-1
while last > 0 :
l[0],l[last] = l[last],l[0] # 每轮遍历将堆顶节点（最大）与堆的最后一个结点对调
self.adjustHeap(l, 0, last) # 对调之后需要重新调整
last -= 1 # 将需要调整的堆的长度-1 （此句与上一句不能弄反）
return l
def adjustHeap(self,l,i,limit): # 对堆进行调整，使其满足堆定义
lchild = 2*i +1
rchild = 2*i +2
#if lchild <= len(l)+1:
max = i
if lchild < limit and l[lchild] > l[max]: max = lchild
if rchild < limit and l[rchild] > l[max]: max = rchild
if max != i: # 说明子结点比结点大，需要对调
l[max], l[i] = l[i], l[max]
self.adjustHeap(l, max, limit) # 对调之后无法保证被调到子结点的结点满足堆定义
# 需要继续调整
def buildHeap(self,l): # 建立一个堆
for i in range((len(l))//2)[::-1]: # 从最后一个非叶结点一直到根结点
self.adjustHeap(l,i,len(l)) # 进行堆的调整，使其满足堆定义
8. 基数排序
堆排序的思想是将各个元素从低位到高位依次作比较。
具体实现是在从低位到高位的每一位分别设置10个桶，每个元素的该位数字是几就放入哪个桶。
最后将所有桶中的元素依次取出，再进行下一次装桶，直到最高位。
此时整个数组有序。
def radixSort(self,l):
if l is None or len(l) in [0,1] : return l
posList, negList = self.sliceListToPosAndNeg(l)
sortedPos = self.posRadixSort(posList)
# 先对负值列表的每个元素取相反数，当作正数正常排
# 排完之后 逆序再取相反数 再拼上正值排序后的列表
sortedNeg = [-j for j in self.posRadixSort([-i for i in negList])[::-1]]
return sortedNeg+sortedPos
def posRadixSort(self,l): # 对无符号整数进行堆排序
max = l[0]
for num in l:
if num > max: max = num
times = self.getPositiveBit(max)
for i in range(times):#桶bit次
buckets = [[] for j in range(10)] # 初始化桶
#result = []
for num in l: # 塞桶
bit = (num // 10**i) % 10
buckets[bit].append(num)
flatmappedbuckets = []
for bucket in buckets: # 拍扁桶们
flatmappedbuckets.extend(bucket)
l = flatmappedbuckets
return l
def getPositiveBit(self,num): # 获取一个正整数的位数，即需要的桶的组数。
if num == 0 : return 1
bit = 0
while(num != 0):
bit += 1
num //= 10
return bit
def sliceListToPosAndNeg(self,l): # 将待排数组分为正数数组和负数数组
posList = []
negList = []
for num in l:
if num >= 0: posList.append(num)
else: negList.append(num)
return posList,negList