python实现交换排序

灰太狼 2022-11-01 00:59 84阅读 0赞

**冒泡排序**  
基本思想：假设待排序表长为n，从后往前或者从前往后两两比较相邻元素的值，若为逆序则交换它们，直到序列比较完。  
每趟冒泡的结果是把待排序序列中的最小元素放到了序列的最终位置，这样最多n-1趟就可以把所有元素排好序。  
![在这里插入图片描述][20210324141338698.gif_pic_center]

def BubbleSort(A):
        le=len(A) #获取元素数目
        for i in range(le-1):#遍历le-1次
            for j in range(i,le):#每一趟冒泡，待排序元素数目都会-1
                if A[j]>A[j-1]:#逆序则交换
                    A[j-1],A[j]=A[j],A[j-1]
            print(A)
    
    tes=[23,34,243,1,28,7,56]
    BubbleSort(tes)

输出为：

[34, 243, 23, 28, 7, 56, 1]
    [243, 34, 28, 23, 56, 7, 1]
    [243, 34, 28, 56, 23, 7, 1]
    [243, 34, 56, 28, 23, 7, 1]
    [243, 34, 56, 28, 23, 7, 1]
    [243, 34, 56, 28, 23, 7, 1]

空间效率：使用了常数个辅助单元，因而空间复杂度为O(1)  
时间效率：O(n²)  
它是一种稳定的排序算法。

**快速排序**  
基本思想：基于分治法，在待排序表L\[1…n\]中任取一个元素pivot作为基准，通过一趟排序将排序表划分为独立的两部分L\[1…k-1\]和L\[k+1…n\].使得L\[1…k-1\]中所有元素<privot，L\[k+1…n\]中所有元素>=privot,privot放在它的最终位置L\[k\]，这个过程为一趟快速排序。  
然后分别递归地对两个子表重复上述过程，直到每部分只有一个元素或者为空为止，即所有元素都放在了其最终位置。  
![在这里插入图片描述][20210324141252884.gif_pic_center]

def quick_sort(alist, start, end):
        if start >= end:
            return
        low = start
        high = end
        mid = alist[low]
        
        while low < high:
            while low < high and mid < alist[high]:
                # 从右边开始找，如果元素小于基准，则把这个元素放到左边
                high -= 1
            alist[low] = alist[high]
            
            while low < high and mid > alist[low]:
                # 从左边开始找，如果元素大于基准，则把元素放到右边
                low += 1
            alist[high] = alist[low]
        
        # 循环退出，low==high，把基准元素放到这个位置
        alist[low] = mid
        
        # 递归调用，重新排列左边的和右边的序列
        quick_sort(alist, start, low-1)
        quick_sort(alist, low+1, end)

空间效率：由于排序算法是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。空间复杂度最坏情况为O(n)，平均情况为O(log2 N)  
时间效率：最坏为O(n²)；最好为O(nlog2 N)  
它是一种不稳定的排序算法。

[20210324141338698.gif_pic_center]: /images/20221024/46e87cf6dc4b49c28fcc49219e0b225a.png
[20210324141252884.gif_pic_center]: /images/20221024/7835a5c4df1b47f883ffb90bff1cbd02.png