程序员必须掌握的十大排序算法（上）-Tutorial Python-php.cn

程序员必须掌握的十大排序算法（上）

Python当打之年

Lepaskan： 2023-08-15 14:55:25

ke hadapan

1024 orang telah melayarinya

本期导读

排序算法可以说是每个程序员都必须得掌握的了, 弄明白它们的原理和实现很有必要，以下为大家介绍十大常用排序算法的python实现方式，方便大家学习。

01 冒泡排序——交换类排序
02 快速排序——交换类排序

03 选择排序——选择类排序
04 堆排序——选择类排序

05 插入排序——插入类排序

06 希尔排序——插入类排序

07 归并排序——归并类排序

08 计数排序——分布类排序

09 基数排序——分布类排序

10 桶排序——分布类排序

冒泡排序

冒泡排序（Bubble Sort）: 一个经典的排序算法，因在算法运行中，极值会像水底的气泡一样逐渐冒出来，因此而得名。

算法原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码如下：

'''冒泡排序''' 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 arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22] result = Bubble_Sort(arr) print('result list: ', result) # result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

Salin selepas log masuk

快速排序

快速排序（Quicksort）： 通过一趟排序将要排序的数据分割成独立的两部分，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列，是对冒泡排序算法的一种改进。

算法原理：

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，直到左、右两个部分各数据排序完成。

代码如下：

'''快速排序''' def Quick_Sort(arr): # 递归入口及出口 if len(arr) >= 2: # 选取基准值，也可以选取第一个或最后一个元素 mid = arr[len(arr) // 2] # 定义基准值左右两侧的列表 left, right = [], [] # 从原始数组中移除基准值 arr.remove(mid) for num in arr: if num >= mid: right.append(num) else: left.append(num) return Quick_Sort(left) + [mid] + Quick_Sort(right) else: return arr arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18] result = Quick_Sort(arr) print('result list: ', result) # result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

Salin selepas log masuk

选择排序

选择排序（Selection sort）：是一种简单直观的排序算法。无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。

算法原理：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

代码如下：

'''选择排序''' def Selection_Sort(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 arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30] result = Quick_Sort(arr) print('result list: ', result) # result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

Salin selepas log masuk

插入排序

插入排序（Insertion Sort） ：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序''' def Insertion_Sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53] result = Insertion_Sort(arr) print('result list: ', result) # result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

Salin selepas log masuk

堆排序

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

算法原理：

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

代码如下：

'''堆排序''' def Heapify(arr, n, i): largest = i # 左右节点分块 left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[i] < arr[left]: largest = left if right < n and arr[largest] < arr[right]: largest = right if largest != i: # 大小值交换 arr[i], arr[largest] = arr[largest], arr[i] # 递归 Heapify(arr, n, largest) def Heap_Sort(arr): nlen = len(arr) for i in range(nlen, -1, -1): # 调整节点 Heapify(arr, nlen, i) for i in range(nlen - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 调整节点 Heapify(arr, i, 0) return arr arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75] result = Heap_Sort(arr) print('result list: ', result) # result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]

Salin selepas log masuk

Atas ialah kandungan terperinci 程序员必须掌握的十大排序算法（上）. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!