Java 정렬 알고리즘 요약 거품 정렬
선언: 거품 정렬(Bubble Sort)은 서로 인접한 두 개의 수를 순서대로 앞에 놓고 큰 수를 뒤에 놓는다.
다음은 거품이 자바에 정렬된 알고리즘의 실현을 살펴본다.
거품 정렬은 컴퓨터의 일종의 정렬 방법으로 시간 복잡도는 O(n^2)이다. 비록 무더기 정렬, 빠른 정렬의 O(nlogn, 밑수 2)에는 미치지 못하지만 두 가지 장점이 있다.
1.'프로그래밍 복잡도'가 낮아 코드를 쓰기 쉽다.
2. 안정성을 가진다. 이곳의 안정성은 원래 서열에서 같은 원소의 상대적인 순서가 정렬 후의 서열로 유지되고 무더기 정렬, 빠른 정렬은 모두 안정성을 가지지 않는다는 것을 말한다.
그러나 1차원, 2차원 병합 정렬, 불균형 2차원 트리 정렬의 속도는 거품 정렬보다 빠르고 안정성을 가지지만 속도가 무더기 정렬에 미치지 못한다.
빠른 정렬.거품 정렬은 n-1번 서브 정렬을 거쳐 완성된 것으로 i번 서브 정렬은 첫 번째 수에서 n-i 개 수로, 만약에 i번 서브 정렬이 다음 수보다 크면
(오름차순, 작은 내림차순) 은 두 수를 교환한다.
거품 정렬 알고리즘이 안정적이고 O(1)의 추가 공간, 비교와 교환의 시간 복잡도는 모두 O(n^2)이다. 스스로 적응하고 이미 기본 정렬된 알고리즘에 대해 시간 복잡도는 O(n)이다.거품 알고리즘의 많은 성질은 삽입 알고리즘과 비슷하지만 시스템에 대한 비용은 조금 높다.
정렬 프로세스
정렬된 그룹 R을 상상합니다 [1...N]수직으로 세워 각 데이터 요소를 무게가 있는 기포로 간주하고 가벼운 기포가 중기포 아래에 있을 수 없다는 원칙에 따라 아래에서 위로 수조 R를 스캐닝한다. 본 원칙에 위반되는 경기포를 스캐닝하면 위로'떠다니게 한다. 이렇게 반복적으로 진행한다. 마지막에 어떤 두 기포가 모두 가벼운 사람이 위에 있고 무거운 사람이 아래에 있을 때까지.
코드 구현:
//
public class BubbleSort{
public static void sort(Comparable[] data){
//
int len = data.length;
for (int i = 0; i < len - 1; i++){
//
Comparable temp = null;
// ,false
boolean isExchanged = false;
for (int j = len - 1; j > i; j--){
// data[j] data[j - 1],
if (data[j].compareTo(data[j - 1]) < 0){
temp = data[j];
data[j] = data[j - 1];
data[j - 1] = temp;
// ,
isExchanged = true;
}// end if
}// end for
// , ,
if (!isExchanged){
return;
}// end if
}// end for
}// end sort
public static void main(String[] args){
// JDK1.5 ,
// int,double Comparable
Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
sort(c);
for (Comparable data : c){
System.out.println(data);
}
}
}
거품 정렬법으로 n개의 데이터를 정렬하려면 모두 n-1번의 비교가 필요하다.원래 순서가 있는 데이터라면 n-1회 비교도 필요하다.거품 정렬법의 알고리즘은 매우 간단하고 효율도 비교적 떨어진다.본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.