当前位置：文档之家 › Python实现各种排序

Python实现各种排序

  • 格式：doc
  • 大小：154.00 KB
  • 文档页数：9

在Python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有Google等搜索引擎的存在），当然，这样的例子数不胜数。

《数据结构》也会花大量篇幅讲解排序。

之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种排序算法，放在这里作为参考。

最简单的排序有三种：插入排序，选择排序和冒泡排序。

这三种排序比较简单，它们的平均时间复杂度均为O(n^2)，在这里对原理就不加赘述了。

代码直接贴出来。

插入排序：def insertion_sort(sort_list):iter_len = len(sort_list)if iter_len < 2:return sort_listfor i in range(1, iter_len):key = sort_list[i]j = i - 1while j>=0 and sort_list[j]>key:sort_list[j+1] = sort_list[j]j -= 1sort_list[j+1] = keyreturn sort_list冒泡排序：def bubble_sort(sort_list):iter_len = len(sort_list)if iter_len < 2:return sort_listfor i in range(iter_len-1):for j in range(iter_len-i-1):if sort_list[j] > sort_list[j+1]:sort_list[j], sort_list[j+1] = sort_list[j+1],sort_list[j]return sort_list选择排序：def selection_sort(sort_list):iter_len = len(sort_list)if iter_len < 2:return sort_listfor i in range(iter_len-1):smallest = sort_list[i]location = ifor j in range(i, iter_len):if sort_list[j] < smallest:smallest = sort_list[j]location = jif i != location:sort_list[i], sort_list[location] = sort_list[location], sort_list[i]return sort_list这里我们可以看到这样的句子：sort_list[i], sort_list[location] = sort_list[location], sort_list[i]不了解Python的同学可能会觉得奇怪，没错，这是交换两个数的做法，通常在其他语言中如果要交换a与b的值，常常需要一个中间变量temp，首先把a赋给temp，然后把b赋给a，最后再把temp赋给b。

但是在python中你就可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。

平均时间复杂度为O(nlogn)的算法有：归并排序，堆排序和快速排序。

归并排序。

对于一个子序列，分成两份，比较两份的第一个元素，小者弹出，然后重复这个过程。

对于待排序列，以中间值分成左右两个序列，然后对于各子序列再递归调用。

源代码如下，由于有工具函数，所以写成了callable的类：class merge_sort(object):def _merge(self, alist, p, q, r):left = alist[p:q+1]right = alist[q+1:r+1]for i in range(p, r+1):if len(left)>0 and len(right)>0:if left[0]<=right[0]:alist[i] = left.pop(0)else:alist[i] = right.pop(0)elif len(right)==0:alist[i] = left.pop(0)elif len(left)==0:alist[i] = right.pop(0)def _merge_sort(self, alist, p, r):if p<r:q = int((p+r)/2)self._merge_sort(alist, p, q)self._merge_sort(alist, q+1, r)self._merge(alist, p, q, r)def __call__(self, sort_list):self._merge_sort(sort_list, 0, len(sort_list)-1)return sort_list堆排序，是建立在数据结构——堆上的。

关于堆的基本概念、以及堆的存储方式这里不作介绍。

这里用一个列表来存储堆（和用数组存储类似），对于处在i位置的元素，2*i+1位置上的是其左孩子，2*i+2是其右孩子，类似得可以得出该元素的父元素。

首先我们写一个函数，对于某个子树，从根节点开始，如果其值小于子节点的值，就交换其值。

用此方法来递归其子树。

接着，我们对于堆的所有非叶节点，自下而上调用先前所述的函数，得到一个树，对于每个节点（非叶节点），它都大于其子节点。

（其实这是建立最大堆的过程）在完成之后，将列表的头元素和尾元素调换顺序，这样列表的最后一位就是最大的数，接着在对列表的0到n-1部分再调用以上建立最大堆的过程。

最后得到堆排序完成的列表。

以下是源代码：class heap_sort(object):def _left(self, i):return 2*i+1def _right(self, i):return 2*i+2def _parent(self, i):if i%2==1:return int(i/2)else:return i/2-1def _max_heapify(self, alist, i, heap_size=None):length = len(alist)if heap_size is None:heap_size = lengthl = self._left(i)r = self._right(i)if lalist[i]:largest = lelse:largest = iif ralist[largest]:largest = rif largest!=i:alist[i], alist[largest] = alist[largest], alist[i]self._max_heapify(alist, largest, heap_size)def _build_max_heap(self, alist):roop_end = int(len(alist)/2)for i in range(0, roop_end)[::-1]:self._max_heapify(alist, i)def __call__(self, sort_list):self._build_max_heap(sort_list)heap_size = len(sort_list)for i in range(1, len(sort_list))[::-1]:sort_list[0], sort_list[i] = sort_list[i], sort_list[0] heap_size -= 1self._max_heapify(sort_list, 0, heap_size)return sort_list最后一种要说明的交换排序算法（以上所有算法都为交换排序，原因是都需要通过两两比较交换顺序）自然就是经典的快速排序。

先来讲解一下原理。

