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)

두 요소의 값을 교환하려면 Python에서 다음과 같이 작성할 수 있습니다. 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

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]进行排序；

合并：因为两个子数组是就地排序的，所以不需要额外的操作。

对于划分partition 每一轮迭代的开始，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)

说下python中的序列：

列表、元组和字符串都是序列，但是序列是什么，它们为什么如此特别呢？序列的两个主要特点是索引操作符和切片操作符。索引操作符让我们可以从序列中抓取一个特定项目。切片操作符让我们能够获取序列的一个切片，即一部分序列,如：a = ['aa','bb','cc'], print a[0] 为索引操作，print a[0:2]为切片操作。