选择排序

1.原理：是一种简单直观的排序算法。原理是，将后面的元素最小元素一个个取出来然后按顺序放置。

2.步骤：

　　1.在未排序序列中找到最小元素，存放到排序序列的起始位置。

　　2.在从剩余未排序元素中继续寻找最小元素，然后放到已排序列的末尾。

　　3.重复第二步，直到所有元素都排列完毕。

3.代码：

 

def selection_sort(li):    n=len(li)　　　　#获取li长度    for i in range (0,n):　　#进行比较的轮数        min=i　　　　#默认为最小值        for j in range(i+1,n):　　#j为列表下标，如果找到比当前值小的值，则两者交换            if li[j]

　　

 

 

堆排序：(一般用数组存储）

1.思想：堆是一种数据结构，可以将堆看作一颗完全二叉树，这颗二叉树满足，任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值。将一个无序序列调整为一个堆，

　　　　就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换到序列的最后一个，这样有序序列就元素增加一个，无序序列元素就减少一个。对新的无序序列重复

　　　　这样的操作，就实现了排序。

2.执行过程：

　　1.从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从上至下，对每个节点进行调整，最终将得到一个大顶堆。

　　　　对节点的调整方法：将当前节点（假设为a）的值与其孩子节点进行比较，如果存在大于a的值的孩子节点，则从中选出最大的一个与a交换。当a来到下一层的时候，重复

　　　　　　　　　　　　　上述过程，直到a的孩子节点的值都小于a为止。

　　2.将当前无序序列的第一个元素（反应在数中的根节点b），与无序序列的最后一个元素交换（假设为c），b进入有序序列，到达最终位置。无序序列元素减少一个，有序序列元素

　　　增加一个，此时只有节点c可能不满足堆的定义，对其进行调整。

　　3.重复2的过程，直到无序序列的元素剩下一个时排序结束。

　　　

堆排序适应于记录数很多的情况下

代码：　

def sift_down(array,start,end):    while True:                #当列表第一个是以下标0开始，节点下标为i，左孩子下标则为2*i+1，右孩子下标                                      为2i+2,若下标以1开始，左孩子则为2*i，右孩子则为2*i+1        left_child=2*start+1    #左孩子节点下标            if left_child>end:        #当节点的右孩子存在，且大于节点的左孩子            break            if left_child+1<=end and array[left_child+1]>array[left_child]:            left_child += 1        if array[left_child]>array[start]:    #当左孩子的的最大值大于父节点时，则交换            array[left_child],array[start]=swap(array[left_child],array[start])            start=left_child        #交换之后以交换子节点为根的堆可能不是大顶堆，需重新调整        else:                        #若父节点大于左右孩子，则跳出循环            breakdef heap_sort(array):    #堆排序    first=len(array)//2-1    #最后一个有孩子的节点（//表示取整的意思）    #第一个节点的下标为0，也可以为1，随便定。    for i in range (first,-1,-1):    #从最后一个有孩子的节点往上调整        print(array[i])        sift_down(array,i,len[array]-1    #初始化大顶堆    print(“初始化大顶堆的结果：”，array)    for head_end in range (len[array]-1,0,-1):        array[head_end],array[0]=array[0],array[head_end]        #交换堆顶与堆尾        sift_down(array,0,head_end-1)