python实现的几种排序算法

深碍√TFBOYSˉ_ 2022-06-11 06:19 211阅读 0赞

# 排序算法 #

## 插入排序 ##

'''
    此算法为插入排序中的
    直接插入排序
    当然这是对于n很小的情况，但是当n很大的时候，可以用折半插入
    
    就是对于直接插入排序的一个改进，对于前一个序列用直接插入排序
    后面就不用这样了，因为前面已经是一个有序序列，可以折半方式提高
    查询效率
    
    '''
    a=[]
    b=None
    #插入列表
    insert_list=[7,3,5,67,3,6,8]
    #插入的数
    #扩展列表
    N=None
    def expand_list():
    	# for i in range(1,join_nuber):
    		a.append(b)
    #得到要插入的数据
    def insert_number(insert_list):
    		return insert_list.pop()
    #得到插入的位置
    def position(N):
    	min=N
    	i=0
    	while True:
    		if( i<(len(a)-1) and min<=a[i]):
    			j=i
    			return j
    		i=i+1
    		if(i==(len(a)-1)):
    			return len(a)-1
    
    #数据插入
    def insert(a,insert_list):
    	while (len(insert_list)!=0):
    
    		N=insert_number(insert_list)
    		print("this moment the value of N",N)
    		print("a",a)
    		if (len(a)==0):
    			expand_list()
    			a[0]=N
    		else:
    			expand_list()
    			print("a",a)
    			print("len a",len(a))
    			print("position",position(N))
    			for i in range(0,len(a)-position(N)-1):
    				a[len(a)-1-i]=a[len(a)-2-i]
    			a[position(N)]=N
    				
    
    insert(a,insert_list)
    print(a)#测试代码

## 选择排序 ##

\#选择排序  
'''  
选择排序就是每一次找出最小的那个数  
然后和第一个数交换位置  
  
'''  
\# a=\[3,4,8,6,3,4,5\]  
  
\# def select\_sort(lists):  
\# \# 选择排序  
\# count = len(lists)  
\# for i in range(0, count):  
\# min = i  
\# for j in range(i + 1, count):  
\# if lists\[min\] > lists\[j\]:  
\# min = j  
\# \#在Python中不需要三方参数来实现两个数的交换  
\# lists\[min\], lists\[i\] = lists\[i\], lists\[min\]  
\# return lists

## 起泡排序 ##

'''  
起泡排序，通过两两比较  
每次找出最大的放在末尾  
  
'''  
\# def bubble\_sort(lists):  
\# \# 冒泡排序  
\# count = len(lists)  
\# for i in range(0, count):  
\# for j in range(i + 1, count):  
\# if lists\[i\] > lists\[j\]:  
\# lists\[i\], lists\[j\] = lists\[j\], lists\[i\]  
\# return lists

## 堆排序 ##

\#堆排序  
'''  
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值  
  
堆排序通过每次找出堆顶元素，来实现排序  
'''

a=[3,20,9,6]
    def adjust_heap(lists, i, size):
        lchild = 2 * i + 1
        rchild = 2 * i + 2
        max = i
        print("adjust_heap")
        if i < size / 2:
            if lchild < size and lists[lchild] > lists[max]:
                max = lchild
            if rchild < size and lists[rchild] > lists[max]:
                max = rchild
            if max != i:
                lists[max], lists[i] = lists[i], lists[max]
                print(lists)
                adjust_heap(lists, max, size)
    
    def build_heap(lists, size):
        for i in range(0, int(size/2))[::-1]:#此处代码的[::-1]的意思就是从高到低循环，i的值是从最大开始取
            adjust_heap(lists, i, size)
             
    def heap_sort(lists):
        size = len(lists)
        build_heap(lists, size)
        for i in range(0, size)[::-1]:
            lists[0],lists[i]=lists[i],lists[0] #此代码的作用是将第一个（即堆顶元素放到最后面，）剩下的元素再进行堆排序
    #直到取出所有堆顶元素，就完成了排序            
            adjust_heap(lists, 0, i)
    
    heap_sort(a)
    print(a)

\#测试代码

到此也差不多了，希望同学们能好好理解一下堆排序，不要觉得难就放弃。生活亦是如此。