老男孩教育专注IT教育10余年,只培养IT技术精英

全国免费咨询电话(渠道合作):400-609-2893

如何用Python实现经典排序算法?老男孩python自学视频

老男孩IT教育

行业新闻

2022年11月29日 09:27

排序算法是最基本的算法之一,不论是在面试还是实际编程中,都会或多或少的使用到排序算法,常见的应用场景有排行榜、好友列表、商品排序等,本文给大家介绍10种常见的内部排序算法,以下是详细的内容:

       排序算法是最基本的算法之一,不论是在面试还是实际编程中,都会或多或少的使用到排序算法,常见的应用场景有排行榜、好友列表、商品排序等,本文给大家介绍10种常见的内部排序算法,以下是详细的内容:

python学习机构

       常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

       一、冒泡排序

       是一种简单直观的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

def bubbleSort(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

       二、选择排序

       是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时,将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

       三、插入排序

       插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

       插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

       四、希尔排序

       也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

       五、归并排序

       归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(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

       想要学习Python,却又担心找不到合适的Python培训机构,在这里推荐大家来老男孩教育。老男孩教育师资团队强大、从业经验丰富、课程体系完善,且拥有真实企业级实战项目,欢迎大家前来试听。

   推荐阅读:

       Python中常用的网站开发库都有哪些?老男孩python学习班

       Python语言的三种主要模块介绍!老男孩python开发课程

       6个新手必备的在线自学Python网站!老男孩Python培训学校

本文经授权发布,不代表老男孩教育立场。如若转载请联系原作者。