Python quick sort, insertion sort algorithm, detailed explanation of custom sorting examples

This article mainly introducesPythonExamples of implementing quick sort and insertion sort algorithms and custom sorting. Custom sorting uses Python's sort and sorted functions. Friends in need can refer to the following

1. Quick sort

Quicksort is an improvement on bubble sort. Proposed by C. A. R. Hoare in 1962. Its basic idea is to divide the data to be sorted into two independent parts through one sorting. All the data in one part is smaller than all the data in the other part, and then use this method to quickly separate the two parts of the data. Sorting, the entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

Quick sorting, recursive implementation

def quick_sort(num_list):
  """
  快速排序
  """
  if num_list == []:
    return num_list
  smallList = []
  bigList = []
  middleElement = num_list[0]
  for i in num_list[1:]:
    if i <= middleElement:
      smallList.append(i)
    else:
      bigList.append(i)
  return quick_sort(smallList)+[middleElement]+quick_sort(bigList)

2. Insertion sort

The algorithm description of Insertion Sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence to find the corresponding position and insert it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

Insertion sorting

def insert_sort(num_list):
  """
  插入排序
  """
  for i in range(len(num_list)-1):
    for j in range(i+1, len(num_list)):
      if num_list[i]>num_list[j]:
        num_list[i],num_list[j] = num_list[j],num_list[i]
  return num_list

3. Custom sorting
It can be achieved by using the key of sort() or sorted().

Examples are as follows:

def sort_key(obj):
  sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
  return sorted_list.index(obj)
 
 
if name == 'main':
  print sorted(range(10), key=sort_key)
 
# 输出结果如下
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]

# Use the index position of the keyword in the list to perform custom sorting

The above is the detailed content of Python quick sort, insertion sort algorithm, detailed explanation of custom sorting examples. For more information, please follow other related articles on the PHP Chinese website!