프로그래머가 마스터해야 할 상위 10가지 정렬 알고리즘(1부)
- Python当打之年앞으로
- 2023-08-15 14:55:251090검색
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
03 선택 정렬 - 선택 정렬 04 힙 정렬 - 선택 정렬
05 삽입 정렬 - 삽입 정렬
06 힐 정렬 - 삽입 정렬
07 병합 정렬 - 병합 정렬
08 계수 정렬 - 분포 정렬 09 기수 정렬 - 분포 정렬 10 버킷 정렬 - 분포 정렬
- 인접 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.
'''冒泡排序'''
def Bubble_Sort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Bubble_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]-
컷오프 값보다 크거나 같은 데이터는 배열 오른쪽에 집중하고, 컷오프 값보다 작은 데이터는 배열 왼쪽에 집중합니다. 이때, 왼쪽 부분의 각 요소는 나누기 값보다 작거나 같고, 오른쪽 부분의 각 요소는 나누기 값보다 크거나 같습니다.
-
그러면 왼쪽과 오른쪽의 데이터를 독립적으로 정렬할 수 있습니다. 왼쪽 배열 데이터의 경우 나누기 값을 사용하여 데이터의 이 부분을 왼쪽과 오른쪽 부분으로 나눌 수 있습니다. 마찬가지로 왼쪽에 작은 값을 배치하고 오른쪽에 큰 값을 배치합니다. 오른쪽의 배열 데이터도 유사하게 처리할 수 있습니다.
-
왼쪽과 오른쪽 부분의 데이터 정렬이 완료될 때까지 위 과정을 반복하세요.
'''快速排序'''
def Quick_Sort(arr):
# 递归入口及出口
if len(arr) >= 2:
# 选取基准值，也可以选取第一个或最后一个元素
mid = arr[len(arr) // 2]
# 定义基准值左右两侧的列表
left, right = [], []
# 从原始数组中移除基准值
arr.remove(mid)
for num in arr:
if num >= mid:
right.append(num)
else:
left.append(num)
return Quick_Sort(left) + [mid] + Quick_Sort(right)
else:
return arr
arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]다음 위치에 저장합니다. 정렬된 시퀀스의 시작 위치입니다.
정렬되지 않은 나머지 요소 중에서 가장 작은(큰) 요소를 계속 찾아 정렬된 시퀀스의 마지막에 배치합니다.
등 모든 요소가 정렬될 때까지 계속됩니다.
'''选择排序'''
def Selection_Sort(arr):
for i in range(len(arr) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
'''插入排序'''
def Insertion_Sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Insertion_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
'''堆排序'''
def Heapify(arr, n, i):
largest = i
# 左右节点分块
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
# 大小值交换
arr[i], arr[largest] = arr[largest], arr[i]
# 递归
Heapify(arr, n, largest)
def Heap_Sort(arr):
nlen = len(arr)
for i in range(nlen, -1, -1):
# 调整节点
Heapify(arr, nlen, i)
for i in range(nlen - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
# 调整节点
Heapify(arr, i, 0)
return arr
arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75]
result = Heap_Sort(arr)
print('result list: ', result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]위 내용은 프로그래머가 마스터해야 할 상위 10가지 정렬 알고리즘(1부)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
이 기사는 Python当打之年에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제