Python版的迷你程序——快速排序（python快速排序原理）

前几天学习的几个排序算法，C语言的实现。

C版的迷你程序——排序算法

Python版的迷你程序——冒泡排序

Python版的迷你程序——选择排序

Python版的迷你程序——插入排序

Python版的迷你程序——归并排序

这个是python版本的快速排序算法，使用了python的列表和模块numpy的数组格式，还对比了列表自身的sort方法和numba模块的加速耗时。

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
#

import numpy
import time
import copy
import math
import random
from numba import jit
from datetime import datetime 

def TimeTest():
    time.sleep(2)

'''  列表包含字典   下面是列表包含列表的实现
def QuickSort(arr):
    n = len(arr)
    r = [0]*(n)
    p = 0
    r[p] = {'start':0, 'end':n-1} 
    p += 1
    
    while p:
        p -= 1
        rge = r[p];
        if rge['start'] >= rge['end']:
            continue

        mid = arr[(rge['start'] + rge['end'])//2]; # 中间基点
        left, right = rge['start'], rge['end'];    # 两端开始

        while (arr[left] < mid):
            left += 1              # 基点左
        while (arr[right] > mid):
            right -= 1             # 基点右
        if (left <= right):
            arr[left],arr[right] = arr[right],arr[left]
            left += 1
            right -= 1
        while (left <= right):
            while (arr[left] < mid):
                left += 1              # 基点左
            while (arr[right] > mid):
                right -= 1             # 基点右
            if (left <= right):
                arr[left],arr[right] = arr[right],arr[left]
                left += 1
                right -= 1

        if (rge['start'] < right) :
            r[p] = {'start':rge['start'], 'end':right} 
            p += 1
        if (rge['end'] > left) :
            r[p] = {'start':left, 'end':rge['end']} 
            p += 1
'''
def QuickSort(arr):
    n = len(arr)
    r = [0]*(n)
    p = 0
    r[p] = [0, n-1] 
    p += 1
    
    while p:
        p -= 1
        rge = r[p];
        if rge[0] >= rge[1]:
            continue

        mid = arr[(rge[0] + rge[1])//2]; # 中间基点
        left, right = rge[0], rge[1];    # 两端开始

        while (arr[left] < mid):
            left += 1              # 基点左
        while (arr[right] > mid):
            right -= 1             # 基点右
        if (left <= right):
            arr[left],arr[right] = arr[right],arr[left]
            left += 1
            right -= 1
        while (left <= right):
            while (arr[left] < mid):
                left += 1              # 基点左
            while (arr[right] > mid):
                right -= 1             # 基点右
            if (left <= right):
                arr[left],arr[right] = arr[right],arr[left]
                left += 1
                right -= 1

        if (rge[0] < right) :
            r[p] = [rge[0], right]
            p += 1
        if (rge[1] > left) :
            r[p] = [left, rge[1]]
            p += 1



@jit
def QuickSortsubjit(arr, rge):
    mid = arr[(rge[0] + rge[1])//2]; # 中间基点
    left, right = rge[0], rge[1];    # 两端开始

    while (arr[left] < mid):
        left += 1              # 基点左
    while (arr[right] > mid):
        right -= 1             # 基点右
    if (left <= right):
        arr[left],arr[right] = arr[right],arr[left]
        left += 1
        right -= 1
    while (left <= right):
        while (arr[left] < mid):
            left += 1              # 基点左
        while (arr[right] > mid):
            right -= 1             # 基点右
        if (left <= right):
            arr[left],arr[right] = arr[right],arr[left]
            left += 1
            right -= 1

    return left,right

def QuickSortjit(arr):
    n = len(arr)
    r = [0]*(n)
    p = 0
    r[p] = [0, n-1] 
    p += 1
    
    while p:
        p -= 1
        rge = r[p];
        if rge[0] >= rge[1]:
            continue

        left,right = QuickSortsubjit(arr, rge)

        if (rge[0] < right) :
            r[p] = [rge[0], right]
            p += 1
        if (rge[1] > left) :
            r[p] = [left, rge[1]]
            p += 1




start_ = datetime.utcnow()  
TimeTest()
end_ = datetime.utcnow()  
cdelt = (end_ - start_)  
print("\t\t\t\t\t\t\t\t TimeTesto running time: %.3fms" % (cdelt.microseconds))


arrlist=[]
arrlen=16*1024
for i in range(arrlen):
    arrlist.append(random.randint(0,32768))

arrlistjt = copy.deepcopy(arrlist)
arrlistso = copy.deepcopy(arrlist)


print ("排序self前的数组:")
for i in range(88):
    print ('%0.6d ' % arrlist[i], end=" ")

start_ = datetime.utcnow() 
QuickSort(arrlist)
end_ = datetime.utcnow()  
cdelt = (end_ - start_)  
print("\n排序self耗时: ====== ====== ====== ====== ====== ====== ====== == %.3fms" % (cdelt.microseconds))

print ("排序self后的数组:")
for i in range(88):
    print ('%d ' % arrlist[i], end=" ")

########################################################################

print ("\n排序sort前的数组:")

for i in range(88):
    print ('%d ' % arrlistso[i], end=" ")

start_ = datetime.utcnow() 
arrlistso.sort(key=None, reverse=False)
end_ = datetime.utcnow()  
cdelt = (end_ - start_)  
print("\n排序sort耗时: ====== ====== ====== ====== ====== ====== ====== == %.3fms" % (cdelt.microseconds))

print ("排序sort后的数组:")
for i in range(88):
    print ('%d ' % arrlistso[i], end=" ")

########################################################################

nparrlistjt=numpy.array(arrlistjt)
print ("\n排序npselfjitnp前的数组:")
for i in range(88):
    print ('%d ' % nparrlistjt[i], end=" ")

start_ = datetime.utcnow() 
QuickSortjit(nparrlistjt)
end_ = datetime.utcnow()  
cdelt = (end_ - start_)  
print("\n排序npselfjitnp耗时: ====== ====== ====== ====== ====== ====== == %.3fms" % (cdelt.microseconds))

print ("排序npselfjitnp后的数组:")
for i in range(88):
    print ('%d ' % nparrlistjt[i], end=" ")
print ("\n==============================")
########################################################################
'''  运行不了了
print ("\n排序selfjit前的数组:")
for i in range(88):
    print ('%d ' % arrlistjt[i], end=" ")

start_ = datetime.utcnow() 
QuickSortjit(arrlistjt)
end_ = datetime.utcnow()  
cdelt = (end_ - start_)  
print("\n排序selfjit耗时: ====== ====== ====== ====== ====== ====== ====== %.3fms" % (cdelt.microseconds))

print ("排序selfjit后的数组:")
for i in range(88):
    print ('%d ' % arrlistjt[i], end=" ")
print ("\n==============================")
'''