A simple example of Python implementing quick sorting algorithm and quick sorting with deduplication-Python Tutorial-php.cn

Quick sort is often used because the sorting efficiency is higher among several sorting methods that are both O(N*logN).

The basic idea of this method is:

1． First, take a number from the sequence as the base number.

2． During the partitioning process, all numbers larger than this number are placed on its right side, and all numbers smaller than or equal to this number are placed on its left side.

3． Repeat the second step for the left and right intervals until there is only one number in each interval.

Now let’s use an example to illustrate quick queuing.

For example, there is an array:

6 2 4 5 3

Copy after login

Step one: Choose a benchmark number. Don’t be scared by this term. You can think of it as a comparative number, because sorting is about comparison,

For example, I select the last number 3 as the base number, and compare the numbers in the array with 3 in sequence. The numbers smaller than 3 are placed on the left, and those larger than 3 are placed on the right. This will give the following result:

2 3 6 4 5

Copy after login

The second step: Determine the number of intervals. After the first step, there is only one number in the left interval, and there is no number to compare with it, so there is no need to repeat the operation. The right interval still has:

6 4 5

Copy after login

Repeat the first step, select 5 as the base number, and get the comparison result:

4 5 6

Copy after login

In this way, there is only one number in the left and right ranges, which marks the completion of sorting. Finally, merge all the ranges to get the sorting result:

2 3 4 5 6

Copy after login

def quick_sort(array):
  less = []; greater = []
  if len(array) <= 1:
    return array
  pivot = array.pop()
  for x in array:
    if x <= pivot: less.append(x)
    else: greater.append(x)
  return quick_sort(less) + [pivot] + quick_sort(greater)
list = [2,4,2,6,7,8,1]

Copy after login

print quick_sort(list)

Copy after login

[1, 2, 2, 4, 6, 7, 8]

Copy after login

Isn’t it much simpler than C, C#, JAVA and the like^.^

TIP: Quick sorting to remove duplicates
As follows, you only need to modify the set into a single-valued element. Here we use Python3 to demonstrate:

# -*- coding: utf-8 -*- 
  
import random 
 
L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] 
 
def qsort(L): 
  if len(L)<2: return L 
  pivot_element = random.choice(L) 
  small = [i for i in L if i< pivot_element] 
  #medium = [i for i in L if i==pivot_element] 
  large = [i for i in L if i> pivot_element] 
  return qsort(small) + [pivot_element] + qsort(large) 
 
print(qsort(L))

Copy after login

Output:

[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]

Copy after login

You can also use sets directly to sort and remove duplicates.

mylist = list(set(L)) #集合自动排序字符串

Copy after login

Related labels：

python Quick sort sort algorithm

source：php.cn

Previous article：Example tutorial on installing Python's PIL and Pillow libraries for image processing on Linux Next article：Summary of string search operations in Python

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