Python을 사용하여 다양한 정렬 알고리즘 구현

일반적인 중앙 집중식 정렬 알고리즘 요약

병합 정렬

병합 정렬이라고도 불리는 병합 정렬은 분할 및 정렬의 일반적인 응용 프로그램입니다. - 정복 방법. 분할 정복의 개념은 각 문제를 작은 문제로 분해하고 각각의 작은 문제를 해결한 다음 병합하는 것입니다.

특정 병합 정렬은 순서가 지정되지 않은 숫자 집합을 n/2로 단 하나의 요소가 있는 하위 항목으로 재귀적으로 분해하는 것이며, 하나의 요소는 이미 정렬되어 있습니다. 그런 다음 순서가 지정된 하위 요소를 병합합니다.

병합 과정은 정렬된 두 하위 시퀀스를 비교하여 먼저 두 하위 시퀀스에서 가장 작은 요소를 선택하고 두 요소 중 가장 작은 하위 시퀀스를 선택한 다음 하위 시퀀스에서 제거하는 것입니다.

제거 및 두 하위 시퀀스가 ​​병합될 때까지 최종 결과 세트에 추가합니다.

코드는 다음과 같습니다.

#!/usr/bin/python  
import sys  
   
def merge(nums, first, middle, last):  
    ''''' merge '''  
    # 切片边界,左闭右开并且是了0为开始  
    lnums = nums[first:middle+1]   
    rnums = nums[middle+1:last+1]  
    lnums.append(sys.maxint)  
    rnums.append(sys.maxint)  
    l = 0  
    r = 0  
    for i in range(first, last+1):  
        if lnums[l] < rnums[r]:  
            nums[i] = lnums[l]  
            l+=1  
        else:  
            nums[i] = rnums[r]  
            r+=1  
def merge_sort(nums, first, last):  
    &#39;&#39;&#39;&#39;&#39; merge sort 
    merge_sort函数中传递的是下标，不是元素个数 
    &#39;&#39;&#39;  
    if first < last:  
        middle = (first + last)/2  
        merge_sort(nums, first, middle)  
        merge_sort(nums, middle+1, last)  
        merge(nums, first, middle,last)  
   
if __name__ == &#39;__main__&#39;:  
    nums = [10,8,4,-1,2,6,7,3]  
    print &#39;nums is:&#39;, nums  
    merge_sort(nums, 0, 7)  
    print &#39;merge sort:&#39;, nums

안정적, 시간 복잡도 O(nlog n)

삽입 정렬

코드는 다음과 같습니다.

#!/usr/bin/python  
import sys  
   
def insert_sort(a):  
    ''''' 插入排序 
    有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数， 
    但要求插入后此数据序列仍然有序。刚开始 一个元素显然有序，然后插入一 
    个元素到适当位置，然后再插入第三个元素，依次类推 
    '''  
    a_len = len(a)  
    if a_len = 0 and a[j] > key:  
            a[j+1] = a[j]  
            j-=1  
        a[j+1] = key  
    return a  
   
if __name__ == '__main__':  
    nums = [10,8,4,-1,2,6,7,3]  
    print 'nums is:', nums  
    insert_sort(nums)  
    print 'insert sort:', nums

안정적, 시간복잡도 O(n^2)

교환 두 요소 파이썬에서는 다음과 같이 쓸 수 있습니다: a, b = b, a. 사실 이는 할당 기호의 왼쪽과 오른쪽이 튜플이기 때문입니다

