pythonバージョンソートアルゴリズム

6878 ワード
おすすめのブログですが、詳細な動図紹介があります.
ソートアルゴリズム
へいきんじかんふくざつさ
最悪時間複雑度
さいてきじかんふくざつさ
くうかんふくざつさ
あんていせい
クイックソート
ふあんてい
バブルソート
あんてい
ソートの挿入
あんてい
ソートの選択
ふあんてい
集計ソート
あんてい
ヒルソート
ふあんてい
ヒープのソート
ふあんてい
クイックソート
思想:1回の並べ替えによって並べ替えられる記録を独立した2つの部分に分け、そのうちの一部の記録のキーワードはいずれも他の部分のキーワードより小さい場合、この2つの部分をそれぞれ並べ替えることができ、つまり分治法の思想である.手順:
  • は、基準
    • として数列から1つの要素を選択する.
  • 再び数列を巡り、基準より小さいものを前に、基準より大きいものを後ろに、同じものを任意の辺に置くことができる
    • .
  • それからさっきの左と右に対して、それぞれ上の操作
    • に戻ります.
    不安定で、この時は二重サイクルではなく、時間複雑度O(nlogn)である.
    # ------ coding:utf-8 -----
'''
    
             ，          ，  、  、       
     、              
O(nlogn),   
'''

def quickSort(nums):
    if len(nums) <= 1:
        return nums
    base = nums[0]
    left = []
    equal = []
    right = []
    for num in nums:
        if num < base:
            left.append(num)
        elif num > base:
            right.append(num)
        else:
            equal.append(num)
    left = quickSort(left)
    right = quickSort(right)
    return left + equal + right

print quickSort([2,3,1,9,0,4,7,8,5])

    もう1つの一般的なその場ソートの実装方法があります.
    def quickSort2(nums, left, right):
    if left >= right:
        return
    low = left
    high = right
    base = nums[left]
    while left < right:
        while left < right and nums[right] > base:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= base:
            left += 1
        nums[right] = nums[left]
    nums[right] = base
    quickSort2(nums, low, left-1)
    quickSort2(nums, left+1, high)

    バブルソート
    思想:並べ替えられるシーケンスを繰り返し、2つの要素を一度に比較します.例えば、それらの間の順序が間違っている場合は、それらを交換します.バブルソートとは、小さな要素を前にし、大きな要素を後ろにすることです.1回のループ後、最大値は最後に表示されます.隣接する2つの要素を比較し、交換が必要かどうかも2つの要素の間で発生することに注意してください.手順:
  • は隣接する要素を比較し、第1の要素が第2の要素より大きい場合、それらを交換する
    • である.
  • シーケンスの最後まで繰り返し、このときシーケンスの最後の要素は最大の数
    • である.
  • 並べ替えが完了するまで繰り返します.
    今回のループでは、要素交換がない場合は停止し、ソート完了を表します.
    2つの要素が等しい場合、位置は交換されません.そのため、前の2台の交換で2つの要素を一緒に置いても、彼らの位置は交換されないので、泡のソートは安定しています.二重サイクル、時間複雑度O(n 2).
    # ------- coding:utf-8 ----
'''
    
        ，                
      O(n^2)，  
'''

def bubbleSort(nums):
    #              
    for i in range(len(nums)-1):
        count = 0   #        ，       ，   0  ，    
        #             
        for j in range(len(nums)-1-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                count += 1
        if count == 0:
            break
    return nums

print bubbleSort([1,2,7,8,3,1,9,0,5])

    ソートの挿入
    思想:秩序シーケンスを構築することによって、未順序データに対して、順序シーケンスの中で、後ろからお金にスキャンして、相応の位置を見つけて挿入します.手順:
  • は最初の要素から始まり、このときは秩序配列
    • である.
  • は次の要素を取り出し、順序付けされたシーケンスで後から前へスキャンし、順序付けされたシーケンスの現在の要素が並べ替えられる要素より大きい場合、順序付けされたシーケンスの要素が並べられる要素より小さいことを見つけるまで、その位置に挿入する(このような要素が見つからない場合は、一番前の位置に挿入する)
    • .
  • 上記の手順を繰り返し、配列要素
    • がないまで繰り返します.
    等しい要素の前後の順序は変更されていないので、挿入ソートは安定しています.二重サイクル、時間複雑度O(n 2).
    # ------ coding:utf-8 -----
'''
    
             ，        。      1   
O(n^2)，  
'''

def insertSort(nums):
    n = len(nums)
    for i in range(1, n):
        #                   
        for j in range(i, 0, -1):
            #                ，     ，        
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]
            else:
                break
    return nums

