Einführung in diese AusgabeSortieralgorithmus Man kann sagen, dass jeder Programmierer es beherrschen muss Es ist notwendig, deren Prinzipien und Implementierung zu verstehen Das Folgende ist eine Einführung in die Python-Implementierung der zehn am häufigsten verwendeten Sortieralgorithmen, um Ihnen das Lernen zu erleichtern.
01 Blasensortierung – Austauschsortierung 02 Schnellsortierung – Austauschsortierung
03 Auswahlsortierung – Auswahlsortierung 04 Heapsortierung – Auswahlsortierung
05 Einfügungssortierung - Einfügungsklassensortierung
06 Hügelsortierung - Einfügungsklassensortierung
07 Zusammenführungssortierung - Zusammenführungsklassensortierung
08. Anzahl Sortierung - Verteilungssortierung 09 Radix-Sortierung – Verteilungssortierung
10 Bucket-Sortierung – Verteilungssortierung
Hill Sort. (S Höllensortierung): ist Einfügungssortierung Eins, auch bekannt als „Vermindernd“. „Inkrementelle Sortierung“ (Diminishing Increment Sort) ist eine effizientere und verbesserte Version des Sortieralgorithmus mit direkter Einfügung. Nehmen Sie eine ganzzahlige Lücke (die Lücke wird als Schrittgröße bezeichnet). ), das kleiner als n ist. Die zu sortierenden Elemente Werden in mehrere Gruppenuntersequenzen unterteilt, werden alle Datensätze, deren Abstand ein Vielfaches der Lücke ist, in derselben Gruppe platziertDie Elemente in jeder Gruppe werden direkt eingefügt und sortiert Reduzieren Sie den Lückenwert in der Reihenfolge Der Code lautet wie folgt: '''希尔排序'''
def Shell_Sort(arr):
# 设定步长,注意类型
step = int(len(arr) / 2)
while step > 0:
for i in range(step, len(arr)):
# 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
while i >= step and arr[i - step] > arr[i]:
arr[i], arr[i - step] = arr[i - step], arr[i]
i -= step
step = int(step / 2)
return arr
arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Shell_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]Nach dem Login kopieren
Platz so anlegen, dass seine Größe die Summe aus beiden ist Dieser Speicherplatz wird zum Speichern verwendet Die zusammengeführte Sequenz. Die Sequenz
legt zwei Indizes fest. Die anfänglichen Indexpositionen sind die Startpositionen der beiden sortierten Sequenzen
- Wählen Sie die relativ kleinen Elemente im Zusammenführungsbereich aus und verschieben Sie den
Index an die nächste Position
Wiederholen Sie den vorherigen Schritt, bis ein bestimmter Index- das Ende der Sequenz überschreitet
und entfernen Sie alle verbleibenden Elemente der anderen Sequenz. Elemente werden direkt an das Ende der zusammengeführten Sequenz kopiert
'''归并排序'''def Merge(left, right):
arr = []
i = j = 0
while j < len(left) and i < len(right):
if left[j] < right[i]:
arr.append(left[j])
j += 1
else:
arr.append(right[i])
i += 1
if j == len(left):
# right遍历完
for k in right[i:]:
arr.append(k)
else:
# left遍历完
for k in left[j:]:
arr.append(k)
return arr
def Merge_Sort(arr):
# 递归结束条件
if len(arr) <= 1:
return arr
# 二分
middle = len(arr) // 2
left = Merge_Sort(arr[:middle])
right = Merge_Sort(arr[middle:])
# 合并
return Merge(left, right)
arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Merge_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]Nach dem Login kopieren
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
'''计数排序'''
def Count_Sort(arr):
max_num = max(arr)
min_num = min(arr)
count_num = max_num - min_num + 1
count_arr = [0 for i in range(count_num)]
res = [0 for i in range(len(arr))]
# 统计数字出现的次数
for i in arr:
count_arr[i - min_num] += 1
# 统计前面有几个比自己小的数
for j in range(1, count_num):
count_arr[j] = count_arr[j] + count_arr[j - 1]
# 遍历重组
for k in range(len(arr)):
res[count_arr[arr[k] - min_num] - 1] = arr[k]
count_arr[arr[k] - min_num] -= 1
return res
arr = [5, 10, 76, 55, 13, 79, 5, 49, 51, 65, 30, 5]
result = Count_Sort(arr)
print('result list: ', result)
# result list: [5, 5, 5, 10, 13, 30, 49, 51, 55, 65, 76, 79]Nach dem Login kopieren
'''基数排序'''
def Radix_Sort(arr):
max_num = max(arr)
place = 0
while 10 ** place <= max_num:
# 创建桶
buckets = [[] for _ in range(10)]
# 分桶
for item in arr:
pos = item // 10 ** place % 10
buckets[pos].append(item)
j = 0
for k in range(10):
for num in buckets[k]:
arr[j] = num
j += 1
place += 1
return arr
arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Radix_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]Nach dem Login kopieren
计算有限桶的数量
逐个桶内部排序
遍历每个桶，进行合并
'''桶排序'''
def Bucket_Sort(arr):
num = max(arr)
# 列表置零
pre_lst = [0] * num
result = []
for data in arr:
pre_lst[data - 1] += 1
i = 0
while i < len(pre_lst): # 遍历生成的列表，从小到大
j = 0
while j < pre_lst[i]:
result.append(i + 1)
j += 1
i += 1
return result
arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75]
result = Bucket_Sort(arr)
print('result list: ', result)
# result list: [4, 5, 5, 21, 26, 46, 53, 72, 75, 83, 86]Nach dem Login kopieren
Das obige ist der detaillierte Inhalt vonDie zehn wichtigsten Sortieralgorithmen, die Programmierer beherrschen müssen (Teil 2). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
