Several examples of commonly used sorting algorithms implemented in Python

  • 2020-04-02 13:46:30
  • OfStack

Some time ago to prepare baidu interview catch up with things, although the last is still brush, or put the few days of "trophy" on the point, algorithm has been relatively weak, after more efforts.

Here are some common sorts implemented in Python, such as quicksort, selection sort, and two-way merge sort.


#encoding=utf-8
import random
from copy import copy
def directInsertSort(seq):
 """  Direct insertion sort  """
 size = len(seq)
 for i in range(1,size):
  tmp, j = seq[i], i
  while j > 0 and tmp < seq[j-1]:
   seq[j], j = seq[j-1], j-1
  seq[j] = tmp
 return seq
def directSelectSort(seq):
 """  Direct selection sort  """
 size = len(seq)
 for i in range(0,size - 1):
  k = i;j = i+1
  while j < size:
   if seq[j] < seq[k]:
    k = j
   j += 1
  seq[i],seq[k] = seq[k],seq[i]
 return seq
def bubbleSort(seq):
 """ Bubble sort """
 size = len(seq)
 for i in range(1,size):
  for j in range(0,size-i):
   if seq[j+1] < seq[j]:
    seq[j+1],seq[j] = seq[j],seq[j+1]
 return seq
def _divide(seq, low, high):
 """ Quicksort partition function """
 tmp = seq[low]
 while low != high:
  while low < high and seq[high] >= tmp: high -= 1
  if low < high:
   seq[low] = seq[high]
   low += 1
  while low < high and seq[low] <= tmp: low += 1
  if low < high:
   seq[high] = seq[low]
   high -= 1
 seq[low] = tmp
 return low
def _quickSort(seq, low, high):
 """ Quicksort helper function """
 if low >= high: return
 mid = _divide(seq, low, high)
 _quickSort(seq, low, mid - 1)
 _quickSort(seq, mid + 1, high)
def quickSort(seq):
 """ Quick sort wrap function """
 size = len(seq)
 _quickSort(seq, 0, size - 1)
 return seq
def merge(seq, left, mid, right):
 tmp = []
 i, j = left, mid
 while i < mid and j <= right:
  if seq[i] < seq[j]:
   tmp.append(seq[i])
   i += 1
  else:
   tmp.append(seq[j])
   j += 1
 if i < mid: tmp.extend(seq[i:])
 if j <= right: tmp.extend(seq[j:])
 seq[left:right+1] = tmp[0:right-left+1]
def _mergeSort(seq, left, right):
 if left == right: 
  return
 else:
  mid = (left + right) / 2
  _mergeSort(seq, left, mid)
  _mergeSort(seq, mid + 1, right)
  merge(seq, left, mid+1, right)
# Two way parallel sorting 
def mergeSort(seq):
 size = len(seq)
 _mergeSort(seq, 0, size - 1)
 return seq
if __name__ == '__main__':
 s = [random.randint(0,100) for i in range(0,20)]
 print s
 print "n"
 print directSelectSort(copy(s))
 print directInsertSort(copy(s))
 print bubbleSort(copy(s))
 print quickSort(copy(s))
 print mergeSort(copy(s))

The operation results are as follows:

E:python_projectpractice>sorting.py
[10, 47, 56, 76, 64, 84, 26, 8, 47, 51, 88, 81, 32, 95, 91, 29, 28, 69, 61, 45]

[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]


Related articles: