불안정한 정렬
선택 정렬:
1차 비교 후 얻은 가장 작은 레코드를 첫 번째 레코드의 위치로 바꾼 후, 첫 번째 레코드를 제외한 레코드에 대해 2차 비교를 수행하고 그 결과 가장 작은 레코드가 두 번째 레코드와 교환됩니다.
시간 복잡도: O(n^2)
공간 복잡도: O(1)
public static void selectSort(int[] arr){
if (arr == null || arr.length == 0)
return;
int len = arr.length;
for (int i = 0; i < len; i++) {
int min = arr[i];
int index = i;
for (int j = i+1; j < len; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
arr[index] = arr[i];
arr[i] = min;
}
}빠른 정렬:
주어진 레코드 세트에 대해 각 정렬 단계 후에는 시퀀스가 두 부분으로 나누어져 전자 부분의 모든 레코드가 후자 부분의 모든 레코드보다 작으며 그 전후 두 부분의 레코드가 빠르게 정렬됩니다.
시간 복잡도: O(nlogn ) 최악의 경우: O(n^2 )
공간 복잡도: O(nlogn)
public int Partition(int[] a,int start,int end){ int std = a[start];
while (start < end){
while(start < end && a[end] >= std)
end--;
a[start] = a[end];
while(start < end && a[start] <= std)
start++;
a[end] = a[start];
}
a[start] = std;
return start;
}
public void quickSort(int[] a,int start,int end){
if(start >= end){
return;
}
int index = Partition(a,start,end);
quickSort(a,start,index-1);
quickSort(a,index+1,end);
}힙 정렬: 완전한 이진 트리
이진 트리를 큰 최상위 힙으로 조정한 다음 힙의 마지막 요소를 최상위 힙과 교환 힙의 요소(즉, 이진 트리의 루트 노드), 힙의 마지막 요소가 가장 큰 레코드이고 첫 번째 n-1 요소가 가장 큰 최상위 힙으로 조정되고 그 다음에는 힙의 최상위 요소가 조정됩니다. 힙은 현재 힙의 마지막 요소와 교환되어 두 번째로 큰 레코드를 얻습니다. 조정될 때까지 이 과정을 반복합니다. 힙에 요소가 하나만 남을 때까지 해당 요소는 최소 레코드가 될 수 있습니다.
시간 복잡도: O(nlogn)
공간 복잡도: O(1)
public void HeapSort(int[] a){
for (int i = a.length/2 - 1; i >= 0 ; i--) {
HeapAdjust(a,i,a.length-1);
}
for (int i = a.length - 1; i >= 0; i--) {
swap(a,0,i);
HeapAdjust(a,0,i-1);
}
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public void HeapAdjust(int[] arr,int s,int len){
int tmp = arr[s];
for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {
if (i < len && arr[i] < arr[i+1]){
i++;
}
if (tmp > arr[i])
break;
arr[s] = arr[i];
s = i; //s记录被替换的子结点的索引
}
arr[s] = tmp;
}직접 삽입 정렬:
첫 번째 레코드는 자체적으로 순서가 지정된 시퀀스로 간주될 수 있으며 나머지 레코드는 호출됩니다. 순서가 없는 시퀀스. 그런 다음 두 번째 레코드부터 시작하여 현재 처리 중인 레코드를 이전 정렬된 시퀀스에 레코드 크기에 따라 순서대로 삽입하고 마지막 레코드가 정렬된 시퀀스에 삽입될 때까지
시간 복잡도: O(n^2)
공간 복잡도 : O(1)
public static void insertSort(int[] arr){
if (arr == null || arr.length == 0)
return;
int len = arr.length;
for (int i = 1; i < len; i++) {
int curr = arr[i];
int j = i;
if (arr[j-1] > curr){
while (j > 0 && arr[j-1]> curr){
arr[j] = arr[j-1];
j--;
}
}
arr[j] = curr;
}
}버블 정렬:
첫 번째 레코드부터 시작하여 인접한 두 레코드를 순서대로 비교합니다. 이전 레코드가 다음 레코드보다 크면 위치가 바뀌며 비교 및 전치 후에 n개 레코드 중 가장 큰 레코드가 위치하게 됩니다. n번째 레코드 비트를 생성한 다음 이전 n-1 레코드에 대해 두 번째 비교를 수행하고 비교할 레코드가 하나만 남을 때까지 프로세스를 반복합니다
시간 복잡도: O(n^2)
공간 복잡도: O(1)
public void bubbleSort(int[] arr){
boolean flag = true;
for (int i = 0; i < arr.length && flag; i++) {
flag = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j+1]){
flag = true;
swap(arr,j,j+1);
}
}
}
}
private void swap(int[] arr, int j, int i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}병합 정렬: 재귀: 재귀, 합집합: 개별 데이터의 순서대로 병합
길이가 1인 인접한 두 하위 시퀀스를 모두 병합하여 길이가 2 또는 1인 n/2개의 정렬된 하위 시퀀스를 얻은 다음 두 개를 병합하고 정렬된 시퀀스를 얻을 때까지 이 프로세스를 반복합니다.
시간 복잡도: O(nlogn)
공간 복잡도: O(n)
public static void mergeSort(int[] arr,int begin,int end){
int mid = (begin+end)/2;
if (begin < end){
mergeSort(arr,begin,mid);
mergeSort(arr,mid+1,end);
Merge(arr,begin,end,mid);
}
}
public static void Merge(int[] arr,int begin,int end,int mid){
int[] temp = new int[end-begin+1];
int i = begin;
int j = mid+1;
int k=0;
while (i <= mid && j <= end){
if (arr[i] < arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= end){
temp[k++] = arr[j++];
}
for (int m = 0;m < temp.length;m++){
arr[m+begin] = temp[m];
}
}위 내용은 Java를 사용하여 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
