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

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

이 문제 소개

정렬 알고리즘

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

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

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

01 버블 정렬 - 교환 정렬

02 퀵 정렬 - 교환 정렬

03 선택 정렬 - 선택 정렬

04 힙 정렬 - 선택 정렬

05 삽입 정렬 - 삽입 클래스 정렬 06 힐 정렬 - 삽입 클래스 정렬

07 병합 정렬 - 병합 클래스 정렬

08 정렬 - 분포 정렬

09 기수 정렬 - 분포 정렬

10 버킷 정렬 - 분포 정렬

06

Hill 정렬

Hill정렬(She ll Sort): 는 삽입 정렬 1이며 "Diminishing"이라고도 함 증분 정렬"(감소 증분 정렬)은 직접 삽입 정렬 알고리즘의 보다 효율적이고 향상된 버전입니다.

알고리즘 원리:

• 정수 간격을 취합니다. ( 간격을 단계 크기라고 함) n보다 작습니다. 정렬할 요소입니다. 여러 그룹 하위 시퀀스로 나누어 간격의 배수인 모든 레코드는 동일한 그룹에 배치됩니다.

• 각 그룹의 요소는 직접 삽입되고 정렬됩니다. 순서대로 gap 값을 줄여서

• 위의 그룹화와 정렬을 반복

• 위의 작업을 반복하고 gap=1이면 정렬이 종료됩니다

코드는 다음과 같습니다

'''希尔排序'''
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]

07

병합 정렬

Merge Sort: 은 병합 작업을 기반으로 하는 효과적이고 안정적인 정렬 알고리즘입니다. 이 알고리즘은 분할 및 정복 방법을 사용합니다. 완전히 정렬된 시퀀스를 얻으려면 하위 시퀀스를 사용하세요.

알고리즘 원리:

• 크기가 두 가지의 합이 되도록 공간을 신청하세요. 이 공간은 시퀀스를 저장하는 데 사용됩니다. 병합된 시퀀스

• 는 두 개의 인덱스를 설정합니다. 초기 index 위치는 두 개의 정렬된 시퀀스

• 의 시작 위치입니다. 상대적으로 작은 요소를 병합 공간으로 선택하고 index를 다음 위치

• 로 이동합니다. 특정

  index가 시퀀스의 끝을 초과할 때까지 이전 단계를 반복합니다

• 다른 시퀀스의 나머지 요소를 모두 제거합니다. 요소는 병합된 시퀀스의 끝에 직접 복사됩니다

代码如下：

'''归并排序'''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(&#39;result list: &#39;, result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

08

计数排序

计数排序（Count sort）：是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

算法原理：

• 找出待排序的数组中最大和最小的元素

• 统计数组中每个值为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]

09

基数排序

基数排序（radix sort）：是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法原理（以LSD为例）：

• 根据个位数的数值，遍历列表将它们分配至编号0到9的桶子中
  

• 将这些桶子中的数值重新串接起来

• 根据十位数的数值，遍历列表将它们分配至编号0到9的桶子中

• 再将这些桶子中的数值重新串接起来
  

代码如下：

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

10

桶排序

桶排序 (Bucket sort)或所谓的箱排序：划分多个范围相同的桶区间，每个桶自排序，最后合并，桶排序可以看作是计数排序的扩展。

算法原理：

• 计算有限桶的数量
  

• 逐个桶内部排序

• 遍历每个桶，进行合并

代码如下：

'''桶排序'''
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(&#39;result list: &#39;, result)
# result list: [4, 5, 5, 21, 26, 46, 53, 72, 75, 83, 86]

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