How to implement eight sorting algorithms in Python

This article mainly introduces the Python implementation of the eight sorting algorithms, and provides a detailed description and code implementation of the eight sorting algorithms. Interested friends can refer to

Python implementation of the eight sorting algorithms for specific content. As follows

1. Insertion sort
Description

The basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to get 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 repeats It walks through the sequence to be sorted, comparing elements two 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

Pass one trip Sorting divides the data to be sorted into two independent parts. All the data in one part is smaller than all the data in the other part. Then the two parts of the data are quickly sorted according to this method. The entire sorting process can be performed recursively. In this way, 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 r1 ~ r[n] to be sorted, and exchange it with r1; in the second pass, select the smallest record among the records r2 ~ r[n] to be sorted, and exchange it with r1 It is exchanged with r2; and so on, the i-th pass selects the smallest record among the records to be sorted r[i] ~ r[n], and exchanges it with r[i], so that the ordered sequence continues to grow until all are sorted. complete.

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

Heap sort ( Heapsort) refers to a sorting algorithm designed using a data structure such as a stacked tree (heap). It is a type of selection sort. You can use the characteristics of arrays to quickly locate the element at a 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. Merge sort
Description

Merge sort is An effective sorting algorithm based on merge operations. This algorithm is a very typical application of the divide and conquer method (pide and Conquer). 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. We first divide the interval to be sorted [s, t] into two at the midpoint, then sort the left sub-range, then sort the right sub-range, and finally use a merge operation between the left interval and the right interval. Merge into ordered intervals [s,t].

Code implementation

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
Description

Radix sort ( radix sort) belongs to "distribution sort", also known as "bucket sort" or bin sort. As the name suggests, it allocates the elements to be sorted to certain In the "bucket", to achieve the sorting effect, the radix sorting method is a stable sorting, and its time complexity is O (nlog(r)m), where r is the radix taken, and m is the number of heaps. Sometimes, radix sorting is more efficient than other stability sorting methods.

Code

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

以上就是Python实现八大排序算法的详细介绍，希望对大家的学习有所帮助。

The above is the detailed content of How to implement eight sorting algorithms in Python. For more information, please follow other related articles on the PHP Chinese website!