A simple example of Python implementing quick sorting algorithm and quick sorting with deduplication

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

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

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

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

4 5 6

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

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]

print quick_sort(list)

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

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)) 

Output:

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

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

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