python实现排序的几种算法

概述#1.选择排序：循环找最小值，依次放在左侧defselect_sort(arr):foriinrange(len(arr)-1):min_index=iforjinrange(i+1,len(arr)):ifarr[j]<arr[min_index]:min_index=jifi!=min_index:

# 1. 选择排序：循环找最小值，依次放在左侧def select_sort(arr):    for i in range(len(arr)-1):        min_index = i        for j in range(i+1, len(arr)):            if arr[j] < arr[min_index]:                min_index = j        if i != min_index:            # 交换两个元素位置            arr[i], arr[min_index] = arr[min_index], arr[i]    return arr# 2. 冒泡排序# 和插入排序相同点: 都是循环比较相邻的两个元素# 不同点：每次循环只会和后面的一个元素比大小，不会和前面的元素比较# 特点: 每次循环把最大值依次放在后面def bubble_sort(arr):    for i in range(1, len(arr)):        for j in range(0, len(arr)-i):            if arr[j] > arr[j+1]:                arr[j], arr[j+1] = arr[j+1], arr[j]    return arr# 3. 插入排序：# 循环比较相邻的两个元素，小的放左边；如果交换后发现左侧还有小元素，继续交换位置def insert_sort(arr):    for i in range(len(arr)):        pre_index = i - 1        current = arr[i]        while pre_index >= 0 and arr[pre_index] > current:            arr[pre_index+1] = arr[pre_index]            pre_index -= 1        arr[pre_index+1] = current    return arr# 4. 希尔排序，插入排序的升级def shell_sort(arr):    Meta = 2    n = len(arr)    gap = int(n // Meta)    while gap > 0:        for i in range(gap, n):            current = arr[i]            j = i - gap            while j >= 0 and arr[j] > current:                arr[j+gap] = arr[j]                j -= gap            arr[j+gap] = current        gap = int(gap//Meta)    return arr# 5. 快速排序def quick_sort(arr):    if len(arr) <= 1:        return arr    pivot = arr[-1]  # 取最后一个数作为pivot    i = 0  # i记录比pivot小的数的个数    j = 0  # j用来遍历整个数列    n = len(arr)    while j < n-1:        if arr[j] < pivot:   # 比pivot小的放前面            arr[i], arr[j] = arr[j], arr[i]            i += 1        j += 1    arr[i], arr[-1] = arr[-1], arr[i]    if i > 0:        # 比pivot小的数据不为空， 则对其进行快速排序        arr[:i] = quick_sort(arr[:i])    if i+1 < n:        # 比pivot大的数据不为空， 则对其进行快速排序        arr[i+1:] = quick_sort(arr[i+1:])    return arr# 6. 归并排序def mergeSort(arr):    if len(arr) < 2:        return arr    mIDdle = len(arr) // 2    left, right = arr[0:mIDdle], arr[mIDdle:]    return merge(mergeSort(left), mergeSort(right))def merge(left, right):    result = []    while left and right:        if left[0] <= right[0]:            result.append(left.pop(0))        else:            result.append(right.pop(0))    while left:        result.append(left.pop(0))    while right:        result.append(right.pop(0))    return result# 7. 堆排序, 理解视频：https://www.bilibili.com/vIDeo/BV1Eb41147dK?from=search&seID=4983284716020974089def heAPIfy(arr, n, i):    largest = i    l = 2 * i + 1  # left = 2*i + 1    r = 2 * i + 2  # right = 2*i + 2    if l < n and arr[i] < arr[l]:        largest = l    if r < n and arr[largest] < arr[r]:        largest = r    if largest != i:        arr[i], arr[largest] = arr[largest], arr[i]  # 交换        heAPIfy(arr, n, largest)def heapSort(arr):    n = len(arr)    # Build a maxheap.    for i in range(n, -1, -1):  # 递减的时候，第2个值-1表示到0结束，包括0        heAPIfy(arr, n, i)        # 一个个交换元素    for i in range(n - 1, 0, -1):        arr[i], arr[0] = arr[0], arr[i]  # 交换        heAPIfy(arr, i, 0)    return arr# 8.计数排序# https://blog.csdn.net/weixin_43790276/article/details/107398262def counting_sort(arr):    if len(arr) < 2:        return arr    max_num = max(arr)    count = [0] * (max_num + 1)  # 新建一个计数列表，长度为待排序列表最大值加1。    for num in arr:        count[num] += 1  # 把待排序元素值当作count列表的下标，计算每个待排序元素重复的次数    new_arr = List()    for i in range(len(count)):        for j in range(count[i]):  # count[i]就是count列表中元素i重复的次数            new_arr.append(i)    return new_arr# 9 基数排序# Coding=utf-8def radix_sort(array):    # 找出带排序元素最大数有几位    max_num = max(array)    place = 1    while max_num >= 10**place:        place += 1    for i in range(place):        # 当i=0时，找个位的基数都有哪些；当i=1时，找十位的基数都有哪些        buckets = [[] for _ in range(10)]        for num in array:            radix = int(num/(10**i) % 10)            buckets[radix].append(num)        # 按基数对元素进行排序        j = 0        for k in range(10):            for num in buckets[k]:                array[j] = num                j += 1    return arraya = [1, 4, 9, 3, 5]# x = bubble_sort(a)#x = mergeSort(a)#x = heapSort(a)x = counting_sort(a)print(x)

 

总结

以上是内存溢出为你收集整理的python实现排序的几种算法全部内容，希望文章能够帮你解决python实现排序的几种算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。