Python implements eight sorting algorithms

How to use Python to implement eight sorting algorithms

1. Insertion sort
Description
Insertion sort The basic operation is to insert a piece of data into the already sorted ordered data, thereby obtaining a new ordered data with the number plus one. The algorithm is suitable for sorting a small amount of data, and the time complexity is O(n^ 2). It is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array, except for the last element (making the array one more space to have an insertion position), and the second part only contains this one element (i.e. the element to be inserted). After the first part is sorted, this last element is inserted into the sorted first part.
Code implementation

 def insert_sort(lists): 
  # 插入排序 
  count = len(lists) 
  for i in range(1, count): 
    key = lists[i] 
    j = i - 1 
    while j >= 0: 
      if lists[j] > key: 
        lists[j + 1] = lists[j] 
        lists[j] = key 
      j -= 1 
  return lists

2. Hill sorting
Description
Hill sort (Shell Sort) is a type of insertion sort. Also known as reducing incremental sorting, it is a more efficient and improved version of the direct insertion sort algorithm. Hill sorting is a non-stable sorting algorithm. This method is due to DL. Shell was named after it was proposed in 1959. Hill sorting groups records by a certain increment of the subscript, and sorts each group using the direct insertion sorting algorithm; as the increment gradually decreases, each group contains more and more keywords. When the increment decreases to 1, The entire file has been grouped into exactly one group, and the algorithm terminates.
Code implementation

 def shell_sort(lists): 
  # 希尔排序 
  count = len(lists) 
  step = 2 
  group = count / step 
  while group > 0: 
    for i in range(0, group): 
      j = i + group 
      while j < count: 
        k = j - group 
        key = lists[j] 
        while k >= 0: 
          if lists[k] > key: 
            lists[k + group] = lists[k] 
            lists[k] = key 
          k -= group 
        j += group 
    group /= step 
  return lists

3. Bubble sort
Description
It repeatedly visits the sequence to be sorted, comparing two elements at a time, and swapping them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted.
Code implementation

 def bubble_sort(lists): 
  # 冒泡排序 
  count = len(lists) 
  for i in range(0, count): 
    for j in range(i + 1, count): 
      if lists[i] > lists[j]: 
        lists[i], lists[j] = lists[j], lists[i] 
  return lists

4. Quick sort
Description
Divide the data to be sorted into two independent parts through one pass of sorting. All the data in one part is smaller than all the data in the other part, and then Then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.
Code implementation

 def quick_sort(lists, left, right): 
  # 快速排序 
  if left >= right: 
    return lists 
  key = lists[left] 
  low = left 
  high = right 
  while left < right: 
    while left < right and lists[right] >= key: 
      right -= 1 
    lists[left] = lists[right] 
    while left < right and lists[left] <= key: 
      left += 1 
    lists[right] = lists[left] 
  lists[right] = key 
  quick_sort(lists, low, left - 1) 
  quick_sort(lists, left + 1, high) 
  return lists

5. Direct selection sorting
Description
Basic idea: In the first pass, select the smallest record among the records to be sorted r1 ~ r[n], and exchange it with r1; 2 passes, select the smallest record among the records to be sorted r2 ~ r[n], and exchange it with r2; and so on, the i-th pass selects the smallest record among the records to be sorted r[i] ~ r[n] records, exchange it with r[i], so that the ordered sequence continues to grow until all sorting is completed.
Code implementation

 def select_sort(lists): 
  # 选择排序 
  count = len(lists) 
  for i in range(0, count): 
    min = i 
    for j in range(i + 1, count): 
      if lists[min] > lists[j]: 
        min = j 
    lists[min], lists[i] = lists[i], lists[min] 
  return lists

6. Heap sort
Description
Heapsort refers to a sorting algorithm designed using a data structure such as a stacked tree (heap). It is a type of selection sorting. You can use the characteristics of the array to quickly locate the element at the specified index. The heap is divided into a large root heap and a small root heap, which is a complete binary tree. The requirement of a large root heap is that the value of each node is not greater than the value of its parent node, that is, A[PARENT[i]] >= A[i]. In non-descending sorting of an array, a large root heap needs to be used, because according to the requirements of a large root heap, the maximum value must be at the top of the heap.
Code implementation

 # 调整堆 
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): 
  for i in range(0, (size/2))[::-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)

7、归并排序
描述
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否 则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复 制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序， 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
代码实现

 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:] 
  return result 
 
def merge_sort(lists): 
  # 归并排序 
  if len(lists) <= 1: 
    return lists 
  num = len(lists) / 2 
  left = merge_sort(lists[:num]) 
  right = merge_sort(lists[num:]) 
  return merge(left, right)

8、基数排序
描述
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
代码实现

 import math 
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: 
      bucket[j/(radix**(i-1)) % (radix**i)].append(j) 
    del lists[:] 
    for z in bucket: 
      lists += z 
      del z[:] 
  return lists

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Python实现八大排序算法相关文章请关注PHP中文网！