基本排序算法的python 实现

﹏ヽ暗。殇╰゛Y 2022-05-22 00:10 165阅读 0赞

（1）冒泡排序

def bubble_sort(arr):
        length = len(arr)
        for index in range(length):
            for j in range(length-index):
                if arr[j-1]>arr[j]:
                    #交换位置
                    arr[j-1],arr[j]=arr[j],arr[j-1]
                return arr

带有标志位的冒泡排序

def bubble_sort(arr):
        length = len(arr)
        for index in range(length):
            flag = true
            for j in range(length-index):
                if arr[j-1]>arr[j]:
                    arr[j-1],arr[j]=arr[j],arr[j-1]
                    flag=false
            if flag:
                return arr
        return arr

(2)插入排序

def insert_sort(arr):
        n= len(arr)
        for i in range(1,n):
            #后一个元素和前一个元素相比较，
            #如果比前一个元素小，则将其取出，并保存下标
            if arr[i]<arr[i-1]:
                temp = arr[i]
                index = i
                # 从后往前依次比较没个元素，和比取出元素大的元素交换
                for j in range(i-1,-1,-1):
                    if arr[j]>temp:
                        arr[j+1]=arr[j]:
                        index = j
                    else:
                        break
                arr[index]=temp
            return arr

(3)计数排序  
计数排序法：计数数组适用于当前数组密集的情况。  
例如(2,3,5,4,2,3,3,2,5,4)

方法：先找出最大值最小值，之后统计每个数出现的次数，根据次数从小到大往数组里添加

计数排序法是一种不需要比较的排序方法

def count_sort(arr):
        min_num = 2147483647
        max_num = 0
        # 第一步 取得最大值和最小值
        for x in arr:
            if x < min_num:
                min_num = x
            if x > max_num:
                max_num = x
        # 创建数组C
        count = [0] * (max_num - min_num +1)
        for index in arr:
            count[index - min_num] += 1
        index = 0
        for a in range(max_num - min_num+1):
            for c in range(count[a]):
                arr[index] = a + min_num
                index += 1
        return arr

（4）快速排序

def quick_sort(arr):
        less = []
        pivot_list = []
        more = []
        # 递归出口
        if len(arr) <= 1:
            return arr
        else:
            #将第一个值作为基准
            pivot = arr[0]
            for i in arr:
                #将比基准值小的放在less数列
                if I<pivot:
                    less.append(i)
                #将比基准值大的放在more数列
                elif I>pivot:
                    more.append(i)
                #将和基准值相同的数值保存在基准数列
                else：
                    pivot_list.append(i)
                #分别对less数列和more数列进行排序
                less = quick_sort(less)
                more = quick_sort(more)
                return less+pivot_list+more
    def quick_sort_cookbook(arr):
        if len(arr)<=1:
            return arr
        else:
            pivot = arr[0]
            return quick_sort_cookbook([x for x in arr[1:] if x<pivot])+[pivot]+quick_sort_cookbook([x for x in arr[1:] if x>=pivot])

(5) 归并排序

def merge_sort(arr):
        #认为长度不大于一的序列是有序的
        if len(arr)<=1:
            return arr
        #二分列表
        middle = len(arr)//2
        left = merge_sort(arr[:middle])
        right = merge_sort(arr[middle:])
        #最后一次合并
        return merge(left,right)
    
    #合并
    def merge(left,right):
        l,r =0,0
        result = []
        #两个子数列比较大小,比较两个序列的第一个元素，谁小，就放在序列后面
        while l<len(left) and r<len(right):
            if left[l]<right[r]:
                result.append(left[l])
                l+=1
            else:
                result.append(right[r])
                r+=1
            #填充结果
            result +=left[l:]
            result += right[r:]
            return result

（6）堆排序  
实现堆排序需要解决两个问题：

1.如何由一个无序序列建成一个堆？

2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

先考虑第二个问题，一般在输出堆顶元素之后，视为将这个元素排除，然后用表中最后一个元素填补它的位置，自上向下进行调整：首先将堆顶元素和它的左右子树的根结点进行比较，把最小的元素交换到堆顶；然后顺着被破坏的路径一路调整下去，直至叶子结点，就得到新的堆。

我们称这个自堆顶至叶子的调整过程为“筛选”。

从无序序列建立堆的过程就是一个反复“筛选”的过程。

def heap_sort(arr):
        #创建最大堆
        for start in range((len(arr)-2)//2,-1,-1):
            sift_down(arr,start.len(arr)-1)
        #堆排序
        for end in range(len(arr)-1,0,-1):
            arr[0],arr[end] = arr[end],arr[0]
            sift_down(arr,0,end-1)
        return arr
    # 最大堆调整
    def sift_down(arr,start,end):
        root=start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

(7)选择排序

def selection_sort():
        n=len(arr)
        for I in range(0,n):
            #获取最小元素
            min_num = i
            # 遍历未排序元素
            for j in range(I+1,n):
                #找到一个比最小元素小的元素
                if arr[j]<arr[min_num]:
                min_num=j
            arr[min_num],arr[I]=arr[i],arr[min_num]
        return arr

(8)希尔排序  
希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。  
排序过程：先取一个正整数d1

def shell_sort(arr):
        n=len(arr)
        #初始步长
        gap=n//2
        while gap>0:
            for I in range(gap,n):
                temp = arr[i]
                j=i
                while j>=gap and arr[j-gap]>temp:
                    arr[j] = arr[j-gap]
                    j-=gap
                arr[j]=temp
            #得到新的步长
            gap=gap//2
        return arr