Python은 8개의 정렬 알고리즘을 구현합니다.

파이썬을 이용한 8가지 정렬 알고리즘 구현

1. 삽입 정렬
설명
삽입 정렬(Insertion Sort) 기본 연산은 정렬된 정렬된 데이터에 데이터 조각을 삽입하여 숫자에 1을 더한 새로운 정렬된 데이터를 얻는 것입니다. 이 알고리즘은 적은 양의 데이터를 정렬하는 데 적합하며 시간 복잡도는 O(n)입니다. ^ 2). 안정적인 정렬 방법입니다. 삽입 알고리즘은 정렬할 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 마지막 요소를 제외한 배열의 모든 요소가 포함되며(배열에 삽입 위치를 확보할 수 있는 공간이 하나 더 추가됨) 두 번째 부분에는 이 요소만 포함됩니다. 하나의 요소(즉, 삽입할 요소). 첫 번째 부분이 정렬된 후 이 마지막 요소가 정렬된 첫 번째 부분에 삽입됩니다.
코드 구현

으으으

2. 🎜>
설명 쉘 정렬은 삽입 정렬의 한 종류입니다. 증분 정렬 감소라고도 하며, 직접 삽입 정렬 알고리즘보다 효율적이고 향상된 버전입니다. Hill 정렬은 불안정한 정렬 알고리즘입니다. 이 방법은 DL 때문입니다. Shell은 1959년 제안된 이름을 따서 명명되었습니다. Hill 정렬은 첨자의 특정 증분으로 그룹을 기록하고 직접 삽입 정렬 알고리즘을 사용하여 각 그룹을 정렬합니다. 증분이 점차 감소함에 따라 각 그룹에는 점점 더 많은 키워드가 포함되며 전체 파일이 그룹화됩니다. 정확히 하나의 그룹으로 분류되고 알고리즘이 종료됩니다.

코드 구현

아아앙

3. 🎜>

설명
정렬할 순서를 반복적으로 진행하면서 두 요소를 한 번에 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 코드 구현


아아아아

4. 🎜>

설명

한 번의 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나눕니다. 한 부분의 모든 데이터가 다른 부분의 모든 데이터보다 작습니다. 그런 다음 이 방법을 사용하면 데이터의 두 부분을 각각 빠르게 정렬할 수 있습니다. 전체 정렬 프로세스를 반복적으로 수행하면 전체 데이터가 정렬된 시퀀스가 ​​됩니다. 코드 구현

 def insert_sort(lists): 
  # 插入排序 
  count = len(lists) 
  for i in range(1, count): 
    key = lists[i] 
    j = i - 1 
    while j >= 0: 
      if lists[j] > key: 
        lists[j + 1] = lists[j] 
        lists[j] = key 
      j -= 1 
  return lists

5. 직접 선택 정렬

설명

기본 아이디어: 첫 번째 패스에서는 r1 ~ r[n]으로 정렬할 레코드 중 가장 작은 레코드를 선택하고 이를 r1과 교환합니다. 2 패스는 r2 ~ r[n] 정렬할 레코드 중에서 가장 작은 레코드를 선택하고 r2와 교환하는 식으로 i 번째 패스는 r[i] ~ 정렬할 레코드 중에서 가장 작은 레코드를 선택합니다. r[n] 레코드를 r[i]와 교환하면 모든 정렬이 완료될 때까지 순서가 지정된 시퀀스가 ​​계속 증가합니다. 코드 구현

rree

6. 🎜>

설명

힙 정렬(Heapsort)은 스택 트리(힙)와 같은 데이터 구조를 이용하여 설계된 정렬 알고리즘의 일종이다. 배열의 특성을 사용하여 지정된 인덱스에서 요소를 빠르게 찾을 수 있습니다. 힙은 큰 루트 힙과 작은 루트 힙으로 나누어지며 이는 완전한 이진 트리입니다. 큰 루트 힙의 요구 사항은 각 노드의 값이 해당 상위 노드의 값, 즉 A[PARENT[i]] >= A[i]보다 크지 않아야 한다는 것입니다. 배열의 비내림차순 정렬에서는 큰 루트 힙의 요구 사항에 따라 가장 큰 값이 힙의 맨 위에 있어야 하기 때문에 큰 루트 힙을 사용해야 합니다.

코드 구현
rreee

7、归并排序
描述 
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。 
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否 则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复 制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序， 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。 
代码实现

 def merge(left, right): 
  i, j = 0, 0 
  result = [] 
  while i < len(left) and j < len(right): 
    if left[i] <= right[j]: 
      result.append(left[i]) 
      i += 1 
    else: 
      result.append(right[j]) 
      j += 1 
  result += left[i:] 
  result += right[j:] 
  return result 
 
def merge_sort(lists): 
  # 归并排序 
  if len(lists) <= 1: 
    return lists 
  num = len(lists) / 2 
  left = merge_sort(lists[:num]) 
  right = merge_sort(lists[num:]) 
  return merge(left, right)

8、基数排序
描述 
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
代码实现

 import math 
def radix_sort(lists, radix=10): 
  k = int(math.ceil(math.log(max(lists), radix))) 
  bucket = [[] for i in range(radix)] 
  for i in range(1, k+1): 
    for j in lists: 
      bucket[j/(radix**(i-1)) % (radix**i)].append(j) 
    del lists[:] 
    for z in bucket: 
      lists += z 
      del z[:] 
  return lists

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Python实现八大排序算法相关文章请关注PHP中文网！