Pythonによる基本並べ替えアルゴリズム02-選択並べ替え
935 ワード
一、ソートを選択する核心思想
(小さいものから大きいものへのソートを例に、合計N個の要素を仮定)
バブルソートは、左側の値がより大きいことが発見されるたびに、交換されます.(詳細は、http://blog.csdn.net/pospro/article/details/47984469)
選択したソートは、まず1回繰り返し、最大値の座標を見つけてから、その値を適切な位置と交換します.「選択」の最大値が表示される場所は、ソート名が選ばれた理由でしょう.
考え方:
計画は小さいころからの到着順に並べられています.つまり、最大値は右端に配置されます.
1.全ての要素を巡り、最大値がある位置を見つけ、最大値が一番右側(即ち[N-1])でない場合、その位置の数を[N-1]と交換する
2.元素0~N-2を遍歴し、最大値の位置を見つけて[N-2]に交換する
...
N-1元素0~1を遍歴し、最大元素を見つけ、その出位置1を確保する
二、プログラムの実例
三、テスト
興味があれば、プログラム中のprint文の前の#を外して、次のテストプログラムを実行することができます(テストプログラムはhttp://blog.csdn.net/pospro/article/details/47984469)
(小さいものから大きいものへのソートを例に、合計N個の要素を仮定)
バブルソートは、左側の値がより大きいことが発見されるたびに、交換されます.(詳細は、http://blog.csdn.net/pospro/article/details/47984469)
選択したソートは、まず1回繰り返し、最大値の座標を見つけてから、その値を適切な位置と交換します.「選択」の最大値が表示される場所は、ソート名が選ばれた理由でしょう.
考え方:
計画は小さいころからの到着順に並べられています.つまり、最大値は右端に配置されます.
1.全ての要素を巡り、最大値がある位置を見つけ、最大値が一番右側(即ち[N-1])でない場合、その位置の数を[N-1]と交換する
2.元素0~N-2を遍歴し、最大値の位置を見つけて[N-2]に交換する
...
N-1元素0~1を遍歴し、最大元素を見つけ、その出位置1を確保する
二、プログラムの実例
def selectionSort(alist):
n=len(alist)
for i in range(n,1,-1): # i=(n,n-1,n-2.....2)
maxpos=0
for j in range(i): #j=(0,1,2,....i-1)
if alist[maxpos]<alist[j]:
maxpos=j
if not maxpos==i-1: # ,
alist[maxpos],alist[i-1]=alist[i-1],alist[maxpos]
#print alist
三、テスト
興味があれば、プログラム中のprint文の前の#を外して、次のテストプログラムを実行することができます(テストプログラムはhttp://blog.csdn.net/pospro/article/details/47984469)