이 글은 python에 대한 관련 지식을 제공합니다. 알고리즘 설명, 분석, 코드 구현 등 버블 정렬과 관련된 내용을 주로 소개합니다. 여러분에게 도움이 되기를 바랍니다. 도움이됩니다.
추천 학습: python 동영상 튜토리얼
Bubble Sort(버블 정렬)은 간단한 정렬 알고리즘입니다. 정렬할 배열을 반복적으로 반복하여 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 배열을 순회하는 작업이 반복됩니다. 이는 배열이 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.
1. 인접 요소를 비교합니다. 첫 번째가 두 번째보다 큰 경우(오름차순) 둘 다 바꿉니다.
2. 시작 부분의 첫 번째 쌍부터 끝 부분의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이 단계가 완료되면 최종 요소는 가장 큰 숫자가 됩니다.
3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
4. 비교할 숫자 쌍이 없을 때까지 점점 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다.
그런 다음 n-1 버블링 프로세스를 수행해야 하며 각 시간에 해당하는 비교 횟수는 아래 그림과 같습니다.
실행 프로세스를 살펴보겠습니다:
다음과 같은 순서가 없는 목록을 정렬합니다
실행 코드:
import timepop_list = [19, 14, 10, 4, 15, 26, 20, 96]print("没排序前的列表为：", pop_list)# 记录开始时间start = time.time()# 外层循环控制轮数for i in range(len(pop_list) - 1):
# 内层循环控制比较次数
for j in range(len(pop_list) - i - 1):
# 如果前一个数字比后一个数字大，就交换位置
if pop_list[j] > pop_list[j + 1]:
# python特有交换位置方式
pop_list[j], pop_list[j + 1] = pop_list[j + 1], pop_list[j]print("排序好的列表为：", pop_list)# 记录结束时间end = time.time()print("算法总耗时：", end - start)
실행 결과:
는 루프에서 변수 개수를 정의합니다. 첫 번째 루프 이후 개수가 변경되지 않으면 입력이 순서가 지정된 시퀀스임을 의미합니다. 현재 시간 복잡도는
O(n)
구현 코드:
import timedef bubble_sort(pop_list):
for j in range(len(pop_list) - 1, 0, -1):
count = 0
for i in range(0, j):
if pop_list[i] > pop_list[i + 1]:
pop_list[i], pop_list[i + 1] = pop_list[i + 1], pop_list[i]
count += 1
if count == 0:
returnpop_list = [19, 14, 10, 4, 15, 26, 20, 96]print("没排序前的列表为：", pop_list)# 记录开始时间start = time.time()bubble_sort(pop_list)print("排序好的列表为：", pop_list)# 记录结束时间end = time.time()print("算法总耗时：", end - start)
실행 결과: 
🎜🎜🎜정렬 분석: 정렬할 배열의 총 8개 숫자, 첫 번째 정렬에서 7번의 비교, 두 번째 정렬에서 6번의 비교 등이 이루어졌으며 마지막 라운드에서는 1번의 비교가 이루어졌습니다.가장 나쁜 시간 복잡도:
- 최적 시간 복잡도 :
O(n)(한 번 순회한 후 교환할 수 있는 요소가 없는 것으로 확인되어 정렬이 종료됨을 나타냄) .)O(n)（表示遍历一次发现没有任何可以交换的元素，排序结束。）- 最坏时间复杂度：
O(n^2)- 稳定性：稳定
- 排序分析：待排数组中一共有8个数，第一轮排序时进行了7次比较，第二轮排序时进行了6比较，依次类推，最后一轮进行了1次比较。
- 数组元素总数为N时，则一共需要的比较次数为：
(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2- 算法约做了
N^2/2次比较。因为只有在前面的元素比后面的元素大时才交换数据，所以交换的次数少于比较的次数。如果数据是随机的，大概有一半数据需要交换，则交换的次数为N^2/4（不过在最坏情况下，即初始数据逆序时，每次比较都需要交换）。- 交换和比较的操作次数都与 N^2 成正比，由于在大O表示法中，常数忽略不计，冒泡排序的时间复杂度为
O(N^2)O(n^2)
(N-1)+ (N-2)+ (N-3)입니다. + .. .1=N*(N-1)/2N^2/2 비교를 수행합니다. 앞의 요소가 뒤의 요소보다 큰 경우에만 데이터를 교환하므로 교환 횟수는 비교 횟수보다 적습니다. 데이터가 랜덤이고 절반 정도의 데이터를 교환해야 하는 경우 교환 횟수는 N^2/4이지만 최악의 경우 초기 데이터가 역순인 경우 각 비교에는 교환이 필요합니다). O(N)입니다. ^2). 🎜🎜🎜🎜🎜추천 학습: 🎜python 비디오 튜토리얼🎜🎜위 내용은 Python 버블 정렬 알고리즘에 대한 자세한 그래픽 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!