데이터 구조 (2) 거품 정렬 과 간단 한 선택 정렬
4. 567917. 메 인 프로그램 을 먼저 던 집 니 다. 4. 567918.
package Sort;
public class BubbleSort {
public static void main(String[] args) {
int [] a = {2,5,6,7,1,8,9};
BubbleSort3( a, 6);
for(int k = 0; k <= 6; k++){
System.out.println(a[k]);
}
}
static void BubbleSort3(int [] a, int n){
int i = 0;
int j = 0;
boolean flag = true;
for (i=0; i<=n && flag==true; i++){
flag = false;
for (j=n; j>=(i+1); j--){
if (a[j] < a[j-1]){
swap(a, j, i);
flag = true;
}
}
}
}
static void BubbleSort2(int [] a, int n){
int i = 0;
int j = 0;
for (i=0; i<=n; i++){
for (j=n; j>=(i+1); j--){
if (a[j] < a[j-1]){
swap(a, j, i);
}
}
}
}
static void BubbleSort1(int [] a, int n){
int i = 0;
int j = 0;
for (i=0; i<=n; i++){
for (j=i+1;j<=n; j++){
if (a[j] < a[i]){
swap(a, j, i);
}
}
}
}
static void swap(int [] num,int j, int i){
int temp;
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
거품 정렬 초급 버 전
static void BubbleSort1(int [] a, int n){
int i = 0;
int j = 0;
for (i=0; i<=n; i++){
for (j=i+1;j<=n; j++){
if (a[j] < a[i]){
swap(a, j, i);
}
}
}
}
엄격 한 의미 에서 볼 때 이것 은 순서 표를 교환 정렬 하 는 것 일 뿐 시간 복잡 도 는 O (N2) 로 분석 된다.또한 swap 작업 은 만족 후 값 이 현재 값 보다 작은 상황 에서 진행 되 기 때문에 후속 값 의 가장 작은 값 과 교환 하 는 것 이 아니 라 불필요 한 작업 이 많이 증가 합 니 다.
static void BubbleSort2(int [] a, int n){
int i = 0;
int j = 0;
for (i=0; i<=n; i++){
for (j=n; j>=(i+1); j--){
if (a[j] < a[j-1]){
swap(a, j, i);
}
}
}
}
이 버 전과 이전 버 전의 차 이 는 내부 순환 이 j = n 에서 시작 되면 효 과 는 바로 인접 비교, 작은 상승 이다. 이것 이 바로 거품 정렬 의 명명 유래 이다.이 알고리즘 은 매번 외부 순환 에서 작은 값 을 순서 표 앞으로 이동 합 니 다.하지만 우리 시 계 는 이미 순서 가 있 을 때, 단지 몇 분 의 다른 상황 일 까?우 리 는 최적화 조 치 를 가지 고 있다.
거품 정렬 정식 최적화 판
static void BubbleSort3(int [] a, int n){
int i = 0;
int j = 0;
boolean flag = true;
for (i=0; i<=n && flag==true; i++){
flag = false;
for (j=n; j>=(i+1); j--){
if (a[j] < a[j-1]){
swap(a, j, i);
flag = true;
}
}
}
}
우리 가 플래그 비트 flag 를 추가 한 것 을 볼 수 있 습 니 다. 그러나 지난번 순환 이 순 서 를 바 꾸 지 않 았 을 때 표 가 질서 가 있 으 면 계속 순환 하지 않 는 다 는 것 을 설명 합 니 다.거품 정렬 의 시간 복잡 도 는 O (N2) 이다.
2. 간단하게 정렬 선택
4. 567917. 메 인 프로그램 을 먼저 던 집 니 다. 4. 567918.
package Sort;
public class SimpleSelectSort {
public static void main(String[] args) {
int [] a = {8,4,5,2,1,7};
SimpleSelectSort1(a, 5);
for(int k = 0; k <= 5; k++){
System.out.println(a[k]);
}
}
static void SimpleSelectSort1(int [] a, int length){
int i,j,min;
for ( i=0; i<=length; i++) {
min = i;
for ( j=i+1; j<=length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if(i != min)
swap(a, i, min);
}
}
static void swap(int [] num,int j, int i){
int temp;
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
간단 한 선택 정렬 분석
간단 한 정렬 의 원 리 는 n - i 차 키워드 간 의 비 교 를 통 해 n - i + 1 개 기록 에서 키워드 의 가장 작은 기록 을 선택 하여 i 차 기록 과 교환 하 는 것 이다.
static void SimpleSelectSort1(int [] a, int length){
int i,j,min;
for ( i=0; i<=length; i++) {
min = i;
for ( j=i+1; j<=length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if(i != min)
swap(a, i, min);
}
}
단순 정렬 의 시간 복잡 도도 O (N2) 다.이들 의 시간 복잡 도 는 O (N) 이기 때문이다.앞으로 수필 에 소개 하 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
