Python 버블 정렬 알고리즘에 대한 자세한 그래픽 설명

이 글은 python에 대한 관련 지식을 제공합니다. 알고리즘 설명, 분석, 코드 구현 등 버블 정렬과 관련된 내용을 주로 소개합니다. 여러분에게 도움이 되기를 바랍니다. 도움이됩니다.

추천 학습: python 동영상 튜토리얼

1. 알고리즘 설명

Bubble Sort(버블 정렬)은 간단한 정렬 알고리즘입니다. 정렬할 배열을 반복적으로 반복하여 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 배열을 순회하는 작업이 반복됩니다. 이는 배열이 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.

2. 알고리즘 분석

1. 인접 요소를 비교합니다. 첫 번째가 두 번째보다 큰 경우(오름차순) 둘 다 바꿉니다.

2. 시작 부분의 첫 번째 쌍부터 끝 부분의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이 단계가 완료되면 최종 요소는 가장 큰 숫자가 됩니다.

3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

4. 비교할 숫자 쌍이 없을 때까지 점점 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다.

그런 다음 n-1 버블링 프로세스를 수행해야 하며 각 시간에 해당하는 비교 횟수는 아래 그림과 같습니다.

3 이해하려면 애니메이션 표시

실행 프로세스를 살펴보겠습니다:

4. 코드 구현

다음과 같은 순서가 없는 목록을 정렬합니다

실행 코드:

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)

실행 결과:

5 . 알고리즘 업그레이드

는 루프에서 변수 개수를 정의합니다. 첫 번째 루프 이후 개수가 변경되지 않으면 입력이 순서가 지정된 시퀀스임을 의미합니다. 현재 시간 복잡도는 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)

실행 결과:

6. 시간 복잡도 분석

• 최적 시간 복잡도 : 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)

안정성: 안정적

🎜🎜🎜정렬 분석: 정렬할 배열의 총 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(N)입니다. ^2). 🎜🎜🎜🎜🎜추천 학습: 🎜python 비디오 튜토리얼🎜🎜

위 내용은 Python 버블 정렬 알고리즘에 대한 자세한 그래픽 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!