插入排序 谢尔排序 归并排序以及 快速排序

插入排序 谢尔排序 归并排序以及 快速排序

插入排序 谢尔排序 归并排序以及 快速排序

插入排序Insertion Sort

第一趟 子列表仅包含第一个数据项 将第二个数据项 当作新项放到子列表的合适位置，这样已排序的子列表就包含了两个数据项

第二趟 再继续将第三个数据项 与前两个数据项进行对比 并移动比自身大的数据项，空出位置来 ，以便加到子列表中

经过n-1套对比和插入，子列表扩展到全表 排序完成

数量级 与最差情况 每一个 可能都进行对比，所以数量级O（n^2)

最好情况，列表已经排好序，每趟仅需要 一次对比 总数量级 O（n)

 def insertSort(alist):for index in range(1,len(alist)):currentvalue= alist[index]position = indexwhile position >0 and alist[position-1] > currentvalue:alist[position] = alist[position-1]position = position-1alist[position] = currentvalue#

谢尔排序 就是将间隔 进行减少 然后进行排序

间隔有说时n/2开始 每趟倍增 n/4 n/8 …直到1
随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数

间隔为3的子列表，子列表分别插入排序后的整体状况更接近有序

间隔逐渐减少，直到为1时 也就是最后一趟标准的插入排序

def shellSort(alist):Jiange= len(alist)//2while  Jiange > 0:for  startposition in range(Jiange):InsertSort(alist,startposition,Jiange)print("After increment")Jiange = Jiange//2
def InsertSort(alist,start,gap):
for i in range(start +gap,len(alist),gap):
current = alist[i]position= i
while position >= gap and alist[position-gap] >current:
alist[position] = alist[position-gap]
position = position -gapalist[position] = current // shell

粗看上去 谢尔排序以插入排序为基础，可能并不会比插入排序好

但由于每趟 都会使得 列表更加接近有序这过程会减少很多原先许哟啊的
无效比对
对谢尔排序的详尽分析比较负责 大致说时介于O（n) 和O（n2) 之间

MergeSort 归并排序

def merge_sort(alist):
if len(alist) <=1:return alist
middle = len(alist) //2  #二分法 
left = merge_sort( alist[:middle])
right = merge_sort( alist[middle:])# 合并左右半部，完成排序merged =[]
while left and right:
if left[0] <right[0]:
merged.append(left.pop[0])
merged.append(right.pop[0])
d(right if right else left)
return merged

归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别及逆行归并排序

快速排序

分解 分裂 对每一部分 在对中间的递归排列
数据表中间的中位值 计算开销

递归排序 三要素

1）基本结束条件: 数据表仅有一个数据项，自然是排好序的
2）缩小规模 : 根据种植，将数据表分为两半，最好情况时相等规模的两半
3) 调用自身: 将两半分别调用自身进行排序( 排序基本操作在分裂过程中)

分裂数据表的目标：找到"中值"的位置
分裂数据表的手段

设置左右标（left/rightmark 

坐标向右移动，右标向左移动

• 左标一直向右移动，碰到比中值大的就停止
  *右标一直向左移动，碰到比中值小的就停止
  *然后把左右标所指的数据项交换

继续移动，直到左标移到右标的右侧，停止移动，这时右标所知位置就是中值应处的位置
将中值和这个位置交换

分裂完成，左半部比中指小，右半部比中值大