java는 거품 정렬을 이용하여 수조를 정렬한다
1. 거품 정렬:
거품 정렬을 이용하여 수조를 정렬하다
2. 기본 개념:
차례대로 인접한 두 수를 비교하여 소수를 앞에 놓고 대수를 뒤에 놓는다.즉, 첫 번째와 두 번째 수를 비교하고 소수를 앞에 놓고 큰 수를 뒤에 놓는다.그리고 두 번째 수와 세 번째 수를 비교하고 소수를 앞에 놓고, 대수를 뒤에 놓고, 이렇게 계속한다. 마지막 두 수를 비교하고, 소수를 앞에 놓고, 대수를 뒤에 놓는다.이로써 첫 번째 끝은 가장 큰 수를 마지막에 놓았다.두 번째: 여전히 첫 번째 대수부터 비교한다(2번째 수와 세 번째 수의 교환으로 인해 첫 번째 수가 두 번째 수보다 작지 않을 수 있기 때문에), 소수를 앞에 놓고, 큰 수를 놓은 후에 두 번째 수(꼴찌의 위치에서 이미 가장 큰 것)까지 비교한다. 두 번째가 끝나면 꼴찌의 두 번째 위치에서 새로운 최대 수(사실은 전체 수열에서 두 번째로 큰 수)를 얻는다.이렇게 하면 최종적으로 정렬이 끝날 때까지 상기 과정을 반복한다.
3. 실현 사고방식:
이중 순환으로 실현하고 외순환 변수는 i로 하고 내순환 변수는 j로 한다.만약 n개수가 정렬을 해야 한다면 외순환은 n-1번, 내순환은 n-1, n-2,...한 번.매번 비교를 하는 두 요소는 모두 내순환 j와 관련이 있다. 그들은 각각 a[j]와 a[j+1] 표지를 사용할 수 있다. i의 값은 1,2,......n-1, 매 i, j의 값은 순서대로 0, 1, 2,...n-i .
세그먼트 길이는 N:
1. 서로 인접한 앞뒤 두 개의 데이터가 앞뒤 데이터보다 크면 두 개의 데이터를 교환한다.
2. 이렇게 해서 수조의 0번째 데이터를 N-1개의 데이터로 한 번 훑어본 후 가장 큰 데이터는 수조의 N-1번째 위치로 가라앉는다.
3.N=N-1, N이 0이 아니면 앞의 두 단계를 반복합니다. 그렇지 않으면 정렬이 완료됩니다.
4. 자바 코드 구현:
package ArrayDemo;
/**
* @author pplsunny
* @category .21
*/
public class ArrayDemo {
/**
* for
*/
public static void main(String[] args) {
int[] a = { 2, 4, 76, 12, 34, 23, 86 };
ArrayDemo.bubbleSort(a);
for (int b : a) {
System.out.print(b + " ");
}
}
/*
* , ,
*
*/
public static void bubbleSort(int a[]) {
for (int i = 1; i < a.length; i++) {
//
for (int j = 0; j < a.length - i; j++) {
//j < a.length - i,
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
5. 성능 분석:만약에 기록 서열의 초기 상태가'정렬'이면 거품 정렬 과정은 한 번의 정렬만 하고 정렬 과정에서 n-1번의 비교만 하고 기록을 이동하지 않는다.반대로 기록 서열의 초기 상태가'역순'이면 n(n-1)/2회 비교와 기록 이동을 해야 한다.따라서 거품 정렬의 총 시간 복잡도는 O(n*n)이다.
6. 알고리즘 최적화:
거품 정렬법의 부족 및 개선 방법:
첫째, 정렬 과정에서 마지막 정렬을 실행한 후 데이터가 모두 정렬되었지만 프로그램이 정렬을 완성했는지 판단할 수 없습니다. 이 부족함을 해결하기 위해 표지 비트 flag를 설정하고 초기 값을 0이 아닌 것으로 설정할 수 있습니다. 정렬된 표는 무질서한 표입니다. 정렬이 시작되기 전에 flag 값을 0으로 설정하고 데이터 교환을 할 때 flag를 0이 아닌 것으로 수정할 수 있습니다.새 정렬이 시작될 때 이 표지를 검사합니다. 만약 이 표지가 0이라면 이전에 교환 데이터를 하지 않았음을 나타냅니다. 정렬을 끝냅니다.그렇지 않으면 정렬하기;
/*
*
*/
public static void BubbleSort(int[] a) {
boolean flag = true;
while (flag) {
flag = false;
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - i ; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
if (!flag)
break; // ,
}
}
}
둘째, 거품 정렬에서 한 번의 스캐닝은 데이터 교환이 없을 수도 있고 한 번 또는 여러 번의 데이터 교환이 있을 수도 있다. 전통적인 거품 정렬 알고리즘과 최근 몇 년 동안 개선된 알고리즘에서 한 번의 스캐닝만 데이터 교환이 있는지 없는지를 기록하고 데이터 교환이 발생하는 위치 정보는 처리하지 않는다.이 정보를 충분히 이용하기 위해 전역 스캐닝에서 모든 반차 데이터에 대해 국부 거품 정렬 처리를 할 수 있는데 이를 국부 거품 정렬이라고 부른다.국부 거품 정렬과 거품 정렬 알고리즘은 같은 시간 복잡도를 가지고 정렬과 역순으로 필요한 키워드의 비교 횟수와 이동 횟수가 완전히 같다.국부 거품 정렬과 거품 정렬의 데이터 이동 횟수는 항상 같기 때문에 국부 거품 정렬에 필요한 키워드의 비교 횟수는 거품 정렬보다 적다. 이는 국부 거품 정렬이 평균 비교 횟수에서 거품 정렬을 개선할 가능성이 높다는 것을 의미한다. 비교 횟수가 비교적 적은 장점이 프로그램의 복잡도에 따른 추가 비용을 상쇄하기에 부족하고 데이터량이 비교적 많을 때국부 거품 정렬의 시간 성능은 거품 정렬보다 현저히 우수하다.N개의 무질서한 데이터에 대해 우리가 거품 정렬을 진행할 때 만약에 k번째 데이터와 k+1번째 데이터가 역순된다면 k+1번째 데이터에 대해 앞으로 거품 정렬을 해서 적당한 위치로 이동시킨다. 즉, 앞의 k+1개 데이터를 정렬로 조절하는 것이다.이런 거품법은 전 k+1개의 데이터에 대해서만 거품 처리를 하기 때문에 우리는 그것을 국부 거품이라고 부른다본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.