首先要用到的是分区工具函数（partition），对于给定的列表（数组），我们首先选择基准元素（这里我选择最后一个元素），通过比较，最后使得该元素的位置，使得这个运行结束的新列表（就地运行）所有在基准元素左边的数都小于基准元素，而右边的数都大于它。

然后我们对于待排的列表，用分区函数求得位置，将列表分为左右两个列表（理想情况下），然后对其递归调用分区函数，直到子序列的长度小于等于1。

下面是快速排序的源代码：class quick_sort(object):def _partition(self, alist, p, r):i = p-1x = alist[r]for j in range(p, r):if alist[j]<=x:i += 1alist[i], alist[j] = alist[j], alist[i]alist[i+1], alist[r] = alist[r], alist[i+1]return i+1def _quicksort(self, alist, p, r):if p<r:q = self._partition(alist, p, r)self._quicksort(alist, p, q-1)self._quicksort(alist, q+1, r)def __call__(self, sort_list):self._quicksort(sort_list, 0, len(sort_list)-1)return sort_list细心的朋友在这里可能会发现一个问题，如果待排序列正好是顺序的时候，整个的递归将会达到最大递归深度（序列的长度）。

而实际上在操作的时候，当列表长度大于1000（理论值）的时候，程序会中断，报超出最大递归深度的错误（maximum recursion depth exceeded）。

在查过资料后我们知道，Python在默认情况下，最大递归深度为1000（理论值，其实真实情况下，只有995左右，各个系统这个值的大小也不同）。

这个问题有两种解决方案，1）重新设置最大递归深度，采用以下方法设置：import syssys.setrecursionlimit(99999)2）第二种方法就是采用另外一个版本的分区函数，称为随机化分区函数。

由于之前我们的选择都是子序列的最后一个数，因此对于特殊情况的健壮性就差了许多。

现在我们随机从子序列选择基准元素，这样可以减少对特殊情况的差错率。

新的randomize partition函数如下：def _randomized_partition(self, alist, p, r):i = random.randint(p, r)alist[i], alist[r] = alist[r], alist[i]return self._partition(alist, p, r)完整的randomize_quick_sort的代码如下（这里我直接继承之前的quick_sort 类）：import randomclass randomized_quick_sort(quick_sort):def _randomized_partition(self, alist, p, r):i = random.randint(p, r)alist[i], alist[r] = alist[r], alist[i]return self._partition(alist, p, r)def _quicksort(self, alist, p, r):if p<r:q = self._randomized_partition(alist, p, r)self._quicksort(alist, p, q-1)self._quicksort(alist, q+1, r)关于快速排序的讨论还没有结束。

合集下载

python rank 的用法

python rank 的用法

一、Python Rank 的基本概念Python 中的 Rank 可以用来对列表中的元素进行排序，它是一个非常常用的功能。

在实际应用中，我们经常需要对一些数据进行排序，这时就可以使用 Python 中的 Rank 来方便地实现这一功能。

二、Python Rank 的用法1. 对列表进行排序使用 Rank 可以非常方便地对列表中的元素进行排序。

如果有一个列表a，想要对其进行从小到大的排序，只需要使用a.rank() 即可实现。

2. 排序顺序的选择Rank 还可以根据不同的需求选择排序的顺序，可以是从小到大，也可以是从大到小。

通过在 .rank() 函数中加入参数，即可实现不同排序需求的实现。

3. 对字典进行排序除了对列表进行排序，Rank 还可以对字典进行排序。

字典在实际应用中也是非常常见的数据结构，所以 Rank 对字典的排序功能也是非常实用的。

4. 自定义排序规则有时候，我们需要根据一些特定的规则对数据进行排序，而不是简单地按照大小顺序进行排列。

这时，可以使用自定义的比较函数来实现特定规则的排序，让 Rank 变得更加灵活。

5. Rank 的性能优化在大规模数据的排序过程中，性能的优化是非常重要的。

Python 中的Rank 也提供了一些性能优化的方法，可以在处理大规模数据时减少排序的时间复杂度，提高程序的运行效率。

三、Python Rank 的应用场景1. 数据分析在数据分析的过程中，经常需要对数据进行排序以便进行进一步的分析。

使用 Rank 可以方便地对数据进行排序，便于后续的处理和分析工作。

2. 算法实现在一些算法的实现过程中，排序是一个非常基础和常用的操作。

使用Rank 可以简化排序的过程，让算法更加清晰和高效。

3. 数据库操作在进行数据库操作时，有时需要对数据库中的数据进行排序。

使用Rank 可以方便地在 Python 程序中对数据库中的数据进行排序操作。

四、总结Python 中的 Rank 是一个非常实用的功能，它可以方便地对列表和字典等数据进行排序，满足不同排序需求的实现。

python经典算法例题

python经典算法例题

python经典算法例题Python作为一种高级编程语言，具有丰富的算法实现和库函数支持，下面我将介绍一些经典的算法例题，并给出相应的Python实现。

1. 二分查找算法。

二分查找算法是一种在有序数组中查找特定元素的算法。

它的时间复杂度是O(log n)。

