初始序列：70 8365 10 32 7 9 每次快速排序的结果
A(13)10组有倒数13个和前10个，13个数字取10个随机排序。或：C(13)10 小于13且大于10、这是从13中取10来排序 A(10)10小于10且大于10、即10组合，则C(13)10*A (10)10 =A(13)10/A(10)10*A(10)10=A(...
python中几种经典排序方法的实现
classSortMethod：插入排序的基本操作就是在已经排序好的有序数据中插入一条数据，得到一个新的数字加一的有序数据，该算法适用于对少量数据进行排序，时间复杂度为O(n^2)。是一种稳定的排序方法。
插入算法将要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，除了最后一个元素（让数组多一个空格插入位置）
第二部分只包含这个元素（即要插入的元素）
第一部分排序后，将最后一个元素插入已经排序的第一部分。 definsert_sort(lists):
# I插入排序
count=len(lists)
foriinrange(1,count):
key=lists[i]
j=i-1
whilej>=0:
iflists [j]>key:
lists[j+1]=lists[j]
lists[j]=key
j-=1
returnlists 希尔排序（ShellSort）是插入排序之一、也称为减少增量排序，它是直接插入排序算法的更高效和改进版本。希尔排序是一种非稳定排序算法。该方法得名于当年DL.Shell提出的。
Hill Sorting是将记录按目标的一定增量进行分组，并使用直接插入排序算法对每一组进行排序；随着增量的减小，每组包含越来越多的关键字。当增量减小到 1 时，整个文件如果被分成一组，则算法终止。 defshell_sort(lists):
#hill sort
count=len(lists)
step=2
group=count/step
whilegroup> 0:
foriinrange(0,group) :
j=i+group
whilej
k=j-group
key=lists[j]
whilek>= 0:
iflists[k]>key :
lists[k+group]=lists[k]
lists[k]=key
k-=grou p
j+=group
group/=step
返回列表冒泡排序重复访问要排序的序列，一次比较两个元素，如果它们的顺序错误则交换它们。重复访问序列的工作，直到不再需要交换，即序列已经排序完毕。 defbubble_sort(lists):
#Bubble sort
count=len(lists)
foriinrange(0,count):
forjinrange(i+1,count):
iflists[i] > list[j]:
temp=lists[j]
lists[j]=lists[i]
lists[i]=temp
returnlists快速排序
按一次排序排序数据被分成两个独立的部分，其中一个部分的所有数据都小于另一部分的所有数据，然后按照这种方法分别对两部分数据进行排序。整个排序过程可以递归执行。将整个数据整理成有序序列 defquick_sort(lists,left,right):
#Quick sort
ifleft>=right:
returnlists
key=lists[left]
low=left
high=right
whileleft
whileleft
right-=1
lists[left]=lists[right]
whileleft
left+=1
lists[right]=lists[left]
lists[right]=key
quick_sort(lists,low,left-1)
quick_sort(lists,left+1,high)
returnlists 直接选择排序
第一次，选择要排序的记录中最小的记录r[1]~r[n]，并与r[1] 交换；
第二遍，在要排序的记录中选择最小的记录r[2]~r[n]，与r[2]交换； 超快排关键词排
以此类推，第i遍在r[i]~r[n]待排序的记录中选择最小的记录，与r[i]交换，这样有序序列就会继续增长直到所有的事情都完成。 defselect_sort(lists):
#选择排序
count=len(lists)
foriinrange(0,count):
min=i
超快排关键词排：年度关键词有哪些
forjinrange(i+1,count):
iflists[min]>lists[j]:
min=j
temp=lists[min]
lists[min]=lists[i]
lists[i]=temp
返回列表堆排序（Heapsort）是指利用堆叠树（堆）的数据结构设计的一种排序算法，是一种选择性排序。
可以利用数组的特性快速定位到指定索引处的元素。堆分为大根堆和小根堆，是一棵完全二叉树。大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]]>=A[i]。
在数组的非降序排序中，需要用到大根堆，因为按照大根堆的要求，最大值必须在堆顶。 #调整堆
defadjust_heap(lists,i,size):
lchild=2*i+1
rchild=2*i+2
max=i
ifi
iflchild
max=lchild
ifrchild
max=rchild
ifmax!=i:
lists[max],lists[i]=lists[i],lists[max]
adjust_heap(lists,max,size)
#创建堆
defbuild_heap(lists,size):
foriinrange(0,(size/2))[::-1]:
adjust_heap(lists,i,size)
#heap排序
defheap_sort(lists):
size= len (lists)
build_heap(lists,size)
foriinrange(0,size)[::-1]:
lists[0],lists[i]=lists[i],lists[0 ]
adjust_heap(lists,0,i) 归并排序是一种基于归并操作的有效排序算法。该算法是使用分治法（DivideandConquer）的一个非常典型的应用。将已有的有序子序列组合起来，得到一个完全有序的序列；即先把每个子序列按顺序做，然后再按顺序做子序列。如果将两个有序列表合并为一个有序列表，则称为双向合并。
合并过程为：
比较a[i]和a[j]的大小，如果a[i]≤a[j]，则将第一个有序列表中的元素a[i]转化为r [k] 并分别给 i 和 k 加 1；
否则，将第二个有序列表中的元素 a[j] 变成 r[k]，并将 j 和 k 分别加到 1 上，循环继续直到其中一个有序列表完成，然后将剩余的元素在另一个有序列表被复制到 r 中从下标 k 到下标 t 的单元。归并排序的算法通常是通过递归实现的。首先将要排序的区间[s,t]用中点一分为二、然后对左子区间进行排序，再对右子区间进行排序，最后将左右区间合并一次。合并为有序区间 [s,t]。 defmerge(left,right):
i,j=0,0
result=[]
whilei
ifleft[i]<=right [j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j+=1
result+= left[i:]
result+=right[j:]
returnresult
defmerge_sort(lists):
#Merge sort
iflen(lists)<=1:
returnlists
num=len(lists)/2
left=merge_sort(lists[:num])
right=merge_sort(lists[num:])
returnmerge(left,right)“分布排序”中的基数排序(distributionsort)，也称为“bucketsort”或binsort，顾名思义，就是通过key值的部分信息，将要排序的元素分配到一定的“bucket”中来达到排序的作用，基数排序是一种排序的稳定性。
它的时间复杂度是 O(nlog(r)m)，其中 r 是所取的基数，m 是堆的数量。在某些情况下，基排序的效率高于其他稳定排序方法。 importmath
defradix_sort(lists,radix=10):
k=int(math.ceil(math.log(max(lists),radix)))
bucket=[[]foriinrange(radix)]
foriinrange(1,k+1):
forjinlists:
bucket[j/(radix**(i-1))%(radix**i)].append(j)
dellists[:]
forzinbucket:
lists+=z
delz[:]
returnlists
--------------------
作者：CRazyDOgen
来源：CSDN
版权声明：本文为博主原创。转载请附上博文链接！
初始序列：70 8365 10 32 7 9 每次快速排序的结果
