バブルソート、選択ソート、挿入ソート、ヒルソート、クイックソート、集計ソートの6つのソートの概要

Pythonテクノロジー共有グループ:556993881
注!以下の方法で実現するのはすべて小さいから大きいまで配列します
1、泡立ち順
意味:
1、仮定:最初の数が最大値であると仮定し、
2、順次比較:最初の数と後の各数を比較し、
3、置換:大きい人は「最大値」と置換し、後の比較を続けます.
4、最大値を得る:最後の1つまで比較して、本当の最大値を最後に置く
5、縮尺繰り返し実行:一度修正したシーケンスを得た後、1、2、3を繰り返し、最後から2番目のビットまで比較すればよい(最後から1番目のビットは前回比較したが、最大の値である)この時に得られるのは大きい値で、最後から2番目のビットに置く
6、........このように,大きなデータは泡のように次から次へとゆっくりと後ろの位置に浮かび上がり,大きな秩序配列から小さい秩序配列を得た.

#    
def bubble_sort1(li):
    n = len(li)
    for j in range(n-1):  #   n-1 ， 0  
        for i in range(n-1-j):  #   （n-1）-1 ，      
            if li[i] > li[i+1]:  #   
                li[i], li[i+1] = li[i+1], li[i]  #   


#                    j ，        
def bubble_sort2(li):
    n = len(li)
    for j in range(n-1, 0, -1):  #     ,      
        for i in range(j):
            if li[i] > li[i+1]:
                li[i], li[i+1] = li[i+1], li[i]

#   
l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
bubble_sort1(l)

bubble/ˈbʌb(ə)l/気泡

       :O(n^2)
       :O(n) (         )
  

2、ソートの選択
意味:
1、タグ:変数を探して最初の値を記録する下付き文字
2、遍歴比較:その後ろから最後の値まで遍歴し、この最初の値と比較する
3、下付き文字の変更:より小さい場合、より小さい値の下付き文字を記録する
4、置換:1回のループの終了で、最初の値と下の値を置換する
5、2番目の値から、1、2、3、4を続けます
6、.......このようにして、最後から2番目の値まで遍歴比較します.

def select_sort(li):
    n = len(li)
    for j in range(n-1):  #   n-1 ， 0  
        temp = j
        for i in range(j+1, n):  #       
            if li[i] < li[temp]:  #   
                temp = i  #     
        li[j], li[temp] = li[temp], li[j]  #   

#   
l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
select_sort(l)

       :O(n^2)
       :O(n^2)
   (        8,      8        )

3、ソートの挿入
意味:
1、順序付けシーケンスの分割:最初の要素を順序付けシーケンスとして扱う
2、逐次比較:後の1つの要素と前の秩序序列の中のすべての要素を順次後から前へ比較する
3、位置を入れ替える:要素をそれより大きいものと交換し、正しい位置が見つかるまで
4、......このように、シーケンス内のすべての要素を左から右にすべて決定します.

#    
def insert_sort(li):
    n = len(li)
    for j in range(n-1):
        for i in range(j+1, 0, -1):
            if li[i] < li[i-1]:
                li[i], li[i-1] = li[i-1], li[i]

#    
def insert_sort(li):
    n = len(li)
    for j in range(1,  n): 
        for i in range(j, 0, -1): 
            if li[i] < li[i-1]:
                li[i], li[i-1] = li[i-1], li[i]

#   
l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
insert_sort(l)

       :O(n^2)
       :O(n)
  

4、ヒルソート
意味:
1、ステップ長の設定:ステップ長をシーケンス長の半分に設定する;
2、比較:ステップ長後の要素から前(自分とは異なるステップ長の要素)に比較する.
3、交换:小さいのは前で、大きいのは后で、更に前に1つのステップの长さを移动してまた数値が自分より大きいならば前へ比较し続けて、自分より小さいあるいは差のステップの长い要素が存在しないまで;
4、歩幅の調整:歩幅を前回の半分にする(自分の好みで歩幅を分けることもできるが、最後に必ず1回の歩幅の比較が必要で、挿入順に相当する)
5、3箇所の交換がわかりにくいので、コードを実行して、心を静めて分析してください

def shell_sort(li):
    n = len(li)
    gap = n//2  # gap:  ,    ∆x
    while gap > 0:
        for i in range(gap, n):  #   ~  
            # i, i+1 ,i+2
            while i-gap >= 0:  #                    
                if li[i] < li[i - gap]:
                    li[i], li[i - gap] = li[i - gap], li[i]
                    i -= gap
                else:
                    break
        gap -= 1

