python基本ソートアルゴリズム

一、泡立ちソート
このアルゴリズムの名前の由来は、大きな元素が交換を通じて徐々に数列の先端(昇順または降順配列)に「浮上」し、炭酸飲料中の二酸化炭素の気泡が最終的に先端に浮上するように「泡ソート」されるからだ.
バブルソートアルゴリズムの原理は次のとおりです.
隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.
各ペアの隣接要素に対して同じ作業を行い、最初のペアから最後のペアまで行います.この点では、最後の要素が最大の数になるはずです.
最後の1つを除いて、すべての要素について上記の手順を繰り返します.
比較する必要がなくなるまで、ますます少ない要素に対して上記の手順を繰り返します.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

li = [99, 0, -1, 46, -87, 7, 17, 20]

le = len(li)  #   8

for i in range(le):  # [0,7]                    ，              。
    for j in range(le - i - 1):  #               ，      。
        if li[j + 1] > li[j]:  #        。          ，       。
            li[j], li[j + 1] = li[j + 1], li[j]
            #     break，

print(li)

二、ソートの選択
選択ソートは、単純で直感的なソートアルゴリズムです.ソート対象のデータ要素から最小(または最大)の要素を選択するたびに、シーケンスの開始位置に格納し、残りのソートされていない要素から最小(大)の要素を探し続け、ソートされたシーケンスの最後に配置するのが原理です.このようにして、ソートされるすべてのデータ要素が整列するまで押します.ソートの選択は不安定なソート方法です.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

li = [99, 0, -1, 46, -87, 7, 17, 20]

le = len(li)  #   8

for i in range(le):  # [0,7]
    max_val = i  #         ，     i    
    for j in range(i + 1, le):  #                      
        if li[j] > li[max_val]:  #               ，      
            max_val = j
    li[i], li[max_val] = li[max_val], li[i]  #       i   ，              ，       i   ，
print(li)

なぜ私たちが選択ソートを回収するのは不安定なソートですか?簡単に言えば、すべての等しい数が何らかのソート方法を経ても、ソート前の相対的な順序を維持することができ、このソート方法は安定していると言います.逆に、非安定です.たとえば[1,1,1,1,1,1,1,1]を並べ替えますが、実際に並べ替えた後、1つずつの順序は変化しないのか、元の色で置くのが安定した並べ替えなのか.つまりソート後もそうである[1,1,1,1,1,1,1,1]
三、挿入順序
挿入ソートは、単純で直感的で安定したソートアルゴリズムです.順序付けされたデータ・シーケンスがある場合、この順序付けされたデータ・シーケンスに数を挿入する必要がありますが、挿入後も順序付けされている必要があります.この場合、新しい順序付け方法が使用されます.順序付けを挿入する基本的な操作は、順序付けされた順序付けデータにデータを挿入し、新しい順序付けされた順序付けデータを得ることです.アルゴリズムは少量のデータの並べ替えに適用され,時間複雑度はO(n^2)であった.安定したソート方法です.挿入アルゴリズムは、ソートする配列を2つの部分に分けます.第1の部分には、この配列のすべての要素が含まれていますが、最後の要素を除いて(配列の複数の空間に挿入された位置があるようにします)、第2の部分には、この要素(すなわち、挿入される要素)しか含まれていません.最初の部分のソートが完了したら、最後の要素をソートされた最初の部分に挿入します.
ソートを挿入する基本的な考え方は、ステップごとにソートされるレコードをキー値の大きさで前にソートされたファイルの適切な位置に挿入し、すべて挿入が完了するまで挿入することです.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
li = [9, 0, -1, 46, -87, 7, 17, 20]

le = len(li)  #   8

k = 0  #       
for i in range(1, le):
    val = li[i]  #                   
    j = i
    while j > 0 and li[j - 1] < val:  #     j  0  and            
        li[j] = li[j - 1]  #          ，        
        j -= 1  #          
        k += 1
    li[j] = val  #                  val      , val    
print(li)
print(k)

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
1）      i、j，       ：i=0，j=N-1；
2）              ，   key， key=A[0]；
3） j      ，         (j--)，       key  A[j]， A[j] A[i]  ；
4） i      ，         (i++)，       key A[i]， A[i] A[j]  ；
5）   3、4 ，  i=j； (3,4  ，         ， 3 A[j]   key,4 A[i]   key     j、i  ，  j=j-1，i=i+1，
      。        ，       i， j      。  ，i==j         i+ j-     ，       ）。
"""
li = [9, 0, -1, 46, -87, 7, 17, 20]

le = len(li)


def QuickSort(li, start, end):
    #   end      start  ,   false,    
    if start < end:
        i, j = start, end
        #      
        base = li[i]
        while i < j:
            #         ,        ,                 
            while (i < j) and (li[j] >= base):
                j = j - 1
            #    ,   j          i,    i,j     
            li[i] = li[j]
            #           
            while (i < j) and (li[i] <= base):
                i = i + 1
            li[j] = li[i]
        #          ,          ,  i=j,         base
        li[i] = base
        #       
        QuickSort(li, start, i - 1)
        QuickSort(li, j + 1, end)
    return li


sortli = QuickSort(li, 0, le - 1)
print(sortli)

五、集計ソート
集計ソートは集計操作に確立された有効なソートアルゴリズムであり、このアルゴリズムは分治法を採用する非常に典型的な応用である.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2ウェイ集計と呼ばれます.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)

    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = int(len(lists) / 2)
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)


if __name__ == '__main__':
    li = [9, 0, -1, 46, -87, 7, 17, 20, 2]
    print(merge_sort(li))