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

伊谢尔伦
Release: 2017-06-28 13:54:53
Original
1836 people have browsed it

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)
Copy after login

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
Copy after login

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 == &#39;main&#39;:
  print sorted(range(10), key=sort_key)
 
# 输出结果如下
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
Copy after login

# 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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template