프로그래머가 마스터해야 할 상위 10가지 정렬 알고리즘(1부)

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이 문제 소개

정렬 알고리즘

모든 프로그래머가 이를 숙지해야 한다고 말할 수 있습니다

. 원리와 구현을 이해하는 것이 필요합니다

다음은 학습을 용이하게 하기 위해 일반적으로 사용되는 상위 10가지 정렬 알고리즘의 Python 구현에 대한 소개입니다.

01 버블 정렬 - 교환 정렬

02 퀵 정렬 - 교환 정렬

03 선택 정렬 - 선택 정렬 04 힙 정렬 - 선택 정렬

05 삽입 정렬 - 삽입 정렬

06 힐 정렬 - 삽입 정렬
07 병합 정렬 - 병합 정렬

08 계수 정렬 - 분포 정렬

09 기수 정렬 - 분포 정렬

10 버킷 정렬 - 분포 정렬

01

버블 정렬

고전적인 정렬 알고리즘입니다. 점차적으로 팝업처럼 물 바닥에 거품이 있어서 이름이 붙었습니다.

알고리즘 원리:

인접 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.
인접 요소의 모든 쌍에 대해 동일한 작업을 수행합니다. 시작 부분의 첫 번째 쌍부터 시작하여 끝 부분의 마지막 쌍으로 끝납니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.
마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
비교할 숫자 쌍이 더 이상 없을 때까지 매번 요소 수를 줄여 위 단계를 계속 반복하세요.

코드는 다음과 같습니다.

'''冒泡排序'''
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]

02

빨리 Sort

Quicksort:

전체 정렬 프로세스를 재귀적으로 수행할 수 있으므로 전체 데이터가 정렬된 시퀀스가 ​​됩니다. 이는 버블 정렬 알고리즘이 개선된 것입니다.

알고리즘 원리:

이 분할 값을 통해 배열을 왼쪽 부분과 오른쪽 부분으로 나눕니다.

• 컷오프 값보다 크거나 같은 데이터는 배열 오른쪽에 집중하고, 컷오프 값보다 작은 데이터는 배열 왼쪽에 집중합니다. 이때, 왼쪽 부분의 각 요소는 나누기 값보다 작거나 같고, 오른쪽 부분의 각 요소는 나누기 값보다 크거나 같습니다.

• 그러면 왼쪽과 오른쪽의 데이터를 독립적으로 정렬할 수 있습니다. 왼쪽 배열 데이터의 경우 나누기 값을 사용하여 데이터의 이 부분을 왼쪽과 오른쪽 부분으로 나눌 수 있습니다. 마찬가지로 왼쪽에 작은 값을 배치하고 오른쪽에 큰 값을 배치합니다. 오른쪽의 배열 데이터도 유사하게 처리할 수 있습니다.

• 왼쪽과 오른쪽 부분의 데이터 정렬이 완료될 때까지 위 과정을 반복하세요.

코드는 다음과 같습니다.

'''快速排序'''
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]

03

정렬 선택

선택 정렬: 간단하고 직관적인 정렬입니다. 연산. 어떤 데이터를 입력해도 시간 복잡도는 O(n²)입니다. 따라서 사용할 때에는 데이터 크기가 작을수록 좋습니다.

알고리즘 원리:

• 다음 위치에 저장합니다. 정렬된 시퀀스의 시작 위치입니다.

• 정렬되지 않은 나머지 요소 중에서 가장 작은(큰) 요소를 계속 찾아 정렬된 시퀀스의 마지막에 배치합니다.

• 등 모든 요소가 정렬될 때까지 계속됩니다.

代码如下：

'''选择排序'''
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(&#39;result list: &#39;, result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

04

插入排序

插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序'''
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(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

05

堆排序

堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

算法原理：

• 创建一个堆 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(&#39;result list: &#39;, result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]

위 내용은 프로그래머가 마스터해야 할 상위 10가지 정렬 알고리즘(1부)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!