python一般的なソートアルゴリズムの実装(二)

クイックソート
高速ソートはバブルソートの改良である.その実現原理は、1回のソートによってソートするデータを独立した2つの部分に分割することであり、その一部のすべてのデータは他の部分のすべてのデータよりも小さくなり、この方法で2つの部分のデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行うことができ、データ全体が秩序化されたシーケンスになることを達成することができる.

#coding: utf-8 
#!/usr/bin/python   
import random

#    0~100     
def get_andomNumber(num):  
    lists=[]  
    i=0  
    while i= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists


a = get_andomNumber(10)
print("    ：%s" %a)

b = quick_sort(a,0,len(a)-1)

print("    ：%s" %b)

     
ヒープのソート
スタックソートは、ツリー選択ソートであり、直接選択ソートの効果的な改善です.
スタックの定義は、n個の要素を有するシーケンス(h 1,h 2,...,hn)であり、(hi>=h 2 i,hi>=2 i+1)または(hi<=h 2 i,hi<=2 i+1)(i=1,2,...,n/2)を満たす場合にのみスタックと呼ぶ.ここでは前者の条件を満たすスタックのみについて議論する.スタックの定義から、スタックトップ要素(すなわち、最初の要素)は必ず最大の項目(大スタック)であることがわかります.完全二叉木はスタックの構造を直感的に表すことができる.スタックトップはルートで、その他は左サブツリー、右サブツリーです.
では、スタックソートとは、私たちが最初にソートする数のシーケンスを1本の順序で格納する二叉木と見なし、それらの格納シーケンスを調整してスタックにし、このときスタックのルートノードの数が最大になるようにすることです.次に、ルートノードをスタックの最後のノードと交換します.次に前(n−1)の個数をスタックとして再調整する.このようにして,2つのノードのみのスタックに至るまでそれらを交換し,最後にn個のノードの秩序化シーケンスを得た.アルゴリズムの記述から,スタック並べ替えには2つのプロセスが必要であり,1つはスタックの構築であり,2つはスタックトップとスタックの最後の要素交換位置である.スタックソートには2つの関数があります.1つはスタックの浸透関数であり,2つは浸透関数を繰り返し呼び出して並べ替えを実現する関数である.

#coding: utf-8 
#!/usr/bin/python   
import random
import math

#    0~100     
def get_andomNumber(num):  
    lists=[]  
    i=0  
    while i lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

#    
def build_heap(lists, size):
    for i in range(0, (int(size/2)))[::-1]:
        adjust_heap(lists, i, size)

#    
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)
    return lists


a = get_andomNumber(10)
print("    ：%s" %a)

b = heap_sort(a)

print("    ：%s" %b)