八大排序算法使用python实现

栏目: Python · 发布时间: 5年前

内容简介:这个之前写的,代码已经丢失,待重新写好代码后补上。一、冒泡排序冒泡排序算法的运作如下:

这个之前写的,代码已经丢失,待重新写好代码后补上。

一、冒泡排序

冒泡 排序 算法的运作如下:

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

以上节选自维基百科

代码实现

二、选择排序

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

以上节选自维基百科

代码实现:

def findSmallest(arr):  # 用于查找出数组中最小的元素,返回最小元素的索引。
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if smallest > arr[i]:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectSort(arr):
    newArr = []
    while arr:
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

三、插入排序

步骤如下

从第一个元素开始,该元素可以认为已经被排序

取出下一个元素,在已经排序的元素序列中从后向前扫描

如果该元素(已排序)大于新元素,将该元素移到下一位置

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

以上节选自维基百科

代码实现

def insert_sort(data):
    for k in range(1, len(data)):
        cur = data[k]
        j = k
        while j > 0 and data[j - 1] > cur:
            data[j] = data[j - 1]
            j -= 1
        data[j] = cur
    return data

四、希尔排序

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。

以上节选自维基百科

代码实现

五、归并排序

原理如下(假设序列共有{displaystyle n}个元素):

将序列每相邻两个数字进行归并操作,形成{displaystyle ceil(n/2)}个序列,排序后每个序列包含两/一个元素

若此时序列数不是1个则将上述序列再次归并,形成{displaystyle ceil(n/4)}个序列,每个序列包含四/三个元素

重复步骤2,直到所有元素排序完毕,即序列数为1

以上节选自维基百科

代码如下

六、快速排序

从数列中挑出一个元素,称为“基准”(pivot),

重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。

递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

以上节选自维基百科

代码如下:

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)


array = [2, 5, 6, 2, 1]
print(quick_sort(array))

七、堆排序

若以升序排序说明,把数组转换成最大堆积(Max-Heap Heap),这是一种满足最大堆积性质(Max-Heap Property)的二叉树:对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。

重复从最大堆积取出数值最大的结点(把根结点和最后一个结点交换,把交换后的最后一个结点移出堆),并让残余的堆积维持最大堆积性质。

八、计数排序

以上节选自维基百科

代码如下

本文章参考维基百科和八大排序算法 python 实现合辑


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

图解服务器端网络架构

图解服务器端网络架构

[日] 宫田宽士 / 曾薇薇 / 人民邮电出版社 / 2015-4 / 79.00元

本书以图配文,详细说明了服务器端网络架构的基础技术和设计要点。基础设计是服务器端网络架构最重要的一个阶段。本书就立足于基础设计的设计细分项目,详细介绍各细分项目的相关技术和设计要点。全书共分为5章,分别讲述进行物理设计、逻辑设计、安全设计和负载均衡设计、高可用性设计以及管理设计时所必需的技术和设计要点。一起来看看 《图解服务器端网络架构》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具