복습 데이터 구조: 정렬 알고리즘 (2) - 거품 정렬
이 복습 은 거품 을 일 으 켜 정렬 된다.
거품 정렬 도 안정 적 인 정렬, 내부 정렬 이다. 거품 정렬 의 기본 사상: 현재 아직 순서 가 정 해 지지 않 은 범위 안의 모든 수 를 위 에서 아래로 인접 한 두 수 를 순서대로 비교 하고 조정 하여 비교적 큰 수 를 아래로 가라앉 히 고 작은 것 을 위로 올 리 도록 한다.즉, 서로 인접 한 수 를 비교 한 후에 그들의 정렬 이 정렬 요구 와 반대 되 는 것 을 발견 할 때마다 서로 바 꾸 는 것 이다.삽입 정렬 이 거품 정렬 보다 빠 릅 니 다!
위 에서 말 한 것 은 일반적인 거품 정렬 알고리즘 입 니 다. 시간 복잡 도 는 O (n ^ 2) 입 니 다. 이런 방법 은 정렬 작업 에서 최대 치 나 최소 치 만 찾 을 수 있 고 시간 이 너무 많이 소 모 됩 니 다.
개선 방법 1: 우 리 는 매 정렬 에서 정방 향 과 역방향 으로 두 번 거품 을 일 으 키 는 방법 을 할 수 있 습 니 다. 한 번 에 최대 치 와 최소 치 를 동시에 얻 을 수 있 습 니 다. 그러면 정렬 의 횟수 가 절반 으로 줄 어 듭 니 다.이런 방법 은 이미 지 를 보면 진동 소 구 와 같다. 만약 에 양 끝 에 최대 치 와 최소 치 를 선택 했다 면 다음 에 정렬 할 때 정렬 의 거 리 를 좁 히 고 뒤에 진동 하 는 폭 이 줄 어 들 것 이다. 그 폭 이 0 이면 진동 소 구 는 저 니 의 존재 로 인해 멈 출 때 까지 폭 을 계속 줄 이 는 것 과 같 지 않다.
개선 방법 2: 모든 정렬 과정 에서 모든 정렬 에서 마지막 으로 교환 하 는 위 치 를 표시 위치 로 기록 합 니 다. 마지막 으로 교환 하 는 위치 가 0 이면 전체 배열 의 정렬 이 완료 되 었 음 을 설명 합 니 다.이러한 개선 사상 은 이전에 정렬 된 선험 정 보 를 사용 하여 정렬 횟수 를 줄 이 는 것 이다.
구현 코드:
#include<iostream>
using namespace std;
void BubbleSort(int a[], int n)
{
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n-i-1; j++)
{
if(a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
void BubbleSort_2(int a[], int n)
{
int low = 0;
int high = n-1;
int j;
while(low < high)
{
for(j = low; j < high; j++)
{
if(a[j] > a[j+1])
swap(a[j], a[j+1]);
}
high--;
for(j = high; j > low; j--)
{
if(a[j] < a[j-1])
swap(a[j], a[j-1]);
}
low++;
}
}
void BubbleSort_3(int a[], int n)
{
int i = n-1; //
while(i > 0) // 0
{
int pos = 0;
for(int j = 0; j < i; j++) //
{
if(a[j] > a[j+1])
{
pos = j;
swap(a[j], a[j+1]);
}
}
i = pos;
}
}
int main()
{
int a[] = {1, 4, 8, 6, 2, 7};
BubbleSort_3(a, 6);
for(int i = 0; i< 6; i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