#   
l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
shell_sort(l)

     :O(n) < O < O(n^2),             ,           
   

5、クイックソート
二分法を用いる
1、中間値を設定する:最初の要素を中間値と仮定し、
2、リストの最后の1位から右から左へ他の要素を比较して、小さいのと第1位の交换に出会って、
3、次に方向を変えて、1位の次の位から左から右へ比較されていない要素を(中間値)と比較し、2の右と大きく交換された要素に遭遇して交換する.
4、方向を再び右から左に変えて、順番に類推して、2、3を繰り返して、すべての要素が分割されるまで
最終的な効果はそれより小さいものを左に、それより大きいものを右に置くことです.
5、繰り返し1,2,3,4:左の半分を1,2,3,4,右の半分も1,2,3,4,
6、続いて分けた小序列を分岐して、更に区分して、ここで再帰(再帰を知らないで、自分で食糧を補充する)を使った.
7、1、2、3の区分手順は分かりにくいので、図面を手順に従って実行することをお勧めします.

# coding:utf8
def quick_sort(list_temp, start, end):
	"""      ,     ,     """
	if start >= end:
		#                       ,      ,    
		return

	low = start
	high = end
	mid = list_temp[start]  #            

	while low < high:
		#        
		while low < high and mid <= list_temp[high]:
			high -= 1
		list_temp[low] = list_temp[high]
		#        
		#            ,             ,      ,          ,       
		while low < high and list_temp[low] < mid:
			low += 1
		list_temp[high] = list_temp[low]

	list_temp[high] = mid

	#   
	quick_sort(list_temp, start, high-1)
	#   
	quick_sort(list_temp, high+1, end)


if __name__ == '__main__':	
	#   
	l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
	quick_sort(l, 0, len(l)-1)
	print(l)

       ：O(nlogn)
       ：O(n2)
   

6、集計ソート
意味:
1、シーケンスを絶えず2つに分けて1つの要素しかないまで(1つの要素の時は必ず秩序あるシーケンスで、自分だけだから);
2、さらに分割したシーケンスを2つ持って比較サイズを合併し、新しい秩序シーケンスを得る.
3、この秩序シーケンスを次のシーケンスとマージする.
4、.......すべての分割された要素が結合されるまで、このようにします.

# coding:utf8
def merge_sort(li):
	"""       """
	if len(li) == 1:
		#     ,    1 ,       ,      
		return li

	mid = len(li) // 2
	left_li = li[:mid]
	right_li = li[mid:]

	#     ,      
	new_l_list = merge_sort(left_li)
	#     ,      
	new_r_list = merge_sort(right_li)

	#              
	new_sort_nums = merge(new_l_list, new_r_list)
	#       
	return new_sort_nums

def merge(left_li, right_li):
	"""                 ,            """
	result = []  #     
	l_index = 0  #       
	r_index = 0  #       

	while l_index < len(left_li) and r_index < len(right_li):
		if left_li[l_index] <= right_li[r_index]:
			result.append(left_li[l_index])
			l_index += 1
		else:
			result.append(right_li[r_index])
			r_index += 1

	#                     ,               (            )
	result += left_li[l_index:]
	result += right_li[r_index:]

	return result


if __name__ == '__main__':
    #   
    l = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
    print(merge_sort(l))

構想運行大体ステップ:

 
  
 
  
   :
  
[3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
コード左後右:
  :                    :
  
[3, 0, 1, 8, 7]       [2, 5, 4, 9, 6]
  
[3, 0]   [1, 8, 7]    [2, 5]   [4, 9, 6]
  
[3] [0]  [1] [8, 7]   [2] [5]  [4] [9, 6]
  
           [8] [7]               [9] [6]
  
[0, 3]                [2, 5]
  
[7, 8]                [6, 9]
  
[1, 7, 8]             [4, 6, 9]
  
[0, 1, 3, 7, 8]       [2, 4, 5, 6, 9]
  
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  
       :O(nlogn)
       :O(nlogn)
  
  
やれやれ寝床、やっと見終わった!!!これは仲間たちの心の声かもしれないが、私もやっと終わったと言いたい..
今cpythonを勉强しているので、Pythonバージョンを贴って、大きいPythonが私を连れて飞ぶことができることを望みます~~~~~
python---->q群:556993881へようこそ