일반 Java 정렬 알고리즘 상세 정보

하나, 정렬 선택(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] + " ");
 }
 }
}

둘째, 정렬 삽입(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)의 기록을 2차 비교한다.비교한 기록이 하나만 남을 때까지 이 과정을 반복한다.

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] + " ");
 }
 }
}

넷째, 병합 정렬(MergeSort)
기본 원리: 귀속과 분치 기술을 이용하여 데이터 서열을 점점 작은 반자표로 나누고 반자표에 대해 정렬한다. 마지막으로 귀속 방법으로 정렬된 반자표를 합쳐서 점점 더 큰 질서 서열로 만든다.주어진 기록 세트(모두 n개의 기록이 있다고 가정)에 대해 먼저 두 개의 인접한 길이가 1인 하위 서열을 병합하고 n/2(상향으로 정돈)개의 길이가 2 또는 1인 질서 서열을 얻은 다음에 두 개의 서열을 병합하여 질서 서열을 얻을 때까지 이 과정을 반복한다.

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] + " ");
 }
 }
}

이상은 본문의 전체 내용입니다. 본고의 내용이 여러분의 학습이나 업무에 일정한 도움을 줄 수 있는 동시에 저희를 많이 지지해 주시기 바랍니다!