java 정렬 알고리즘 및 복잡도
3392 단어 Java 정렬
public class Bubble {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
for (int m = a.length - 1; m > 0; m--) {
for (int n = 0; n < m; n++) {
if (a[n] > a[n + 1]) {
int temp = a[n];
a[n] = a[n + 1];
a[n + 1] = temp;
}
}
}
for (int i : a) {
System.out.println(i);
}
}
}
복잡도 분석: 거품 정렬은 불안정한 정렬 알고리즘으로 모두 비교하기((n-1)+(n-2)+...+3+2+1)=n*(n-1)/2회이기 때문에 시간 복잡도는 O(n^2)입니다.
빠른 정렬:
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] initArray = { 1, 545, 23, 334, 876, 222, 111, 8, 9, 7, 6, 57, 89,
0, -23, 670 };
qsort(initArray, 0, initArray.length - 1);
outprint(initArray);
}
public static void outprint(int[] initArray) {
for (int i : initArray) {
System.out.println(i);
}
}
public static void swap(int[] array, int a, int b) {
System.out.println("a=" + a);
System.out.println("b=" + b);
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
public static int getPivotIndex(int[] array, int begin, int end) {
Random r = new Random();
return begin + r.nextInt(end - begin + 1);
}
public static void qsort(int[] array, int begin, int end) {
if (end > begin) {
int index = getPivotIndex(array, begin, end);
index = portions(array, begin, end, index);
qsort(array, begin, index - 1);
qsort(array, index + 1, end);
}
}
public static int portions(int[] array, int begin, int end, int index) {
int pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; i++) {
if (array[i] < pivot) {
swap(array, index++, i);
}
}
swap(array, index, end);
return index;
}
}
최악의 상황은 거품이 생기는 것과 마찬가지로 시간 복잡도는 O(n^2)이며, 가장 좋은 것은 n*logn이다.
삽입 정렬:
public class InsertSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] array = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
isort(array, 0, array.length);
outprint(array);
}
public static void outprint(int[] initArray) {
for (int i : initArray) {
System.out.println(i);
}
}
public static void swap(int[] array, int a, int b) {
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
public static void isort(int[] array, int begin, int end) {
for (int i = begin; i < end; i++) {
int temp = array[i];
for (int m = i - 1; m >= 0; m--) {
if (temp < array[m]) {
array[m + 1] = array[m];
array[m] = temp;
} else {
break;
}
}
}
}
}
가장 좋은 상황은 순서가 정해져 있으면 n-1회만 비교하면 된다는 것이다.최악의 경우: 순서가 딱 역순, 비교 1+2+...+n-1회.
평균 시간의 복잡도도 O(n^2)이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 정렬 알고리즘 - 정렬 선택텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.