数据结构常用排序算法

╰+哭是因爲堅強的太久メ 2023-05-31 12:18 7阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td>排序算法</td> 
   <td>时间复杂度（平均）</td> 
   <td style="width:184px;">空间复杂度</td> 
   <td style="width:124px;">是否稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td><img alt="O(n^2)" src="https://private.codecogs.com/gif.latex?O%28n%5E2%29"></td> 
   <td style="width:184px;"><img alt="O(1)" src="https://private.codecogs.com/gif.latex?O%281%29"></td> 
   <td style="width:124px;">不稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td><img alt="O(n^\frac{3}{2})" src="https://private.codecogs.com/gif.latex?O%28n%5E%5Cfrac%7B3%7D%7B2%7D%29"></td> 
   <td style="width:184px;"><img alt="O(1)" src="https://private.codecogs.com/gif.latex?O%281%29"></td> 
   <td style="width:124px;">不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td><img alt="O(n^2)" src="https://private.codecogs.com/gif.latex?O%28n%5E2%29"></td> 
   <td style="width:184px;"><img alt="O(1)" src="https://private.codecogs.com/gif.latex?O%281%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td><img alt="O(nlog_{2}n )" src="https://private.codecogs.com/gif.latex?O%28nlog_%7B2%7Dn%20%29"></td> 
   <td style="width:184px;"><img alt="O(1)" src="https://private.codecogs.com/gif.latex?O%281%29"></td> 
   <td style="width:124px;">不稳定</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td><img alt="O(n^2)" src="https://private.codecogs.com/gif.latex?O%28n%5E2%29"></td> 
   <td style="width:184px;"><img alt="O(1)" src="https://private.codecogs.com/gif.latex?O%281%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td><img alt="O(nlog_{2}n )" src="https://private.codecogs.com/gif.latex?O%28nlog_%7B2%7Dn%20%29"></td> 
   <td style="width:184px;"><img alt="O(nlog_{2}n )" src="https://private.codecogs.com/gif.latex?O%28nlog_%7B2%7Dn%20%29"></td> 
   <td style="width:124px;">不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td><img alt="O(nlog_{2}n )" src="https://private.codecogs.com/gif.latex?O%28nlog_%7B2%7Dn%20%29"></td> 
   <td style="width:184px;"><img alt="O(n)" src="https://private.codecogs.com/gif.latex?O%28n%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td><img alt="O(n+k)" src="https://private.codecogs.com/gif.latex?O%28n&amp;plus;k%29"></td> 
   <td style="width:184px;"><img alt="O(n+k)" src="https://private.codecogs.com/gif.latex?O%28n&amp;plus;k%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td><img alt="O(n+k)" src="https://private.codecogs.com/gif.latex?O%28n&amp;plus;k%29"></td> 
   <td style="width:184px;"><img alt="O(n)" src="https://private.codecogs.com/gif.latex?O%28n%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td><img alt="O(n*k)" src="https://private.codecogs.com/gif.latex?O%28n*k%29"></td> 
   <td style="width:184px;"><img alt="O(n*k)" src="https://private.codecogs.com/gif.latex?O%28n*k%29"></td> 
   <td style="width:124px;">稳定</td> 
  </tr> 
 </tbody> 
</table>

# #

## 冒泡排序 ##

def bubble_sort(test_list):
        for i in range(len(test_list)):
            for j in range(i,len(test_list)):
                if test_list[i]>test_list[j]:
                    test_list[i],test_list[j]=test_list[j],test_list[i]
        return test_list
    
    test_list=[3,10,7,1,3,5,6,2,6]
    print(bubble_sort(test_list))

## 计数排序 ##

def count_sort(test_list):
        n=len(test_list)
        res=[0 for i in range(n)]
        for item in test_list:
            count=0
            for item1 in test_list:
                if item1<item:
                    count+=1
            while res[count]!=0:
                count+=1
            res[count]=item
        return res
    
    test_list=[3,10,7,1,3,5,6,2,6]
    #[1, 2, 3, 3, 5, 6, 6, 7, 10]
    print(count_sort(test_list))

## 插入排序 ##

def insert_sort(test_list):
        n=len(test_list)
        for i in range(n):
            j=i-1
            p=test_list[i]
            while j>=0 and p<test_list[j]:
                test_list[j+1]=test_list[j]
                j-=1
            test_list[j+1]=p
        return test_list
    
    test_list=[3,10,7,1,3,5,6,2,6]
    print(insert_sort(test_list))

## 快速排序 ##

def quick_sort(test_list):
        if len(test_list)==0 or len(test_list)==1:
    	    return test_list
        left=[]
        right=[]
        p=test_list[0]
        for i in range(1,len(test_list)):
        	if p<test_list[i]:
        		right.append(test_list[i])
        	else:
        		left.append(test_list[i])
        return quick_sort(left)+[p]+quick_sort(right)
    
    test_list=[3,10,7,1,3,5,6,2,6]
    print(quick_sort(test_list))

## 选择排序 ##

def select_sort(test_list):
        n=len(test_list)
        min_index=-1
        for i in range(n):
            min_index=i
            for j in range(i+1,n):
                if test_list[j]<test_list[min_index]:
                    min_index=j
            test_list[i],test_list[min_index]=test_list[min_index],test_list[i]
        return test_list
    
    test_list=[3,10,7,1,3,5,6,2,6]
    print(select_sort(test_list))

## 希尔排序 ##

def shell_sort(test_list):
        n=len(test_list)
        gap=n//2
        while gap>=1:
            for i in range(gap,n):
                j=i
                while j>=gap and test_list[j-gap]>test_list[j]:
                    test_list[i-gap],test_list[j]=test_list[j],test_list[j-gap]
                    j-=gap
            gap=gap//2
        return test_list
    
    test_list=[3,10,7,1,3,5,6,2,6]
    print(shell_sort(test_list))