专栏首页CSDN博客Python实现常见的排序算法
原创

Python实现常见的排序算法

原文博客:Doi技术团队 链接地址:https://blog.doiduoyi.com/authors/1584446358138 初心:记录优秀的Doi技术团队学习经历 本文链接:Python实现常见的排序算法

前言

本章介绍使用Python实现场景的几种排序算法。分别有冒泡算法、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排序、桶排序、基数排序。

创建一个比较大的list,用于测试排序算法使用。

import numpy as np
import time

src_list = np.random.randint(1, 10000000, (100000)).tolist()

冒泡排序

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-1-i):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
start = time.time()
result = bubble_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

快速排序

在一个数据集中取个数作为参考点,大于该数的元素放在其右边;小于该数的元素放在其左边。这样就将数据集分成两部分,大于参考值部分和小于参考值部分,递归该过程,直到序列中所有记录均有序。

def quick_sort(listt, left, right):
    if left >= right:
        return listt
 
    # 选择参考点,该调整范围的第1个值
    pivot = listt[left]
    low = left  
    high = right
 
    while left < right:
        # 从右边开始查找大于参考点的值
        while left < right and listt[right] >= pivot:
            right -= 1
         # 这个位置的值先挪到左边
        listt[left] = listt[right] 
 
         # 从左边开始查找小于参考点的值
        while left < right and listt[left] <= pivot:
            left += 1
         # 这个位置的值先挪到右边
        listt[right] = listt[left]
 
    # 写回改成的值
    listt[left] = pivot
 
    # 递归,并返回结果
    quick_sort(listt, low, left - 1)    # 递归左边部分
    quick_sort(listt, left + 1, high)   # 递归右边部分
    return listt
start = time.time()
result = quick_sort(src_list, 0, 1000)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

def insert_sort(alist):
    length = len(alist)
    for i in range(1,length):
        for j in range(i, 0, -1):
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[i]
            else:
                break
    return alist
start = time.time()
result = insert_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

def shell_sort(alist):
    n = len(alist)
    gap = n // 2
    while gap >= 1:
        for i in range(gap,n):
            while (i - gap) >= 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i = i - gap
                else:
                    break
        gap = gap // 2
    return alist
start = time.time()
result = shell_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

选择排序

选择排序是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

def select_sort(alist):
    n = len(alist)
    for i in range(n):
    # 设置索引 i为最小值的索引
        min_idx = i
        # 通过比较,不断调整最小值的索引位置
        for j in range(i,n):
            if alist[j] < alist[min_idx]:
                min_idx = j
        # 交换第i个值与最小值
        alist[i], alist[min_idx] = alist[min_idx], alist[i]
    return alist
start = time.time()
result = select_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

# 调整堆的结构,使其父节点的值大于子节点的值
def max_heap(heap, heapsize, root):
    left = 2*root+1
    right = left + 1
    large = root
    if left < heapsize and heap[large] < heap[left]:
        large = left
    if right < heapsize and heap[large] < heap[right]:
        large = right
    # 若large=right或large=left,则说明,出现比父节点大的子节点,这时对调,使子节点变为父节点
    if large != root:
        heap[large], heap[root] = heap[root], heap[large]
        max_heap(heap, heapsize, large)
        
# 构造一个堆,对堆中数据重新排序
def build_max_heap(heap):
    length = len(heap)
    # 从后往前调整结构
    for i in range((length-2)//2,-1,-1):
        max_heap(heap, length, i)
        
# 将根节点取出与最后一位对调,对前面len-1个节点继续进行对调过程
def heap_sort(heap):
    build_max_heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heap(heap,i,0)
    return heap
start = time.time()
result = heap_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

归并排序

归并排序(mergesort)是创建在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

分治法:

分割:递归地把当前序列平均分割成两半

集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)

def merge_sort(alist):
    if len(alist) < 2:
        return alist
    # 将列表分成更小的两个列表
    mid = int(len(alist)/2)
    # 分别对左右两个列表进行处理,分别返回两个排序好的列表
    left = merge_sort(alist[:mid])
    right = merge_sort(alist[mid:])
    # 对排序好的两个列表合并,产生一个新的排序好的列表
    return merge(left,right)

def merge(left,right):
    i = 0
    j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
start = time.time()
result = merge_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

对每一个输入的元素ai,确定小于 ai 的元素个数。所以可以直接把 ai 放到它输出数组中的位置上。假设有5个数小于 ai,所以 ai 应该放在数组的第6个位置上

def count_sort(alist):
    # 找到最大最小值
    min_num = min(alist)
    max_num = max(alist)
    # 初始化计数列表
    count_list = [0]*(max_num-min_num+1)
    # 对列表中的每一个元素计数
    for num in alist:
        count_list[num-min_num] += 1
    alist.clear()
    # 当某个元素的个数不为 0,将该元素填回alist列表
    for cur_num, count in enumerate(count_list):
        while count != 0:
            alist.append(cur_num+min_num)
            count -= 1
    return alist
start = time.time()
result = count_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

桶排序

把数组a划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并。桶排序要求数据的分布必须均匀,不然可能会失效。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。

原理:

(1) 设置一个定量的数组当作空桶