(여기서 강조할 필요가 있는 것은 파이썬에서는 , 튜플은 실제로 괄호 대신 쉼표 ","로 구분됩니다.

선택 정렬

선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식은 다음과 같습니다. 먼저, 정렬되지 않은 시퀀스에서 가장 작은(큰) 요소를 찾아

정렬된 시퀀스의 시작 위치에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은(큰) 요소를 찾고, 그런 다음 정렬된 순서의 끝에 넣습니다. 모든

요소가 정렬될 때까지 계속됩니다.

import sys  
def select_sort(a):  
    ''''' 选择排序  
    每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 
    顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 
    选择排序是不稳定的排序方法。 
    '''  
    a_len=len(a)  
    for i in range(a_len):#在0-n-1上依次选择相应大小的元素   
        min_index = i#记录最小元素的下标   
        for j in range(i+1, a_len):#查找最小值  
            if(a[j]<a[min_index]):  
                min_index=j  
        if min_index != i:#找到最小元素进行交换  
            a[i],a[min_index] = a[min_index],a[i]  
   
if __name__ == &#39;__main__&#39;:  
    A = [10, -3, 5, 7, 1, 3, 7]    
    print &#39;Before sort:&#39;,A    
    select_sort(A)    
    print &#39;After sort:&#39;,A

불안정, 시간 복잡도 O(n^2)

힐 정렬

힐 정렬이라고도 함 내림차순 증분 정렬 알고리즘인 Hill 정렬은 비안정 정렬 알고리즘입니다. 이 방법은 DL이기 때문에 증분 정렬 감소라고도 합니다. Shell은 1959년에 제안된 이름을 따서 명명되었습니다.

먼저 n보다 작은 정수 d1을 첫 번째 증분으로 취하고 파일의 모든 레코드를 d1 그룹으로 나눕니다. 거리가 d1의 배수인 모든 레코드는 동일한 그룹에 배치됩니다. 각 그룹 내에서 첫 번째 정렬

그런 다음 두 번째 증분 d2

import sys  
def shell_sort(a):  
    ''''' shell排序  
    '''  
    a_len=len(a)  
    gap=a_len/2#增量  
    while gap>0:  
        for i in range(a_len):#对同一个组进行选择排序  
            m=i  
            j=i+1  
            while j<a_len:  
                if a[j]<a[m]:  
                    m=j  
                j+=gap#j增加gap  
            if m!=i:  
                a[m],a[i]=a[i],a[m]  
        gap/=2  
   
if __name__ == &#39;__main__&#39;:  
    A = [10, -3, 5, 7, 1, 3, 7]    
    print &#39;Before sort:&#39;,A    
    shell_sort(A)    
    print &#39;After sort:&#39;,A

불안정, 시간 복잡도 평균 시간 O(nlogn) 최악의 시간 O(n^s)1

힙 정렬(Heap Sort)

"힙"의 정의: 시작 인덱스가 0인 "힙"에서:

노드 i의 오른쪽 하위 노드는 위치 2 * i + 24) 노드 i의 상위 노드는 바닥((i - 1) / 2) 위치에 있습니다. 바닥은 "반올림" 연산을 나타냅니다.

힙의 특성:

키 각 노드의 값은 항상 상위 노드보다 크거나 작아야 합니다.

"최대 힙":

"힙"의 루트 노드는 가장 큰 키 값을 가진 노드를 저장합니다. . 즉, "힙"에 있는 각 노드의 키 값은 항상 해당 하위 노드보다 큽니다.

위로 이동, 아래로 이동:

노드의 키 값이 상위 노드보다 크면 "위로 이동" 작업을 수행해야 합니다. 노드를 상위 노드

의 위치로 이동하고 상위 노드가 해당 위치에 도달하도록 한 다음 노드를 계속 판단하고 노드가 더 이상 노드보다 크지 않을 때까지 "위로 이동"을 멈추지 않습니다. 상위 노드.

이제 "아래로 이동" 작업을 살펴보겠습니다. 노드의 키 값을 더 작은 값으로 변경할 때는 "아래로 이동"해야 합니다.

방법:

먼저 최대 힙(시간 복잡도 O(n))을 구축한 다음 매번 루트 노드를 마지막 위치의 노드와 교환하면 되며, 그런 다음 마지막 One 위치를 제외하고 교환 후 루트 노드의 힙이 조정됩니다(시간 복잡도 O(lgn)). 즉, 루트 노드가 "아래로 이동"됩니다. 힙 정렬의 전체 시간 복잡도는 O(nlgn)

코드는 다음과 같습니다.

#!/usr/bin env python  
   
# 数组编号从 0开始  
def left(i):  
    return 2*i +1  
def right(i):  
    return 2*i+2  
   
#保持最大堆性质 使以i为根的子树成为最大堆  
def max_heapify(A, i, heap_size):  
    if heap_size <= 0:  
        return   
    l = left(i)  
    r = right(i)  
    largest = i # 选出子节点中较大的节点  
    if l  A[largest]:  
        largest = l  
    if r  A[largest]:  
        largest = r  
    if i != largest :#说明当前节点不是最大的，下移  
        A[i], A[largest] = A[largest], A[i] #交换  
        max_heapify(A, largest, heap_size)#继续追踪下移的点  
    #print A  
# 建堆    
def bulid_max_heap(A):  
    heap_size = len(A)  
    if heap_size >1:  
        node = heap_size/2 -1  
        while node >= 0:  
           max_heapify(A, node, heap_size)  
           node -=1  
   
