数据结构--排序算法（理解+实现）

Dear 丶 2023-01-03 12:50 66阅读 0赞

# 数据结构排序算法 #

排序算法有很多，下文列出常见排序算法的理解与实现（持续更新~）

*  排序算法名称-时间复杂度-空间复杂度
 *  
 *  冒泡排序-o（n²）,o(1)
 *  选择排序-o（n²）,o(1)
 *  插入排序-o（n²）,o(1)
 *  希尔排序-o（nlogn）,o(1)
 *  快速排序-o（nlogn）,o(logn) （★）
 *  归并排序-o（nlogn）,o(n)
 *  计数排序-o（n+k），o（n+k）

1.  冒泡排序：  
    从前往后遍历，比较相邻两个数值大小并将大值放在后边（交换位置），一次遍历使得最大值放在了最后一位；进行n-1次冒泡遍历~选出每次的最大值放到后边

def bubble_sort(alist):
    	n=len(alist)
    	for j in range(n-1):
    		count =0   #使用count计数，实现最优复杂度o(n)
    		for i in range(n-1-j):
    			if alist[i]>alist[i+1]:
    				alist[i],alist[i+1]=alist[i+1],alist[i]
    				count+=1
    		if count ==0:
    			return alist
    	return alist
    #测试：
    if __name__=="__main__":
        li=[54,26,93,17,77,31,44,55,20]
        print(li)
        bubble_sort(li)
        print(li)

1.  选择排序：  
    将列表分为有序与无序两部分，每次遍历从无序数组中找到最小值，添加到有序数组中（使用与无序数组第一个值交换位置的方式添加）（有序数组起始为空）

def selection_sort(alist):
    	'''选择排序'''
    	n = len(alist)
    	for i in range(n-1):
    		min_index=i
    		for j in  range(i+1,n):
    			if alist[j]<alist[min_index]:
    				min_index=j
    		alist[i],alist[min_index]=alist[min_index],alist[i]
    	return alist

1.  插入排序：  
    将列表提前分为有序与无序部分（有序部分起始为首位元素），然后将无序数组的第一位元素从后往前与有序数组元素比较，若无序首位元素大，则交换位置，持续比较直至找到该元素在有序数组中的位置。依次遍历无序数组，找到所有元素的插入位置。

def insert_sort(alist):
    	n=len(alist)
    	for i in range(1,n):
    		index=i
    		while index>0:
    			if alist[index]<alist[index-1]:
    				alist[index-1],alist[index] = alist[index],alist[index-1]
    				index-=1
    			else:  #提前停止
    				break
    	return alist

1.  希尔排序  
    给定gap，将数据分组，每隔gap步长的元素分为一组，对于每一组都使用插入排序。一次排序后，将gap//2，再次分组插入排序，直至gap为1

def shell_sort(alist):
    	n=len(alist)
    	gap=n//2
    	while gap>=1:
    		for i in range(gap,n):
    			index=i
    			while index>=gap:
    				if alist[index]<alist[index-gap]:
    					alist[index],alist[index-gap] = alist[index-gap],alist[index]
    					index-=gap
    				else:
    					break
    		gap//=2
    	return alist

1.  快速排序  
    在一次遍历中，找到第一个值在列表中的位置并交换过去，该位置左侧的值都比该值小，右侧都比该值大。找到位置后，再将该位置左右两侧分割开，分别再进行快速排序，直至分割开的只剩一个元素。

def quick_sort(alist,first,last):
    	if first >=last:
    		return alist
    	mid_value = alist[first]
    	low = first
    	high = last
    	while low<high:
    		while low<high and alist[high]>=mid_value:
    			high-=1
    		alist[low]=alist[high]
    
    		while low<high and alist[low]<mid_value:
    			low+=1
    		alist[high] = alist[low]
    	alist[low] = mid_value
    	quick_sort(alist,first,low-1)
    	quick_sort(alist,low+1,last)

1.  归并排序  
    先“归”，将列表元素二分，划分为一个一个单个元素，然后再将单个元素进行合并。单层合并时，将左右两边的序列中元素按大小进行排序并存储到额外的空间。然后再依次向上合并。  
    单层合并时：使用两个指针分别指向左右两个序列首元素，然后依次取出小值放在额外空间内。

def merge_sort(alist):
    	n=len(alist):
    	if n<=1:return alist
    	mid = n//2
    
    	left_li=merge_sort(alist[:mid])
    	right_li=merge_sort(alist[mid:])
    	
    	left_point,right_point = 0,0
    	result=[]
    	while left_point<len(left_li) and right_point<len(right_li):
    		if left_li[left_point]<right_li[right_point]:
    			result.append(left_li[left_point])
    			left_point+=1
    		else: 
    			result.append(right_li[right_point])
    			right_point+=1
    	result+=left_li[left_point:]
    	result+=right_li[right_point:]
    	
    	return result

1.  计数排序  
    计数排序是指，创建长度为最大值+1的数组，然后将新数组中的下标作为原数组中的值，新数组中的值代表原数组中值的出现次数  
    注意：如果原数组中出现有负值，也可将数组长度变为max-min+1，最后输出时再加上min

def count_sort(alist):
        #找到最大值
        max=0
        for j in range(len(alist)):
            if alist[j]>max:
                max=alist[j]
        ans=[0]*(max+1)  #构建计数数组(0~max)，下标代表原数组值
        #ans=[0]*(max-min+1)
        res=[]
        for i in alist:
            ans[i]+=1
        for j in range(len(ans)):
            while ans[j]>0:
                res.append(j)
                ans[j]-=1
        return res