Python을 사용하여 8가지 정렬 알고리즘 구현 - 빠른 정렬-파이썬 튜토리얼-php.cn

Python을 사용하여 8가지 정렬 알고리즘 구현 - 빠른 정렬

巴扎黑

풀어 주다： 2016-12-03 11:23:37

원래의

935명이 탐색했습니다.

빠른 정렬의 기본 아이디어:

한 번의 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 분할합니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작습니다. 를 누른 후 이것을 누르세요. 이 방법은 이 두 부분의 데이터에 대해 각각 빠른 정렬을 수행하며 전체 정렬 과정을 반복적으로 수행하여 전체 데이터가 정렬되도록 할 수 있습니다.

예:

arr = [49,38,04,97,76,13,27,49,55,65], 오른쪽부터 첫 번째 숫자 49를 키 값으로 설정 왼쪽의 키 값보다 작은 숫자를 찾아 첫 번째 숫자에 할당합니다.

arr = [27,38,04,97,76,13,27,49,55, 65], 그런 다음 첫 번째 왼쪽에서 오른쪽으로 키 값보다 큰 숫자를 찾고 오른쪽에서 왼쪽으로 찾은 마지막 숫자에 찾은 숫자를 할당합니다.

arr = [27,38,04,97; ,76 ,13,97,49,55,65] 그런 다음 오른쪽에서 왼쪽으로, 왼쪽에서 오른쪽으로, 왼쪽=오른쪽이 될 때까지 루프를 중단하고 키 값을 일부 인덱스 값에 할당합니다. 마지막으로 양쪽의 그룹을 반복합니다.

코드:

def quick_sort(lists, left, right):
    #快速排序
    if left >= right:  #当递归调用的分组为1个数时返回列表
        return lists
    key = lists[left]  #保存key值，在一轮调用结束时，存到中间值
    low = left
    high = right  #供递归调用时使用
    while left < right:  #通过下面两个循环依次交替赋值并使key值两侧为大小分组
        while left < right and lists[right] >= key:  
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left-1)  #对key值左侧进行排序分组
    quick_sort(lists, left+1, high)  #对key值右侧进行排序分组
    return lists

로그인 후 복사