下面是一个简单的Python实现：python.def binary_search(arr, target):low, high = 0, len(arr) 1。

while low <= high:mid = (low + high) // 2。

if arr[mid] == target:return mid.elif arr[mid] < target:low = mid + 1。

else:high = mid 1。

return -1。

2. 快速排序算法。

快速排序是一种高效的排序算法，其平均时间复杂度为O(nlogn)。

下面是一个简单的Python实现：python.def quick_sort(arr):if len(arr) <= 1:return arr.pivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle +quick_sort(right)。

3. 最大子数组问题。

最大子数组问题是指在一个数组中找到一个连续的子数组，使得子数组的和最大。

下面是一个简单的Python实现：python.def max_subarray(arr):max_sum = float('-inf')。

current_sum = 0。

for num in arr:current_sum = max(num, current_sum + num)。

python排序方法

python排序方法

python排序方法一、冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历待排序序列，每次比较相邻的两个元素，如果顺序错误就交换它们。

经过一轮的遍历，最大的元素会排到序列的最后面，然后继续遍历剩余的元素。

代码实现:```def bubble_sort(lst):n = len(lst)for i in range(n - 1):for j in range(n - i - 1):if lst[j] > lst[j + 1]:lst[j], lst[j + 1] = lst[j + 1], lst[j]return lst```二、选择排序选择排序是一种简单直观的排序算法，它的主要思想是在未排序的序列中选择最小（或最大）的元素，将它与序列的第一个元素交换位置，然后在剩余的序列中继续做同样的操作，直到整个序列排序完成。

三、插入排序插入排序是一种简单但效率较低的排序算法，它的思路是遍历待排序序列，将每个元素插入到已排序的序列中的正确位置上。

插入排序分为直接插入排序和希尔排序两种。

1. 直接插入排序2. 希尔排序希尔排序是直接插入排序的升级版，它利用了“增量序列”的概念，可以将待排序序列拆分为若干个子序列进行排序，逐步缩小增量序列的范围，最终完成整个序列的排序。

四、快速排序快速排序是一种高效的排序算法，它的主要思想是通过分治技术将待排序序列拆分为两个子序列，然后对子序列分别进行排序，最终合并成一个有序序列。

快速排序的优点是实现简单且在大多数情况下都能在O(nlogn)的时间复杂度内完成排序。

五、堆排序堆排序是一种基于堆数据结构的排序算法，它的主要思想是将待排序序列构建成一个二叉堆，然后利用堆的性质将堆顶元素与末尾元素交换位置，然后将未排序部分重新构建成一个堆，重复以上操作，直到整个序列排序完成。

```def heap_sort(lst):def sift_down(start, end, nums):root = startwhile True:child = 2 * root + 1if child > end:breakif child + 1 <= end and nums[child] < nums[child + 1]:child += 1if nums[root] < nums[child]:nums[root], nums[child] = nums[child], nums[root]root = childelse:breakn = len(lst)for i in range(n // 2 - 1, -1, -1):sift_down(i, n - 1, lst)for i in range(n - 1, 0, -1):lst[0], lst[i] = lst[i], lst[0]sift_down(0, i - 1, lst)return lst```六、归并排序七、计数排序计数排序是一种非比较排序算法，它的主要思想是统计待排序序列中每个元素出现的次数，然后根据元素的大小和出现次数进行排序。

python sort排序规则

python sort排序规则

python sort排序规则在Python中，sort()是一个非常常用的排序函数。

它可以按照一定的规则对列表中的元素进行排序。

但是，在使用sort()函数时，需要注意一些规则，否则会引起排序错误。

下面是Python中sort()排序规则的详细介绍。

1. 默认排序规则默认情况下，sort()函数按照元素的大小进行排序。

如果是数字类型的元素，则按照从小到大的顺序进行排序；如果是字符串类型的元素，则按照字典序进行排序。

例如，对于以下列表：lst = [1, 3, 2, 5, 4]使用sort()函数进行排序：lst.sort()得到的结果为：[1, 2, 3, 4, 5]2. 自定义排序规则在实际应用中，我们有时需要按照自定义的规则对列表中的元素进行排序。

此时，我们可以使用sort()函数的key参数。

key参数是一个函数，用来计算每个元素的排序值。

sort()函数会调用这个函数来获得每个元素的排序值，然后按照排序值进行排序。

最终得到的结果就是按照自定义规则排序后的列表。

例如，对于以下列表：lst = ['apple', 'banana', 'orange', 'pear']我们想要按照每个水果的长度进行排序。

此时，可以使用len()函数作为key参数：lst.sort(key=len)得到的结果为：['pear', 'apple', 'banana', 'orange']说明：按照水果的长度从小到大排序。

长度相同的情况下，按照字典序进行排序。

3. 降序排序除了默认情况下从小到大进行排序外，我们还可以使用reverse 参数将排序规则改为从大到小排序。

reverse参数是一个布尔值，如果为True，则按照从大到小排序；否则按照从小到大排序。

例如，对于以下列表：lst = [1, 3, 2, 5, 4]我们想要按照从大到小的顺序进行排序。