# 堆排序 下标从0开始  
def heap_sort(A):  
    bulid_max_heap(A)  
    heap_size = len(A)  
    i = heap_size - 1   
    while i > 0 :  
        A[0],A[i] = A[i], A[0] # 堆中的最大值存入数组适当的位置，并且进行交换  
        heap_size -=1 # heap 大小 递减 1  
        i -= 1 # 存放堆中最大值的下标递减 1  
        max_heapify(A, 0, heap_size)  
   
if __name__ == &#39;__main__&#39; :  
   
    A = [10, -3, 5, 7, 1, 3, 7]  
    print &#39;Before sort:&#39;,A  
    heap_sort(A)  
    print &#39;After sort:&#39;,A

불안정, 시간 복잡도 O(nlog n)

퀵 정렬

퀵 정렬 알고리즘도 병합 정렬 알고리즘과 마찬가지로 분할 정복 모델을 기반으로 합니다. 하위 배열 A[p...r]을 빠르게 정렬하는 분할 정복 프로세스의 세 단계는 다음과 같습니다.

분해: 배열 A[p...r]을 A[p]로 나눕니다. ..q -1] 및 A[q+1...r], 여기서 A[p...q-1]의 각 요소는 A[q] 및 A[q+1..보다 작거나 같습니다. .r ] 의 각 요소는 A[q]보다 크거나 같습니다.

해결책: 빠른 정렬을 재귀적으로 호출하고 하위 배열 A[p...q-1]과 A[q+1을 쌍으로 만듭니다. ... r] 정렬

병합: 두 하위 배열이 제자리에 정렬되므로 추가 작업이 필요하지 않습니다.

파티션 파티션의 각 반복 시작 시 x=A[r], 임의의 배열 첨자 k에 대해 다음이 있습니다.

1) p≤k≤i이면 A[ k] ≤x.

2) i+1≤k≤j-1이면 A[k]>x입니다.

3) k=r이면 A[k]=x입니다.

코드는 다음과 같습니다.

#!/usr/bin/env python  
# 快速排序  
''''' 
划分 使满足 以A[r]为基准对数组进行一个划分，比A[r]小的放在左边， 
   比A[r]大的放在右边 
快速排序的分治partition过程有两种方法， 
一种是上面所述的两个指针索引一前一后逐步向后扫描的方法, 
另一种方法是两个指针从首位向中间扫描的方法。 
'''  
#p,r 是数组A的下标  
def partition1(A, p ,r):  
    ''''' 
      方法一，两个指针索引一前一后逐步向后扫描的方法 
    '''  
    x = A[r]  
    i = p-1  
    j = p  
    while j < r:  
        if A[j] < x:  
            i +=1  
            A[i], A[j] = A[j], A[i]  
        j += 1  
    A[i+1], A[r] = A[r], A[i+1]  
    return i+1  
   
def partition2(A, p, r):  
    &#39;&#39;&#39;&#39;&#39; 
    两个指针从首尾向中间扫描的方法 
    &#39;&#39;&#39;  
    i = p  
    j = r  
    x = A[p]  
    while i = x and i < j:  
            j -=1  
        A[i] = A[j]  
        while A[i]<=x and i < j:  
            i +=1  
        A[j] = A[i]  
    A[i] = x  
    return i  
   
# quick sort  
def quick_sort(A, p, r):  
    &#39;&#39;&#39;&#39;&#39; 
        快速排序的最差时间复杂度为O(n2)，平时时间复杂度为O(nlgn) 
    &#39;&#39;&#39;  
    if p < r:  
        q = partition2(A, p, r)  
        quick_sort(A, p, q-1)  
        quick_sort(A, q+1, r)  
   
if __name__ == &#39;__main__&#39;:  
   
    A = [5,-4,6,3,7,11,1,2]  
    print &#39;Before sort:&#39;,A  
    quick_sort(A, 0, 7)  
    print &#39;After sort:&#39;,A

불안정합니다. 가장 좋은 시간 복잡도는 O(nlogn)이고 가장 나쁜 시간은 O(n^2)입니다.

파이썬의 시퀀스에 대해 이야기해 보겠습니다.

목록, 튜플 및 문자열입니다. 모든 시퀀스가 ​​있지만 시퀀스란 무엇이며 왜 그렇게 특별한가요? 시퀀스의 두 가지 주요 기능은 인덱싱 연산자와 슬라이싱 연산자입니다. 인덱스 연산자를 사용하면 시퀀스에서 특정 항목을 가져올 수 있습니다. 슬라이스 연산자를 사용하면 다음과 같이 시퀀스의 조각, 즉 시퀀스의 일부를 얻을 수 있습니다. a = ['aa','bb','cc'], print a[0]은 인덱스 연산입니다. , 슬라이싱 작업을 위해 a[0:2]를 인쇄합니다.