一般的に使用される Java ソート アルゴリズムの詳細な説明

1. 選択ソート (SelectSort)

基本原則: 指定されたレコードのセットについて、最初の比較の後、最小のレコードが取得され、そのレコードの位置が最初のレコードと交換されます。最初のレコード以外のレコードが含まれないレコードが再度比較され、最小のレコードが取得され、その位置が 2 番目のレコードと交換されます。このプロセスは、比較されるレコードが 1 つだけになるまで繰り返されます。

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)

基本原則: 与えられたデータセットについて、最初のレコードは順序付きシーケンスを形成し、残りのレコードは順序なしシーケンスであると想定されます。次に、2 番目のレコードから開始して、最後のレコードが順序付けされたシーケンスに挿入されるまで、レコードのサイズに応じて、現在処理されているレコードがその前の順序付けされたシーケンスに挿入されます。

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 個のレコードについて、最初のレコードから順に 2 つの隣接するレコードを比較します。 前のレコードが より大きい場合、後続のレコードについては、位置が交換されると、n 個のレコードのうち最大のレコードが n 番目の位置になり、最初の (n-1) 個のレコードに対して 2 回目の比較が実行されます。比較するレコードは 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)

基本原理: 再帰と分割統治技術を使用して、データシーケンスをますます小さい半分のサブテーブルに分割し、次に半分のサブテーブルをソートし、最後に再帰を使用する このメソッドは、ソートされたハーフサブリストを、ますます大きなソートされたシーケンスにマージします。指定されたレコードのセット (合計 n レコードと仮定) について、まず長さ 1 の隣接する 2 つのサブシーケンスをすべてマージして、長さ 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)

基本原理: 指定されたレコードのセットについて、ソートを 1 回行った後、元のシーケンスが 2 つの部分に分割され、前の部分のすべてのレコードが小さくなります。 1 つの部分のレコードはすべて小さいため、前後の 2 つの部分のレコードがすぐにソートされ、シーケンス内のすべてのレコードがソートされるまでプロセスが再帰的に行われます。

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. シェルソート

基本原理: まず、ソート対象の配列要素を複数のサブシーケンスに分割して、各サブシーケンスの要素数が相対的に減り、次に各サブシーケンスに対して個別の操作を実行します。挿入ソートでは、ソート対象のシーケンス全体が「基本的に順序付け」された後、最後にすべての要素に対して直接挿入ソートが実行されます。

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) 個の要素が小さな最上位のヒープに再調整され、次にその最上位の要素になります。現在のヒープの最後の要素と交換した後、調整されたヒープに 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 中国語 Web サイトに注目してください。