import java.util.Random;
/**
* 정렬 테스트 클래스
*
* 정렬 알고리즘의 분류는 다음과 같습니다. 1. 삽입 정렬(직접 삽입 정렬, 절반 삽입 정렬, 힐 정렬) 2. 교환 정렬(버블 정렬, 퀵 정렬)
* 3. 선택 정렬(직접 선택 정렬, 힙 정렬) 4. 병합 정렬 5. 기수 정렬.
*
* 정렬 방법 선택에 관하여: (1) n이 작은 경우(예: n≤50) 직접 삽입 또는 직접 선택 정렬을 사용할 수 있습니다.
* 레코드 크기가 작을 경우 직접 삽입 정렬이 더 좋고, 직접 삽입에 비해 이동된 레코드 수가 적기 때문에 직접 선택 정렬이 더 좋습니다.
* (2) 파일의 초기 상태가 기본적으로 순서(양의 순서를 나타냄)인 경우 직접 삽입, 버블 또는 임의 빠른 정렬을 사용해야 합니다.
* (3) n이 큰 경우에는 시간복잡도가 O(nlgn)인 정렬 방법(퀵 정렬, 힙 정렬, 병합 정렬)을 사용해야 합니다.
*
*/
공개 클래스 정렬 {
/**
* 테스트 배열 초기화 방법
*
* @return 초기화된 배열
*/
공개 int[] createArray() {
무작위 무작위 = 새로운 무작위();
int[] 배열 = 새로운 int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // 두 개의 난수를 생성하고 이를 빼서 생성된 숫자에 음수가 있는지 확인합니다.
}
System.out.println("==========원본 시퀀스==========");
printArray(배열);
반환 배열;
}
/**
* 배열의 요소를 콘솔에 인쇄
*
* @param 소스
*/
공공 무효 printArray(int[] 데이터) {
for (int i : 데이터) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 배열에서 지정된 두 요소의 위치를 교환합니다.
*
* @param 데이터
* @param x
* @param y
*/
개인 무효 교환(int[] 데이터, int x, int y) {
int temp = 데이터[x];
데이터[x] = 데이터[y];
데이터[y] = 온도;
}
/**
* 버블정렬----교환정렬의 일종
* 방법: 두 개의 인접한 요소를 비교하고 필요한 경우 교환합니다. 각 주기가 완료된 후 가장 큰 요소가 마지막으로 순위가 매겨집니다(예: 작은 것에서 큰 것으로 정렬).
* 성능: 비교 횟수 O(n^2),n^2/2, 교환 횟수 O(n^2),n^2/4
*
* @param 데이터
* 정렬할 배열
* @param sortType
* 정렬 유형
* @반품
*/
공공 무효 bubbleSort(int[] 데이터, 문자열 sortType) {
if (sortType.equals("asc")) { // 작은 것에서 큰 것 순으로 긍정적인 정렬
// 비교 라운드 수
for (int i = 1; i < data.length; i++) {
// 인접한 두 숫자를 비교하면 더 큰 숫자가 나타납니다.
for (int j = 0; j < data.length - i; j++) {
if (데이터[j] > 데이터[j + 1]) {
// 인접한 두 숫자를 바꿉니다.
swap(데이터, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // 큰 것부터 작은 것 순으로 역순으로 정렬합니다.
// 비교 라운드 수
for (int i = 1; i < data.length; i++) {
// 인접한 두 숫자를 비교하면 더 큰 숫자가 나타납니다.
for (int j = 0; j < data.length - i; j++) {
if (데이터[j] < 데이터[j + 1]) {
// 인접한 두 숫자를 바꿉니다.
swap(데이터, j, j + 1);
}
}
}
} 또 다른 {
System.out.println("입력한 정렬 유형이 잘못되었습니다!");
}
printArray(data);//버블정렬 후 배열값 출력
}
/**
* 직접 선택 정렬 방법----선택 정렬의 일종
* 방법: 각 패스에서 정렬할 데이터 요소 중 가장 작은(또는 가장 큰) 요소를 선택하고, 정렬할 모든 데이터 요소가 정렬될 때까지 정렬된 배열의 끝에 순서를 둡니다.
* 성능: 비교 횟수 O(n^2),n^2/2
* 교환수 O(n),n
* 교환 횟수는 버블 정렬보다 훨씬 적습니다. 교환은 비교보다 CPU 시간이 더 많이 필요하므로 선택 정렬이 버블 정렬보다 빠릅니다.
* 다만 N이 상대적으로 클 경우에는 비교에 필요한 CPU 시간이 지배적이므로 이때의 성능은 버블정렬과 크게 다르지는 않지만 확실히 속도가 빨라진다.
*
* @param 데이터
* 정렬할 배열
* @param sortType
* 정렬 유형
* @반품
*
*/
공공 무효 selectSort(int[] 데이터, 문자열 sortType) {
if (sortType.equals("asc")) { // 작은 것에서 큰 것 순으로 긍정적인 정렬
정수 인덱스;
for (int i = 1; i < data.length; i++) {
인덱스 = 0;
for (int j = 1; j <= data.length - i; j++) {
if (데이터[j] > 데이터[인덱스]) {
인덱스 = j;
}
}
//data.length-i 위치의 두 숫자와 인덱스(최대값)를 교환합니다.
swap(data, data.length - i, 인덱스);
}
} else if (sortType.equals("desc")) { // 큰 것부터 작은 것 순으로 역순으로 정렬합니다.
정수 인덱스;
for (int i = 1; i < data.length; i++) {
인덱스 = 0;
for (int j = 1; j <= data.length - i; j++) {
if (데이터[j] < 데이터[인덱스]) {
인덱스 = j;
}
}
//data.length-i 위치의 두 숫자와 인덱스(최대값)를 교환합니다.
swap(data, data.length - i, 인덱스);
}
} 또 다른 {
System.out.println("입력한 정렬 유형이 잘못되었습니다!");
}
printArray(data);//직접 선택 정렬 후 배열값 출력
}
/**
*
* 삽입 정렬
*
* 방법: 정렬된 순서 목록(빈 목록일 수도 있음)에 레코드를 삽입하여 레코드 수가 1 증가한 새로운 순서 목록을 얻습니다.
* 성능: 비교 횟수 O(n^2),n^2/4
* 복사 매수 O(n),n^2/4
* 비교 횟수는 처음 2개 사이의 평균이며, 복사하는 것이 교환하는 것보다 CPU 시간이 덜 필요하므로 성능은 버블 정렬의 두 배 이상이고 선택 정렬보다 빠릅니다.
*
* @param 데이터
* 정렬할 배열
* @param sortType
* 정렬 유형
*/
공공 무효 insertSort(int[] 데이터, 문자열 sortType) {
if (sortType.equals("asc")) { // 작은 것에서 큰 것 순으로 긍정적인 정렬
// 비교 라운드 수
for (int i = 1; i < data.length; i++) {
// 첫 번째 i+1 숫자가 정렬되었는지 확인합니다.
for (int j = 0; j < i; j++) {
if (데이터[j] > 데이터[i]) {
// j와 i 위치의 두 숫자를 바꿉니다.
스왑(데이터, i, j);
}
}
}
} else if (sortType.equals("desc")) { // 큰 것부터 작은 것 순으로 역순으로 정렬합니다.
// 비교 라운드 수
for (int i = 1; i < data.length; i++) {
// 첫 번째 i+1 숫자가 정렬되었는지 확인합니다.
for (int j = 0; j < i; j++) {
if (데이터[j] < 데이터[i]) {
// j와 i 위치의 두 숫자를 바꿉니다.
스왑(데이터, i, j);
}
}
}
} 또 다른 {
System.out.println("입력한 정렬 유형이 잘못되었습니다!");
}
printArray(data);//삽입정렬 후 배열값 출력
}
/**
*
* 배열을 뒤집는 방법
*
* @param 데이터
* 소스 배열
*/
공개 무효 역(int[] 데이터) {
int 길이 = data.length;
int temp = 0;//임시변수
for (int i = 0; i < 길이 / 2; i++) {
온도 = 데이터[i];
데이터[i] = 데이터[길이 - 1 - i];
데이터[길이 - 1 - i] = 온도;
}
printArray(data);//변환된 배열로 값을 출력합니다.
}
/**
*
* 퀵 정렬
*
* 퀵 정렬은 분할 정복 전략을 사용하여 시퀀스(리스트)를 두 개의 하위 시퀀스(하위 목록)로 나눕니다.
*
*단계는 다음과 같습니다.
* 1. 시퀀스에서 "피벗"이라는 요소를 선택합니다.
* 2. 기본 값보다 작은 요소는 모두 기본 앞에 배치되고 기본 값보다 큰 요소는 모두 기본 뒤에 배치되도록 시퀀스를 재정렬합니다(양쪽에 동일한 번호가 배치될 수 있음). 이 분할 후에 데이텀은 최종 위치에 있게 됩니다. 이를 파티션 작업이라고 합니다.
* 3. 기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.
*
* 재귀의 가장 낮은 경우는 배열의 크기가 0 또는 1인 경우, 즉 항상 정렬되어 있었던 경우입니다. 계속 반복되지만 이 알고리즘은 항상 종료됩니다. 왜냐하면 각 반복(반복)에서 최소한 하나의 요소를 최종 위치로 이동하기 때문입니다.
*
* @param 데이터
* 정렬할 배열
* @param 낮음
* @param 하이
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
공개 무효 QuickSort(int[] 데이터, 문자열 sortType) {
if (sortType.equals("asc")) { // 작은 것에서 큰 것 순으로 긍정적인 정렬
qsort_asc(데이터, 0, data.length - 1);
} else if (sortType.equals("desc")) { // 큰 것부터 작은 것 순으로 역순으로 정렬합니다.
qsort_desc(data, 0, data.length - 1);
} 또 다른 {
System.out.println("입력한 정렬 유형이 잘못되었습니다!");
}
}
/**
*
* 빠른 정렬의 구체적인 구현, 올바른 순서로 정렬
*
* @param 데이터
* @param 낮음
* @param 하이
*/
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // 이 조건은 재귀를 종료하는 데 사용됩니다.
나는 = 낮음;
j = 높음;
x = 데이터[i];
동안 (i < j) {
while (i < j && data[j] > x) {
j--; // 오른쪽에서 왼쪽으로 x보다 작은 첫 번째 숫자를 찾습니다.
}
만약 (i < j) {
데이터[i] = 데이터[j];
나++;
}
while (i < j && 데이터[i] < x) {
i++; // 왼쪽에서 오른쪽으로 x보다 큰 첫 번째 숫자를 찾습니다.
}
만약 (i < j) {
데이터[j] = 데이터[i];
j--;
}
}
데이터[i] = x;
qsort_asc(데이터, 낮음, i - 1);
qsort_asc(데이터, i + 1, 높음);
}
}
/**
*
* 퀵 정렬의 구체적인 구현, 역순 정렬
*
* @param 데이터
* @param 낮음
* @param 하이
*
*/
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // 이 조건은 재귀를 종료하는 데 사용됩니다.
나는 = 낮음;
j = 높음;
x = 데이터[i];
동안 (i < j) {
while (i < j && 데이터[j] < x) {
j--; // 오른쪽에서 왼쪽으로 x보다 작은 첫 번째 숫자를 찾습니다.
}
만약 (i < j) {
데이터[i] = 데이터[j];
나++;
}
while (i < j && data[i] > x) {
i++; // x보다 큰 첫 번째 숫자를 왼쪽에서 오른쪽으로 찾습니다.
}
만약 (i < j) {
데이터[j] = 데이터[i];
j--;
}
}
데이터[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(데이터, i + 1, 높음);
}
}
/**
*
* 정수 배열에서 특정 정수의 위치에 대한 이진 검색(재귀)
*
* 검색 선형 목록은 순서가 지정된 목록이어야 합니다.
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int BinarySearch(int[] 데이터 세트, int 데이터, int startIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1 // mid = (low + high)와 같습니다.
// / 2, 그러나 효율성은 더 높아질 것입니다
if (데이터 < 데이터 세트[beginIndex] || 데이터 > 데이터 세트[endIndex] || BeginIndex > endIndex)
-1을 반환합니다.
if (데이터 < 데이터세트[midIndex]) {
return BinarySearch(데이터 세트, 데이터, BeginIndex, midIndex - 1);
} else if (데이터 > 데이터세트[midIndex]) {
return BinarySearch(dataset, data, midIndex + 1, endIndex);
} 또 다른 {
midIndex를 반환합니다.
}
}
/**
*
* 정수 배열에서 특정 정수 위치에 대한 이진 검색(비재귀)
*
* 검색 선형 목록은 순서가 지정된 목록이어야 합니다.
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
공개 int BinarySearch(int[] 데이터 세트, int 데이터) {
int startIndex = 0;
int endIndex = 데이터세트.길이 - 1;
int midIndex = -1;
if (데이터 < 데이터 세트[beginIndex] || 데이터 > 데이터 세트[endIndex] || BeginIndex > endIndex)
-1을 반환합니다.
while(beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1 // midIndex =와 같습니다.
// (beginIndex +
// endIndex) / 2이지만 효율성은 더 높아집니다.
if (데이터 < 데이터세트[midIndex]) {
endIndex = midIndex - 1;
} else if (데이터 > 데이터세트[midIndex]) {
BeginIndex = midIndex + 1;
} 또 다른 {
midIndex를 반환합니다.
}
}
-1을 반환합니다.
}
공개 정적 무효 메인(String[] args) {
정렬 sortTest = new Sort();
int[] 배열 = sortTest.createArray();
System.out.println("==========버블 정렬 후(양수)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========버블 정렬 후(역순)==========");
sortTest.bubbleSort(array, "desc");
배열 = sortTest.createArray();
System.out.println("==========배열을 뒤집은 후==========");
sortTest.reverse(array);
배열 = sortTest.createArray();
System.out.println("==========선택 정렬 후(양수)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========선택 정렬 후(역순)==========");
sortTest.selectSort(array, "desc");
배열 = sortTest.createArray();
System.out.println("==========삽입 정렬 후(양수 순서)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========삽입 정렬 후(역순)==========");
sortTest.insertSort(array, "desc");
배열 = sortTest.createArray();
System.out.println("==========빠른 정렬 후(양수)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========빠른 정렬 후(역순)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========배열의 이진 검색==========");
System.out.println("찾고 있는 숫자는 다음 위치에 있습니다." + sortTest.binarySearch(array, 74)
+ "좌석. (아래첨자는 0부터 계산)");
}
}