정렬 알고리즘의 자바 공략
Java 정렬은 Collections를 사용할 수 있습니다.sort () 정렬 함수 구현.
컬렉션으로.sort 방법은list 정렬에 두 가지 방법이 있습니다.
첫 번째는 list의 객체가 다음과 같은 Comparable 인터페이스를 구현하는 것입니다.
/**
* order User
*/
public class User implements Comparable<User>{
private String name;
private Integer order;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
public int compareTo(User arg0) {
return this.getOrder().compareTo(arg0.getOrder());
}
}
public class Test{
public static void main(String[] args) {
User user1 = new User();
user1.setName("a");
user1.setOrder(1);
User user2 = new User();
user2.setName("b");
user2.setOrder(2);
List<User> list = new ArrayList<User>();
// add user2 add user1
list.add(user2);
list.add(user1);
Collections.sort(list);
for(User u : list){
System.out.println(u.getName());
}
}
}
a
b
/**
* order User
*/
public class User { // Comparable
private String name;
private Integer order;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
}
public class Test{
public static void main(String[] args) {
User user1 = new User();
user1.setName("a");
user1.setOrder(1);
User user2 = new User();
user2.setName("b");
user2.setOrder(2);
List<User> list = new ArrayList<User>();
list.add(user2);
list.add(user1);
Collections.sort(list,new Comparator<User>(){
public int compare(User arg0, User arg1) {
return arg0.getOrder().compareTo(arg1.getOrder());
}
});
for(User u : list){
System.out.println(u.getName());
}
}
}
a
b
좋은 것을 골라 쓰다.
상용 정렬 알고리즘
다음은 몇 가지 고전적인 정렬 알고리즘의 Java 코드 실천을 살펴보겠습니다.
거품 정렬
public static void bubbleSort(int A[], int n) {
int i, j;
for (i = 0; i < n - 1; i ++) {
for (j = 0; j < n - i - 1; j ++) {
if (A[j] > A[j + 1]) {
A[j] = A[j] ^ A[j + 1];
A[j + 1] = A[j] ^ A[j + 1];
A[j] = A[j] ^ A[j + 1];
}
}
}
}
정렬 직접 삽입
public static void insertSort(int A[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = A[i];
for (j = i - 1; j >= 0; j--) {
if (A[j] > tmp) {
A[j + 1] = A[j];
} else {
break;
}
}
A[j + 1] = tmp;
}
}
정렬 직접 선택
public static void selectSort(int A[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (A[j] < A[loc]) {
loc = j;
}
}
if (loc != i) {
A[i] = A[i] ^ A[loc];
A[loc] = A[i] ^ A[loc];
A[i] = A[i] ^ A[loc];
}
}
}
무더기 정렬
/**
* （ ）
*
* @param A
* @param n
*/
public static void heapSort(int A[], int n) {
int tmp;
//
buildMaxHeap(A, n);
for (int j = n - 1; j >= 1; j--) {
tmp = A[0];
A[0] = A[j];
A[j] = tmp;
maxheapIfy(A, 0, j);
}
}
/**
*
*
* @param A
* @param n
*/
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, n);
}
}
/**
* i
*
* @param A
* @param i
* @param n
*/
private static void maxheapIfy(int A[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && A[left] > A[i]) {
i = left;
}
if (right < n && A[right] > A[i]) {
i = right;
}
if (loc != i) {
A[i] = A[loc] ^ A[i];
A[loc] = A[loc] ^ A[i];
A[i] = A[loc] ^ A[i];
} else {
break;
}
}
}
빠른 정렬
public static void quickSort(int A[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotPartition(A, bt, ed);
quickSort(A, bt, pivot - 1);
quickSort(A, pivot + 1, ed);
}
}
private static void swapVar(int A[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
A[bt] = A[bt] ^ A[mid];
A[mid] = A[bt] ^ A[mid];
A[bt] = A[bt] ^ A[mid];
}
}
private static int pivotPartition(int A[], int bt, int ed) {
// stand， O(n^2)
swapVar(A, bt, ed);
int stand = A[bt];
while (bt < ed) {
while (bt < ed && A[ed] >= stand) {
ed--;
}
if (bt < ed) {
A[bt++] = A[ed];
}
while (bt < ed && A[bt] <= stand) {
bt++;
}
if (bt < ed) {
A[ed--] = A[bt];
}
}
A[bt] = stand;
return bt;
}
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
테스트 프로그램
다음 알고리즘을 요약해 보겠습니다.
import java.util.Scanner;
public class JavaSort {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int A[], n;
while (cin.hasNext()) {
n = cin.nextInt();
A = new int[n];
for (int i = 0; i < n; i++) {
A[i] = cin.nextInt();
}
// bubbleSort(A, n);
// insertSort(A, n);
// selectSort(A, n);
// heapSort(A, n);
// quickSort(A, 0, n - 1);
mergeSort(A, 0, n - 1);
printArr(A);
}
}
/**
*
*
* @param A
* @param bt
* @param ed
*/
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
/**
*
*
* @param A
* @param bt
* @param mid
* @param ed
*/
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
/**
*
*
* @param A
* @param bt
* @param ed
*/
public static void quickSort(int A[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotPartition(A, bt, ed);
quickSort(A, bt, pivot - 1);
quickSort(A, pivot + 1, ed);
}
}
private static void swapVar(int A[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
A[bt] = A[bt] ^ A[mid];
A[mid] = A[bt] ^ A[mid];
A[bt] = A[bt] ^ A[mid];
}
}
/**
*
*
* @param A
* @param bt
* @param ed
* @return
*/
private static int pivotPartition(int A[], int bt, int ed) {
// stand， O(n^2)
swapVar(A, bt, ed);
int stand = A[bt];
while (bt < ed) {
while (bt < ed && A[ed] >= stand) {
ed--;
}
if (bt < ed) {
A[bt++] = A[ed];
}
while (bt < ed && A[bt] <= stand) {
bt++;
}
if (bt < ed) {
A[ed--] = A[bt];
}
}
A[bt] = stand;
return bt;
}
/**
* （ ）
*
* @param A
* @param n
*/
public static void heapSort(int A[], int n) {
int tmp;
//
buildMaxHeap(A, n);
for (int j = n - 1; j >= 1; j--) {
tmp = A[0];
A[0] = A[j];
A[j] = tmp;
maxheapIfy(A, 0, j);
}
}
/**
*
*
* @param A
* @param n
*/
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, n);
}
}
/**
* i
*
* @param A
* @param i
* @param n
*/
private static void maxheapIfy(int A[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && A[left] > A[i]) {
i = left;
}
if (right < n && A[right] > A[i]) {
i = right;
}
if (loc != i) {
A[i] = A[loc] ^ A[i];
A[loc] = A[loc] ^ A[i];
A[i] = A[loc] ^ A[i];
} else {
break;
}
}
}
/**
*
*
* @param A
* @param n
*/
public static void selectSort(int A[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (A[j] < A[loc]) {
loc = j;
}
}
if (loc != i) {
A[i] = A[i] ^ A[loc];
A[loc] = A[i] ^ A[loc];
A[i] = A[i] ^ A[loc];
}
}
}
/**
*
*
* @param A
* @param n
*/
public static void insertSort(int A[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = A[i];
for (j = i - 1; j >= 0; j--) {
if (A[j] > tmp) {
A[j + 1] = A[j];
} else {
break;
}
}
A[j + 1] = tmp;
}
}
/**
*
*
* @param A
* @param n
*/
public static void bubbleSort(int A[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (A[j] > A[j + 1]) {
A[j] = A[j] ^ A[j + 1];
A[j + 1] = A[j] ^ A[j + 1];
A[j] = A[j] ^ A[j + 1];
}
}
}
}
/**
*
*
* @param A
*/
public static void printArr(int A[]) {
for (int i = 0; i < A.length; i++) {
if (i == A.length - 1) {
System.out.printf("%d
", A[i]);
} else {
System.out.printf("%d ", A[i]);
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
