Summary of eight sorting algorithms in Python (Part 2)

This article mainly introduces the second part of the eight sorting algorithms implemented in Python in detail. It has a certain reference value. Interested friends can refer to it.

This article is continued from the previous blog python Part 1 of the eight major sorting algorithms implemented will continue to use Python to implement the remaining four of the eight major sorting algorithms: quick sort, heap sort, merge sort, radix sort

5, quick sort

Quick sort is generally considered to have the best average performance among sorting methods of the same order of magnitude (O(nlog2n)).

Algorithm idea:

We know a set of unordered data a[1], a[2],...a[n], which need to be arranged in ascending order. First, any data a[x] is taken as the benchmark. Compare a[x] with other data and sort it so that a[x] is ranked at the kth position of the data, and make each data in a[1]~a[k-1] a[x], and then use the divide and conquer strategy to a[1]~a[k-1] and a[k+1]~a respectively [n]Quickly sort two sets of data.
Advantages: Extremely fast, less data movement;
Disadvantages: Unstable.

Python code implementation:

def quick_sort(list):
  little = []
  pivotList = []
  large = []
  # 递归出口
  if len(list) <= 1:
    return list
  else:
    # 将第一个值做为基准
    pivot = list[0]
    for i in list:
      # 将比基准小的值放到less数列
      if i < pivot:
        little.append(i)
      # 将比基准大的值放到more数列
      elif i > pivot:
        large.append(i)
      # 将和基准相同的值保存在基准数列
      else:
        pivotList.append(i)
    # 对less数列和more数列继续进行快速排序
    little = quick_sort(little)
    large = quick_sort(large)
    return little + pivotList + large

The following code comes from the three lines of "Python cookbook second edition" to implement python quick sorting.

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python实现八大排序算法
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def quick_sort(list):
  if len(list) <= 1:
    return list
  else:
    pivot = list[0]
    return quick_sort([x for x in list[1:] if x < pivot]) + \
        [pivot] + \
        quick_sort([x for x in list[1:] if x >= pivot])

Screenshot of running test results:

Okay, there is more streamlined syntax sugar, all in one line:

quick_sort = lambda xs : ( (len(xs) <= 1 and [xs]) or [ quick_sort( [x for x in xs[1:] if x < xs[0 ]] ) + [xs[0]] + quick_sort( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

If the initial sequence is ordered by key or basically ordered, quick sort will degenerate into bubble sort. In order to improve it, the "three-in-one method" is usually used to select the benchmark record, that is, the three record keys centered on the two endpoints and the midpoint of the sorting interval are adjusted as the fulcrum record. Quicksort is an unstable sorting method.

In the improved algorithm, we will only recursively call quick sort on subsequences with length greater than k to make the original sequence basically ordered, and then use the insertion sort algorithm to sort the entire basic ordered sequence. Practice has proved that the time complexity of the improved algorithm has been reduced, and when the value of k is about 8, the improved algorithm has the best performance.

6. Heap Sort

Heap sort is a tree selection sort, which is an effective improvement on direct selection sort.

Advantages: high efficiency
Disadvantages: unstable

Under the definition of heap: a sequence of n elements (h1, h2,...,hn), when And it is called only when it satisfies (hi>=h2i,hi>=2i+1) or (hi<=h2i,hi<=2i+1) (i=1,2,...,n/2) heap. Only heaps that meet the former condition are discussed here. It can be seen from the definition of a heap that the top element of the heap (that is, the first element) must be the largest item (big top heap). A complete binary tree can represent the structure of the heap very intuitively. The top of the heap is the root, and the others are the left subtree and the right subtree.

Algorithmic idea:

Initially, the sequence of numbers to be sorted is regarded as a binary tree stored sequentially, and their storage order is adjusted to make it a heap. This The number of root nodes in the heap is the largest. Then swap the root node with the last node of the heap. Then re-adjust the previous (n-1) numbers to form a heap. And so on, until there is a heap with only two nodes, and they are exchanged, and finally an ordered sequence of n nodes is obtained. From the algorithm description, heap sorting requires two processes, one is to establish the heap, and the other is to exchange positions between the top of the heap and the last element of the heap. So heap sort consists of two functions. One is the penetration function to build the heap, and the other is the function to repeatedly call the penetration function to implement sorting.

Python code implementation:

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def adjust_heap(lists, i, size):# 调整堆
  lchild = 2 * i + 1;rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)
def build_heap(lists, size):# 创建堆
  halfsize = int(size/2)
  for i in range(0, halfsize)[::-1]:
    adjust_heap(lists, i, size)
def heap_sort(lists):# 堆排序
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)
    print(lists)

Result example:

7. Merge sort

Algorithm idea:

Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a divide-and-conquer method. Very typical application. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge.

The merging process is: compare the sizes of a[i] and a[j], if a[i]≤a[j], copy the element a[i] in the first ordered list to r[k], and add 1 to i and k respectively; otherwise, copy the element a[j] in the second ordered list to r[k], and add 1 to j and k respectively, This cycle continues until one of the ordered lists is fetched, and then the remaining elements in the other ordered list are copied to the cells from subscript k to subscript t in r. We usually use recursion to implement the merge sorting algorithm. First, the interval to be sorted [s, t] is divided into two by the midpoint, then the left sub-range is sorted, then the right sub-range is sorted, and finally the left interval and the right interval are merged together. Merge into ordered intervals [s,t].

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def merge(left, right):
  i, j = 0, 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:]
  print(result)
  return result
def merge_sort(lists):# 归并排序
  if len(lists) <= 1:
    return lists
  num = int(len(lists) / 2)
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

Program result example:

8、桶排序/基数排序(Radix Sort)

优点：快，效率最好能达到O(1)
缺点：

1.首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

2.其次待排序的元素都要在一定的范围内等等。

算法思想：

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先，可以把桶大小设为10，这样就有100个桶了，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。

然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

python代码实现：

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
import math
lst = [65,56,9,23,84,34,8,6,9,54,11]
#因为列表数据范围在100以内，所以将使用十个桶来进行排序
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      gg = int(j/(radix**(i-1))) % (radix**i)
      bucket[gg].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
      print(lists)
  return lists

程序运行测试结果：

The above is the detailed content of Summary of eight sorting algorithms in Python (Part 2). For more information, please follow other related articles on the PHP Chinese website!