print insertSort([1,2,8,9,0,3,6,7,4])

    ソートの選択
    アイデア:まず、ソートされていないシーケンスで最小の要素を見つけ、ソートされたシーケンスの開始位置に保存し、残りのソートされていない要素から最小の要素を探し続け、ソートされたシーケンスの最後に配置します.
    「ソートの選択」は、ソートする要素の中で現在最も小さい要素を各場所に選択します.例えば、1番目の位置に最小を選択し、残りの要素の中で2番目の位置に小さいものを選択します.このように、n-1番目の要素まで、n番目の要素は選択しなくてもよい.例:5 8 5 2 9は,まず5と2を交換するので,2つの5の順序が交換されるので,選択ソートが不安定である.二重サイクル、時間複雑度O(n 2).
    # ------ coding:utf-8 -------
'''
    
                  （  ）
O(n^2)，   
'''

def selectSort(nums):
    n = len(nums)
    for i in range(n-1):
        min_dix = i
        for j in range(i+1, n):
            #          
            if nums[min_dix] > nums[j]:
                min_dix = j
        if i != min_dix:
            #            
            nums[i], nums[min_dix] = nums[min_dix], nums[i]
    return nums

print selectSort([1,2,0,4,9,8,5,4,7])

    集計ソート
    思想:分治法を採用し、2つの秩序化されたシーケンスを1つの秩序化されたシーケンスに統合し、完全な秩序化されたシーケンスを得る.すなわち,各サブシーケンスを秩序化してから,自己シーケンス間を秩序化する.2つの順序テーブルを1つの順序テーブルに統合すると、2-ルーティング集計になります.手順:
  • は、長さnのシーケンスを、長さn/2の2つのサブシーケンス
    • に分割する.
  • は、これら2つの自己シーケンスをそれぞれ集計ソート
    • を採用する.
  • は、2つの並べ替えられた自己シーケンスを1つの最終的な並べ替えシーケンス
    • に結合する.
    集計ソートの最初の状態は,n個の長さ1の秩序化自己シーケンスと見なすことができる.1つまたは2つの要素の場合、1つの要素は交換されず、2つの要素は大きさが等しければ交換されないので、安定しているこの場合は二重ループではなく、時間複雑度O(nlogn)
    # -------- coding:utf-8 ------
'''
    
                ，     n    1     
O(nlong),   
'''

def mergeSort(nums):
    #     n    1     
    if len(nums) <= 1:
        return nums
    mid_idx = len(nums) / 2 
    left_nums = mergeSort(nums[:mid_idx])   #             
    right_nums = mergeSort(nums[mid_idx:])  #            
    return merge(left_nums, right_nums) #                 

def merge(left_nums, right_nums):
    result = []
    left_idx, right_idx = 0, 0
    #               
    while left_idx < len(left_nums) and right_idx < len(right_nums):
        if left_nums[left_idx] < right_nums[right_idx]:
            result.append(left_nums[left_idx])
            left_idx += 1
        else:
            result.append(right_nums[right_idx])
            right_idx += 1
    #          
    result += left_nums[left_idx:]
    result += right_nums[right_idx:]
    return result

print mergeSort([1,2,0,9,4,5,8,7,3])

    ヒルソート
    思想:ヒルソートは縮小増分ソートとも呼ばれる.ソートを簡単に挿入する改良版ですが、距離の遠い要素が好ましい点が異なります.手順:
  • 増分シーケンスを選択:5 3 2 1
    • のように
  • インクリメンタルシーケンス個数kでk回ソートを行い、上記の例は4回ソート
    • である.
  • の各ソートは、対応するインクリメントに基づいて、器をいくつかの長さmのサブシーケンスに分割する、その後、各サブテーブルに対して直接挿入ソート
    • を行う.
    通常、実装の過程で、初期増分step=len(nums)/2、後のstep/=2を指定することなく、増分シーケンスを指定することができる.
    def shellSort(nums):
   n = len(nums)
   step = n / 2
   while step >= 1:
       for i in range(step, n):
           for j in range(i, 0, -step):
               if nums[j] < nums[j - step]:
                   nums[j], nums[j - step] = nums[j - step], nums[j]
               else:
                   break
       step /= 2
   return nums

    同じ数は1回のstepでは同じ自己配列ではない可能性があるため,この過程で位置が変化する可能性があるため,ヒルソートは不安定である.
    ヒープのソート
    思想:スタックソートは完全な二叉木に基づいており、大きなスタックを例にとると、大きなスタックは各ノードが自分の子供ノードより大きいか等しいかを表す.手順:
  • 長さnの配列をスタック秩序化して大きなトップスタック構造にするプロセスは、n個のノードがある場合、n/2-1~0個のノードを1個ずつ検査することである.これらのノードには子供ノードがあるだけで、子供ノードより小さい場合、子供ノードと交換する
    • である.
  • 大天井のルートノードとテールノードを交換
    • .
  • 残りのn-1ノード
    • をチェック
  • 上記の手順を繰り返し、大屋根スタックに1つのノード
    • しかないまで
    bintrayリリース再入坑
    Igniteメッセージとイベント