데이터 구조 -- Python 을 이용 하여 상용 정렬 알고리즘 을 실현 하 는 기본 적 인 사고방식 과 코드
54016 단어 데이터 구조
기본 사고방식: 거품 정렬 (Bubble Sort) 은 컴퓨터 과학 분야 의 간단 한 정렬 알고리즘 이다.그것 은 정렬 할 수열 을 반복 적 으로 방문 하여 한 번 에 두 요 소 를 비교 한 적 이 있 으 며, 만약 그들의 순서 가 틀 리 면 그들 을 교환 할 것 이다.이 알고리즘 의 이름 은 작은 요소 일수 록 수열 의 맨 위로 천천히 떠 오 르 고 무 거 운 요소 일수 록 천천히 끝까지 가라앉 기 때문에 '거품 정렬' 이 라 고 불 린 다.시간 복잡 도가 가장 빠르다: O (n).최 악: O (n ^ 2).주의해 라, 단점 은 매번 하나의 원소 만 확정 할 수 있다 는 것 이다.
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
def bubble_sort(my_list):
length = len(my_list)
# length， length-1
for i in range(1, length):
# ，
# ， ，
for i in range(0, length-i):
if my_list[i] > my_list[i+1]:
temp = my_list[i]
my_list[i] = my_list[i+1]
my_list[i+1] = temp
return my_list
if __name__ == '__main__':
my_list = [1, 4, 5, 7, 3, 9, 10, 24, 0]
new_mylist = bubble_sort(my_list)
print(new_mylist)2. 직접 삽입 법 정렬
기본 적 인 사고방식: 삽입 정렬 법 은 새로운 데 이 터 를 이미 배 열 된 데이터 에 직접 삽입 하고 배열 의 모든 요 소 를 앞 에 배 열 된 요소 와 순서대로 비교 하 는 것 이다. 만약 에 선택 한 요소 가 정렬 된 요소 보다 작 으 면 모든 요 소 를 비교 할 때 까지 교환한다. 시간 복잡 도 는 O (n ^ 2) 입 니 다.
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
def insert_sort(my_list):
# ， 0 ， 1
for i in range(1, len(my_list)):
# ， ，
# range(x-1,-1,-1): i-1 0
for j in range(i-1, -1, -1):
# ：
if my_list[j] > my_list[j+1]:
temp = my_list[j+1]
my_list[j+1] = my_list[j]
my_list[j] = temp
return my_list
if __name__ == '__main__':
my_list = [1, 2, 10, 3, 9, 4, 5, 7]
new_list = insert_sort(my_list)
print(new_list)3. 정렬 선택
기본 사고방식: 비교 + 교환.정렬 할 시퀀스 에서 가장 작은 요 소 를 찾 습 니 다.만약 에 최소 요소 가 정렬 대기 서열 의 첫 번 째 요소 가 아니라면 첫 번 째 요소 와 교환 합 니 다.남 은 N - 1 개 요소 에서 키워드 의 가장 작은 요 소 를 찾 아 정렬 이 끝 날 때 까지 반복 (1), (2) 단 계 를 반복 합 니 다.
시간 복잡 도: O (n ^ 2).
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
def select_sort(my_list):
#
for x in range(0, len(my_list)):
#
mixnum = my_list[x]
#
for i in range(x+1, len(my_list)):
if my_list[i] < mixnum:
temp = my_list[i]
my_list[i] = mixnum
mixnum = temp
#
my_list[x] = mixnum
return my_list
if __name__ == '__main__':
my_list = [2, 4, 1, 6, 7, 3, 9, 8]
new_list = select_sort(my_list)
print(new_list)더미 정렬
기본 사고방식:
큰 꼭대기 의 뿌리 노드 를 꺼 내 서 끝의 노드 와 교환 하고 만족 하 는 큰 꼭대기 의 전제 에서 중복 교환 을 하 며 나머지 어느 값 이 최소 치 입 니까?시간 복잡 도: O (n ^ 2)
쌓 아 올 리 는 개념: 쌓 아 올 리 는 것 은 큰 쌓 아 올 리 는 것 과 작은 쌓 아 올 리 는 것 으로 나 뉜 다.
큰 꼭대기 에 노드 의 요 소 는 모두 아이 보다 커 야 한다.
작은 지붕 더 미 는 노드 요소 가 모두 그 정도 보다 작 아야 한다.
더 미 를 이용 하여 정렬 하 는 것 은 큰 더 미 를 기반 으로 하거나 작은 더 미 를 기반 으로 하 는 정렬 방법 이다.한 번 은 큰 무 더 기 를 통 해 이 루어 진다.
python 언어 구현 코드 는 다음 과 같 습 니 다.
# ------------------------- --------------------------------
# ********** **********
def Left(i):
return 2*i + 1
def Right(i):
return 2*i + 2
# ********** **********
# L: length: i:
def adjust_max_header(L, length, i):
# int
largest = i
# ： ：1 ；2.
while True:
#
left, right = Left(i), Right(i)
# ， largest
if (left < length) and (L[left] > L[i]):
largest = left
print(' ', largest)
else:
largest = i
# ， largest
if (right < length) and (L[right] > L[largest]):
largest = right
print(' ', largest)
# largest i ，
if largest != i:
temp = L[i]
L[i] = L[largest]
L[largest] = temp
i = largest
continue
else:
break
return L
# ********** **********
def build_max_header(L):
length = len(L)
for x in range(int((length-1)/2), -1, -1):
adjust_max_header(L, length, x)
# ********** **********
def do_header_sort(L):
# ， ；
build_max_header(L)
# i： .
i = len(L)
# ：1. (len-1,len-2,len-3...)
# 2. ， ，
while i > 0:
temp = L[i-1]
L[i-1] = L[0]
L[0] = temp
# 1
i -= 1
#
adjust_max_header(L, i, 0)
return L
#
if __name__ == '__main__':
L = [2, 4, 3, 1, 7, 8, 9, 5, 10, 12, 11]
print(do_header_sort(L))
5. 빠 른 정렬
기본 적 인 사고: 시퀀스 에서 하나의 기준 수 (pivot) 를 선택 하 십시오.
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
# L： start index,end index
# length ：start = 0;end = length - 1
def quick_sort(L, start, end):
if start < end:
i, j, pivot = start, end, L[start]
while i < j:
# pivot
while (i < j) and (L[j] >= pivot):
j = j - 1
# pivot
if i < j:
L[i] = L[j]
i = i+1
# pivot
while (i < j) and (L[i] < pivot):
i = i+1
# pivot
if i < j:
L[j] = L[i]
j = j-1
# ， i=j， pivot, pivot
# pivot ，
# ： ： 0 ~ i-1// ： i+1 ~ end
L[i] = pivot
#
quick_sort(L, start, i-1)
#
quick_sort(L, i+1, end)
return L
if __name__ == '__main__':
L = [9, 7, 2, 1, 7, 5, 3, 4]
print(quick_sort(L, 0, len(L) - 1))
6. 힐 정렬
기본 적 인 사고방식: 정렬 대기 배열 을 보폭 에 따라 그룹 을 나 눈 다음 에 각 그룹의 요 소 를 정렬 에 직접 삽입 하 는 방법 으로 정렬 한다.매번 gap 를 반 으로 줄 이 고 상기 조작 을 순환 합 니 다.gap = 1 시 직접 삽입 을 이용 하여 정렬 을 완료 합 니 다.
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
def insert_shell(L):
# gap ，
gap = int(len(L)/2)
# ： gap
while gap >= 1:
# ：
# range(gap,len(L)): gap
for x in range(gap, len(L)):
# range(x-gap,-1,-gap): x-gap ， gap
for i in range(x-gap, -1, -gap):
# ，
if L[i] > L[i+gap]:
temp = L[i+gap]
L[i+gap] = L[i]
L[i] = temp
# while
gap = int(gap/2)
return L
if __name__ == '__main__':
L = [3, 2, 4, 6, 3, 9, 4, 2]
print(insert_shell(L))
7. 병합 정렬
기본 적 인 사고: 기 존의 하위 서열 을 합 쳐 완전 질서 있 는 서열 에 이 르 도록 한다.즉, 모든 하위 서열 을 질서 있 게 한 다음 에 하위 서열 을 질서 있 게 하 는 것 이다.
먼저 서열 을 매번 반 으로 나 눈 다음 에 분 단 된 서열 구간 의 두 순 서 를 합 친다.
python 언어 구현 코드 는 다음 과 같 습 니 다.
#
#
# L[first...mid] L[mid+1...last]
def mergearray(L,first,mid,last,temp):
# i,j,k
i, j, k = first, mid+1, 0
# ，
while (i <= mid) and (j <= last):
if L[i] <= L[j]:
temp[k] = L[i]
i = i+1
k = k+1
else:
temp[k] = L[j]
j = j+1
k = k+1
#
while i <= mid:
temp[k] = L[i]
i = i+1
k = k+1
#
while j <= last:
temp[k] = L[j]
j = j+1
k = k+1
# temp L
for x in range(0, k):
L[first+x] = temp[x]
#
def merge_sort(L,first,last,temp):
if first < last:
mid = int((first + last) / 2)
#
merge_sort(L, first, mid, temp)
#
merge_sort(L, mid+1, last, temp)
#
mergearray(L, first, mid, last, temp)
#
def merge_sort_array(L):
# len(L)
temp = len(L)*[None]
#
merge_sort(L, 0, len(L)-1, temp)
八、基数排序
基本思路：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]
对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束
python语言实现代码如下：
#************************ **************************** # # def radix_sort_nums(L): maxNum = L[0] # for x in L: if maxNum < x: maxNum = x # times = 0 while maxNum > 0: maxNum = (int)(maxNum/10) times = times+1 return times # num pos def get_num_pos(num,pos): return ((int)(num/(10**(pos-1))))%10 # def radix_sort(L): count = 10*[None] # bucket = len(L)*[None] # # for pos in range(1, radix_sort_nums(L)+1): # for x in range(0, 10): count[x] = 0 # ( ， ， ....) for x in range(0,len(L)): # j = get_num_pos(int(L[x]), pos) count[j] = count[j] + 1 # count[i] i for x in range(1, 10): count[x] = count[x] + count[x-1] # for x in range(len(L)-1, -1, -1): # K j = get_num_pos(L[x], pos) # ，count[j]-1 j bucket[count[j]-1] = L[x] # -1 count[j] = count[j]-1 # ， for x in range(0, len(L)): L[x] = bucket[x]八、桶排序（简化版：最简单最快速的排序）
基本思路：个人理解-逆向思维，首先将要排序的目标排序好，然后将出现的数值记录+1，形象的说就是，每出现一次，就将它放入对应的桶中，然后将出现的次数输出。
demo:
第一步：将分数按照大小排序，分数由0-100分构成，我们就定义一个数组int a[100] ,然后循环遍历数组的下标，将所有的下标对应的值初始化为0
# python ， a = [] for i in range(0, 101): # 0 a.append(0)
두 번 째 단계: 첫 번 째 단계 이후 에 우 리 는 100 개의 점 수 를 대표 하 는 목록 요소 가 생 겼 습 니 다. 0 으로 초기 화 되 었 습 니 다. 그러면 우리 의 사 고 는 모든 요소 가 하나의 '통' 을 대표 하고 나타 날 때마다 요 소 를 초기 화 하 는 값 을 + 1 로 대응 하 는 것 입 니 다. 즉, 목록 에서 (C 언어 는 배열 이 고 아래 표) 모든 요소 의 값 은 다음 표 (점수) 를 대표 합 니 다.출현 횟수 에 대응 하 다.# 5 for i in range(5): n = int(input(" %d :" % i)) a[n] += 1
세 번 째 단 계 는 이 목록 을 옮 겨 다 니 면 0 이상 의 요 소 를 출력 하고 해당 하 는 아래 표 (점수) 를 출력 합 니 다. 0 은 출력 하지 않 습 니 다 (나타 나 지 않 았 습 니 다). 값 이 얼마 인지 출력 합 니 다.# ， 0 ， ， for i in range(0, 101): for j in range(0, a[i]): print(i)
전체 코드 는 다음 과 같 습 니 다:# python ， a = [] for i in range(0, 101): # 0 a.append(0) # 5 for i in range(5): n = int(input(" %d :" % i)) a[n] += 1 # ， 0 ， ， for i in range(0, 101): for j in range(0, a[i]): print(i)
여기 서 통 정렬 은 간단 한 버 전의 통 정렬 일 뿐 진정한 의미 의 통 정렬 이 아 닙 니 다. 그러나 사상 은 이 렇 습 니 다. (개인 적 인 이 해 는 역방향 사고 이 고 문제 부터 시작 합 니 다) python 3 에서 배열 의 정의 가 없 기 때문에 목록 으로 대체 할 수 밖 에 없습니다. 코드 를 고민 하지 말고 이런 데이터 구조의 추상 적 인 사 고 를 배 워 야 합 니 다. 이렇게 밖 에 없습니다.너희들 의 물건 을 프로 그래 밍 할 수 있다.
통 정렬 의 가장 큰 문 제 는 데이터 가 수만 에 달 할 때 그 는 해당 하 는 공간 을 정의 해 야 하기 때문에 매우 낭비 된다 는 것 이다. 그래서 이렇게 공간 으로 시간 을 바 꾸 는 방법 은 믿 을 수 없다. 게다가 소수 가 정렬 할 방법 이 없 으 면 거품, 빠 른 배열, 선택, 직접 삽입, 힐 등 순 서 를 도입 했다.
요약:
데이터 양 이 적 을 때 이 여덟 가지 정렬 은 별 차이 가 없 을 것 이다.
하지만 데이터 양 이 수만, 심지어 수 십 만 에 이 르 면 격차 가 벌 어 진다.
실행 결 과 를 보면 쌓 기 정렬, 병합 정렬, 기수 정렬 이 다른 알고리즘 보다 훨씬 빠르다.
알림: 여기 서 순 서 는 C 언어 에서 순 서 를 매 기 는 가장 간단 한 사상 일 뿐 입 니 다. 깊이 연구 하고 발굴 하려 면 알고리즘 을 계속 최적화 처리 해 야 합 니 다. 나중에 시간 이 있 으 면 업데이트 해 드 리 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