(2) 遍历输入数据,并且把数据一个一个放到对应的桶里去

(3) 对每个不是空的桶进行排序

(4) 从不是空的桶里把排好序的数据拼接起来

def bucket_sort(alist):
    min_num = min(alist)
    max_num = max(alist)
    # 设置桶的大小
    bucket_size = (max_num - min_num)/len(alist)
    # 创建桶数组
    bucket_list = [[]for i in range(len(alist)+1)]
    # 向桶数组填数
    for num in alist:
        bucket_list[int((num-min_num)//bucket_size)].append(num)
    alist.clear()
    # 回填,这里桶内部排序直接调用了sorted
    for i in bucket_list:
        for j in sorted(i):
            alist.append(j)
    return alist
start = time.time()
result = bucket_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

基数排序

基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序,也就是说,基数排序的实质是多关键字排序,比如说成绩的排序,如果两个人总分相同,则语文高的排在前面,语文成绩也相同则数学高的排在前面,如果对数字进行排序,那么个位、十位、百位就是不同优先级的关键

原理:

(1) 取得数组中的最大数,并取得位数

(2) 建立桶数组

(3) 按位数的大小分别装进不同的桶里

(4) 将原数组清空,将各个桶里的数据依次添加进原列表

(5) 再进行前一位的排序,依次循环,直到排序的位数大于最大值的位数

def radix_sort(alist):
    # 记录正在对哪一位进行排序,最低位为个位
    i = 0
    # 最大值的位数
    max_num = max(alist)
    j = len(str(max_num))
    while i < j:
        # 建立桶数组,数字为0-9,所以建10个桶
        bucket_list = [[]for i in range(10)]
        # 按位数的大小分别装进不同的桶里
        for num in alist:
            bucket_list[int(num/(10**i)%10)].append(num)
        #将原列表清空,将各个桶里的数据依次添加进原列表
        alist.clear()
        for l in bucket_list:
            for b in l:
                alist.append(b)
        # 再进行前一位的排序,依次循环,直到排序的位数大于最大值的位数
        i += 1
    return alist
start = time.time()
result = radix_sort(src_list)
end = time.time()
print ("耗时:%d 毫秒" % int(round((end - start) * 1000)))

更好阅读体验可以访问Kesci Lab: https://www.kesci.com/home/project/5ebf61f52d8821002dc425d0

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用 Python 实现几种常见的排序算法

    冒泡排序是最为基础的排序算法,其核心思想就是相邻元素两两比较,把较大的元素放到后面,在一轮比较完成之后,最大的元素就位于最后一个位置了,就好像是气泡,慢慢的浮出...

    周萝卜
  • 常见排序算法-Python实现

    常见排序算法-Python实现 python 排序 算法 1.二分法 python    32行 #coding=utf-8 def binary_s...

    marsggbo
  • JAVA实现常见排序算法 快速排序

    基本思想:用选取的初始值(一般是第一个)将待排序序列分为小于初始值和大于初始值的两部分,然后重复此操作,最终到排序完成。该算法是一个不稳定的算法(如果待排序序列...

    算法与编程之美
  • Java实现常见排序算法(二)

    上次的博客讨论了排序算法中的插入排序和交换排序两个大类,今天将剩下的常见排序算法全部梳理出来。

    算法与编程之美
  • Java实现常见排序算法(一)

    在开发过程中使用得比较多的算法就是排序算法和查找算法了,今天先盘点一下常见的排序算法中的两个大类交换排序和插入排序。

    算法与编程之美
  • 常见排序算法及golang 实现

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有...

    程序员小饭
  • 《常见排序算法》

    1.概述 常见的排序算法,虽然很基础,但是很见功力,如果能思路清晰,很快写出来各个算法的代码实现,还是需要花一点功夫的,今天,就跟大家盘点下常用的一些算法。 冒...

    企鹅号小编
  • Python中几种常见的排序算法?

    小猿会从最基础的面试题开始,每天一题。如果参考答案不够好,或者有错误的话,麻烦大家可以在留言区给出自己的意见和讨论,大家是要一起学习的 。

    程序IT圈
  • 常见算法之排序

    各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

    我是东东东
  • 排序算法的python实现

    所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。

    Minerva
  • 常见的五种排序算法

    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。

    Yif
  • 排序算法python实现

    jeremyxu
  • 排序算法:Python 实现

    import sys print (sys.version) # 3.5.2 |Continuum Analytics, Inc.| (default, J...

    用户1332428
  • Python实现排序算法

    本章介绍使用Python实现场景的几种排序算法。分别有冒泡算法、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排序、桶排序、基数排序。

    用户3577892
  • Python实现排序算法

    排序算法有很多种,下面列举几种: 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 5.快速排序 6.归并排序

    py3study
  • 常见排序算法分类

      此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

    Dabelv
  • 十种常见排序算法

    十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择...

    Dabelv
  • 常见排序算法分析

    一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

    猿人谷
  • 常见排序算法详解

    作为程序员,时时刻刻都要与算法打交道,其中排序算法算是比较常见的一种。而在面试程序员岗位中, 不出意外,排序算法也是比较常见的考量之一。因此我们有必要了解和掌握...

    终身幼稚园

扫码关注云+社区

领取腾讯云代金券