거품 정렬 해석 및 최적화
3121 단어 데이터 구조
그의 규칙 은 첫 번 째 요소 와 두 번 째 요 소 를 비교 한 후에 요 소 를 이동 한 다음 에 두 번 째 요소 와 세 번 째 요 소 를 비교 하 는 것 이다. 이것 은 정렬 을 완성 하고 가장 큰 요 소 를 마지막 으로 배열 하 는 것 이다.이에 따라 두 번 째, 세 번 째 순 서 를 정렬 할 때 까지 진행 합 니 다.
먼저 실제 예 를 보 자.
일반적인 상황:
i 값 원 시퀀스: 10 3 7 8 5 2 1 4 9 6 교환 범위
1 첫 번 째: 3 7 8 5 2 1 4 9 6 10 [0—10-1)
2 두 번 째: 3 7 5 2 1 4 8 6 9 10 [0—10-2)
3 세 번 째: 3 5 2 1 4 7 6 8 9 10 [0—10-3)
4 네 번 째: 3 2 1 4 5 6 7 8 9 10 [0—10-4)
5 다섯 번 째: 2 1 3 4 5 6 7 8 9 10 [0—10-5)
6 여섯 번 째: 1 2 3 4 5 6 7 8 9 10 [0—10-6)
7 일곱 번 째: 1 2 3 4 5 6 7 8 9 10 [0—10-7)
8 여덟 번 째: 2 1 3 4 5 6 7 8 9 10 [0—10-8)
9 9 번 째: 1 2 3 4 5 6 7 8 9 10 [0—10-9)
그 일반적인 거품 정렬 은 바로 다음 과 같다.
#include
typedef int ElemType;
void BubbleSort(ElemType *arr,int length);
int main() {
using namespace std;
std::cout << "BubbleSort!" << std::endl;
ElemType arr[] = {90,80,70,60,30,20,10};
int length = sizeof(arr)/ sizeof(arr[0]);
BubbleSort(arr,length);
for (int i = 0; i < length; ++i) {
cout< arr[j+1]){//
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
시간 복잡 도: 가장 좋 은 상황 은 표 의 요소 가 정방 향 정렬 에 부합 되면 n - 1 회 만 비교 하면 정렬 이 완 료 됩 니 다. 그러나 프로그램 은 이것 이 완 료 된 줄 모 르 고 계속 실 행 됩 니 다. 그러면 실행 횟수 는 n - 1 + n (n - 1) / 2 + 교환 횟수 이 고 가장 좋 은 상황 교환 횟수 는 0 이 며 최 악 은 3 * n (n - 1) / 2 이 며 최종 의합 시간 복잡 도 는 O (n ^ 2) 입 니 다.
그렇다면 이미 기본적으로 질서 가 있 는 시계 에 대해 서 는 좀 더 빠 를 수 있 을 까? 시스템 에 이 시계 가 이미 정렬 되 었 다 는 것 을 알 릴 때 매번 실행 을 마치 고 시간 을 낭비 하지 않 아 도 된다 는 뜻 일 까?
나 는 컴퓨터 에 이 점 을 알 릴 수 있 는 유일한 것 은 컴퓨터 의 언어 로 그 에 게 알 리 는 것 이 바로 표지 위 치 를 설정 하 는 것 이 라 고 생각한다.
제 구상 은 교환 하 는 내외 에 표지 위 치 를 설정 하면 표지 의 서로 다른 상 태 를 나타 내 고 매번 if 문 에 들 어가 면 요 소 를 바 꾸 어 이번 에는 정렬 이 완성 되 지 않 았 음 을 증명 하 는 것 입 니 다. 만약 에 if 문 에 들 어가 지 않 았 다 면 순 서 를 완 성 했 기 때문에 계속 진행 하지 않 아 도 된다 는 것 을 의미 합 니 다.
코드 는 다음 과 같 습 니 다:
#include
#include
typedef int ElemType;
void BubbleSort(ElemType *arr,int length);
int main() {
using namespace std;
std::cout << "BubbleSort!" << std::endl;
ElemType arr[] = {90,80,70,60,30,20,10};
int length = sizeof(arr)/ sizeof(arr[0]);
BubbleSort(arr,length);
for (int i = 0; i < length; ++i) {
cout< arr[j+1]){//
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
CHANGE = true;// , true
}
}
}
}
최 악의 경우 거품 정렬 은 당연히 시간 복잡 도 를 바 꿀 수 없 지만, 가장 좋 은 상황 이나 이미 기본적으로 질서 가 있 는 수열 에 대해 서 는 시간 을 효과적으로 단축 시 킬 수 있다. 가장 좋 은 상황 을 비교 해 보면 수열 이 간단 하고 질서 가 있다 고 가정 하면 n - 1 번 만 비교 하면 함 수 를 끝 낼 수 있 으 며, 뒤의 조작 을 할 필요 가 없다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.