Python 정렬 알고리즘 요약 및 예

이 글은 주로 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)

삽입 sort

코드는 다음과 같습니다.

#!/usr/bin/python 
importsys 
 
definsert_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라고 쓰면 됩니다. 사실 할당 기호의 왼쪽과 오른쪽이 튜플이기 때문입니다

(여기서 강조할 필요가 있는 점은 python 에서 튜플은 실제로 대괄호 대신 쉼표 ","로 구분된다는 것입니다).

선택 정렬

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

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

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

아아아아

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

힐 정렬

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

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

그런 다음 두 번째 증분 d2

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(nlogn) 최악의 시간 O(n^s)1

힙 정렬(Heap Sort)

"힙"의 정의: 처음에 "힙"에 인덱스 0:

노드 i의 오른쪽 하위 노드는 위치 2 * i + 24에 있습니다. 노드 i의 상위 노드는 바닥((i – 1) / 2) 위치에 있습니다. 바닥은 "를 의미합니다. 반올림" 연산

힙의 특성:

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

"최대 힙":

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

위로 이동, 아래로 이동:

노드의 키 값이 상위 노드보다 크면 "위로 이동" 작업을 수행해야 합니다. 노드를 상위 노드의 위치로 이동하고 상위 노드를 해당 위치로 이동시킨 다음 노드를 계속 판단하고 노드가 더 이상 상위 노드보다 크지 않을 때까지 "위로 이동"을 멈추지 않습니다.

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

방법:

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

의 코드는 다음과 같습니다.

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(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 
 
# 数组编号从 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(nlogn)이고 가장 나쁜 시간은 O(n^2)입니다.

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

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

이 글을 통해 Python 정렬 알고리즘에 대한 지식을 습득하고 싶습니다. 이 사이트를 지원해 주셔서 감사합니다!

Python 정렬 알고리즘 요약 및 예제와 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!