> Java > java지도 시간 > 본문

일반적으로 사용되는 Java 정렬 알고리즘에 대한 자세한 설명

高洛峰
풀어 주다: 2017-01-18 16:59:28
원래의
1918명이 탐색했습니다.

1. 선택 정렬(SelectSort)

기본 원리: 주어진 레코드 집합에 대해 첫 번째 비교 후 가장 작은 레코드를 얻은 다음 해당 레코드를 해당 레코드의 위치와 비교합니다. 첫 번째 레코드를 교환한 다음 첫 번째 레코드를 제외한 다른 레코드에 대해 두 번째 비교를 수행하여 가장 작은 레코드를 얻고 비교할 레코드가 하나만 있을 때까지 이 프로세스를 반복합니다.

public class SelectSort {
 public static void selectSort(int[] array) {
 int i;
 int j;
 int temp;
 int flag;
 for (i = 0; i < array.length; i++) {
 temp = array[i];
 flag = i;
 for (j = i + 1; j < array.length; j++) {
 if (array[j] < temp) {
  temp = array[j];
  flag = j;
 }
 }
 if (flag != i) {
 array[flag] = array[i];
 array[i] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };
 selectSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}
로그인 후 복사

2. InsertSort(InsertSort)

기본 원칙: 주어진 데이터 집합에 대해 처음에는 첫 번째 레코드가 순서가 있는 시퀀스만 있고 나머지 레코드는 순서가 없는 시퀀스입니다. 그런 다음 두 번째 레코드부터 시작하여 현재 처리 중인 레코드가 레코드 크기에 따라 순서대로 이전 레코드에 삽입되고 마지막 레코드가 정렬된 시퀀스에 삽입됩니다.

public class InsertSort {
 public static void insertSort(int[] a) {
 if (a != null) {
 for (int i = 1; i < a.length; i++) {
 int temp = a[i];
 int j = i;
 if (a[j - 1] > temp) {
  while (j >= 1 && a[j - 1] > temp) {
  a[j] = a[j - 1];
  j--;
  }
 }
 a[j] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };
 // int[] a =null;
 insertSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}
로그인 후 복사

3. 버블 정렬(BubbleSort)

기본 원리: 주어진 n 레코드에 대해 첫 번째 레코드부터 시작 인접한 두 레코드를 비교합니다. 이전 레코드가 다음 레코드보다 크면 위치를 바꿉니다. 일련의 비교 및 ​​전치 후에 n번째 레코드 중 가장 큰 레코드가 n번째 위치에 배치되고 이전(n-1) 레코드가 비교됩니다. 두 번째 비교 라운드에서는 비교할 레코드가 하나만 남을 때까지 이 과정을 반복합니다.

public class BubbleSort {
 public static void bubbleSort(int array[]) {
 int temp = 0;
 int n = array.length;
 for (int i = n - 1; i >= 0; i--) {
 for (int j = 0; j < i; j++) {
 if (array[j] > array[j + 1]) {
  temp = array[j];
  array[j] = array[j + 1];
  array[j + 1] = temp;
 }
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 45, 1, 21, 17, 69, 99, 32 };
 bubbleSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}
로그인 후 복사

4. MergeSort(MergeSort)

기본 원리: 재귀 및 분할 정복 기술을 사용하여 데이터 시퀀스를 더 작은 크기로 나눕니다. 더 작은 것들은 반 하위 테이블을 만들고, 반 하위 테이블을 정렬하고, 마지막으로 재귀적 방법을 사용하여 정렬된 반 하위 테이블을 점점 더 큰 순서의 순서로 병합합니다. 주어진 레코드 집합(총 n개 레코드로 가정)에 대해 먼저 길이가 1인 두 개의 인접한 하위 시퀀스를 모두 병합하여 길이가 2 또는 1인 n/2(반올림) 순서의 하위 시퀀스를 얻습니다. 하위 시퀀스를 2개씩 병합합니다. , 그리고 정렬된 순서가 얻어질 때까지 이 과정을 반복합니다.

public class MergeSort {
 public static void merge(int array[], int p, int q, int r) {
 int i, j, k, n1, n2;
 n1 = q - p + 1;
 n2 = r - q;
 int[] L = new int[n1];
 int[] R = new int[n2];
 for (i = 0, k = p; i < n1; i++, k++)
 L[i] = array[k];
 for (i = 0, k = q + 1; i < n2; i++, k++)
 R[i] = array[k];
 for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
 if (L[i] > R[j]) {
 array[k] = L[i];
 i++;
 } else {
 array[k] = R[j];
 j++;
 }
 }
 if (i < n1) {
 for (j = i; j < n1; j++, k++)
 array[k] = L[j];
 }
 if (j < n2) {
 for (i = j; i < n2; i++, k++) {
 array[k] = R[i];
 }
 }
 }
 public static void mergeSort(int array[], int p, int r) {
 if (p < r) {
 int q = (p + r) / 2;
 mergeSort(array, p, q);
 mergeSort(array, q + 1, r);
 merge(array, p, q, r);
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 mergeSort(a, 0, a.length - 1);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}
로그인 후 복사

5. 빠른 정렬(QuickSort)

기본 원칙: 주어진 레코드 집합에 대해 한 번의 정렬 과정을 거친 후 원본 시퀀스는 두 부분으로 나뉘는데, 앞 부분의 모든 레코드가 뒷 부분의 모든 레코드보다 작습니다. 그런 다음 두 부분의 레코드가 차례로 빠르게 정렬되고 프로세스는 순서가 맞습니다.

public class QuickSort {
 public static void sort(int array[], int low, int high) {
 int i, j;
 int index;
 if (low >= high)
 return;
 i = low;
 j = high;
 index = array[i];
 while (i < j) {
 while (i < j && index <= array[j])
 j--;
 if (i < j)
 array[i++] = array[j];
 while (i < j && index > array[i])
 i++;
 if (i < j)
 array[j--] = array[i];
 }
 array[i] = index;
 sort(array, low, i - 1);
 sort(array, i + 1, high);
 }
 public static void quickSort(int array[]) {
 sort(array, 0, array.length - 1);
 }
 public static void main(String[] args) {
 int a[] = { 5, 8, 4, 6, 7, 1, 3, 9, 2 };
 quickSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}
로그인 후 복사

6. 쉘 정렬(ShellSort)

기본 원리: 먼저 정렬할 배열 요소를 여러 하위 시퀀스로 나눕니다. 하위 시퀀스의 요소 수를 상대적으로 줄여 각 하위 시퀀스에 대해 직접 삽입 정렬을 수행한 후 정렬할 전체 시퀀스를 "기본적으로" 정렬한 후 최종적으로 모든 요소에 직접 삽입 정렬을 수행합니다.

public class ShellSort {
 public static void shellSort(int[] a) {
 int len = a.length;
 int i, j;
 int h;
 int temp;
 for (h = len / 2; h > 0; h = h / 2) {
 for (i = h; i < len; i++) {
 temp = a[i];
 for (j = i - h; j >= 0; j -= h) {
  if (temp < a[j]) {
  a[j + h] = a[j];
  } else
  break;
 }
 a[j + h] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 shellSort(a);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}
로그인 후 복사

7. 최소 힙 정렬(MinHeapSort)

기본 원칙: 주어진 n개의 레코드에 대해 처음에는 이러한 레코드를 순차적으로 확인합니다. 저장된 이진 트리를 작은 최상위 힙으로 조정한 다음 힙의 마지막 요소를 힙의 최상위 요소와 교환합니다. 그런 다음 (n-1) 요소가 다시 사용됩니다. - 작은 최상위 힙으로 조정된 다음 힙의 최상위 요소가 현재 힙의 마지막 요소와 교환되어 다음으로 가장 작은 레코드를 얻습니다. 조정된 힙에 요소가 하나만 남을 때까지 이 프로세스를 반복합니다. 는 최대 기록이며, 이 시점에서 순서가 지정된 시퀀스를 얻을 수 있습니다.

public class MinHeapSort {
 public static void adjustMinHeap(int[] a, int pos, int len) {
 int temp;
 int child;
 for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
 child = 2 * pos + 1;
 if (child < len && a[child] > a[child + 1])
 child++;
 if (a[child] < temp)
 a[pos] = a[child];
 else
 break;
 }
 a[pos] = temp;
 }
 public static void myMinHeapSort(int[] array) {
 int i;
 int len = array.length;
 for (i = len / 2 - 1; i >= 0; i--) {
 adjustMinHeap(array, i, len - 1);
 }
 for (i = len - 1; i >= 0; i--) {
 int tmp = array[0];
 array[0] = array[i];
 array[i] = tmp;
 adjustMinHeap(array, 0, i - 1);
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 myMinHeapSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}
로그인 후 복사

위 글의 내용은 모두의 공부나 업무에 조금이라도 도움이 되었으면 좋겠습니다. PHP 중국어를 지원합니다!

일반적으로 사용되는 Java 정렬 알고리즘 및 관련 기사에 대한 자세한 설명은 PHP 중국어 웹사이트를 참고하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