java.util.Randomをインポートします。
/**
* テストクラスのソート
*
※ソートアルゴリズムの分類は以下の通りです。 1. 挿入ソート（直接挿入ソート、半挿入ソート、ヒルソート） 2. 交換ソート（バブルソート、クイックソート）
* 3. 選択ソート (直接選択ソート、ヒープ ソート)。 5. 基数ソート。
*
※ソート方法の選択について： (1) nが小さい場合（n≦50など）、直接挿入ソートまたは直接選択ソートが使用できます。
* レコード サイズが小さい場合は、直接挿入ソートの方が適しています。そうでない場合は、直接選択の方が移動するレコード数が直接挿入よりも少ないため、直接選択ソートの方が適しています。
* (2) ファイルの初期状態が基本的に正しい場合 (正の順序を参照)、直接挿入、バブル、またはランダムなクイック ソートを使用する必要があります。
* (3) n が大きい場合、時間計算量が O(nlgn) のソート方法 (クイック ソート、ヒープ ソート、またはマージ ソート) を使用する必要があります。
*
*/
パブリック クラス ソート {
/**
* テスト配列を初期化するメソッド
*
* @return 初期化された配列
*/
public int[] createArray() {
ランダム ランダム = new Random();
int[] 配列 = 新しい int[10];
for (int i = 0; i < 10; i++) {
array[i] =random.nextInt(100) -random.nextInt(100); // 2 つの乱数を生成し、それらを減算して、生成された数値に負の数値が含まれていることを確認します。
}
System.out.println("==========元のシーケンス============);
printArray(配列);
配列を返します。
}
/**
* 配列内の要素をコンソールに出力します
*
* @paramソース
*/
public void printArray(int[] data) {
for (int i : データ) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 配列内の指定された 2 つの要素の位置を交換します。
*
* @paramデータ
* @paramx
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = データ[x];
データ[x] = データ[y];
データ[y] = 温度;
}
/**
※バブルソート・・・交換ソートの一種
* 方法: 2 つの隣接する要素を比較し、必要に応じて交換します。各サイクルが完了すると、最大の要素が最後にランク付けされます (小さい値から大きい値への並べ替えなど)。次のサイクルでは、他の数値に対して同様の操作が実行されます。
* パフォーマンス: 比較数 O(n^2),n^2/2、交換数 O(n^2),n^2/4
*
* @paramデータ
* ソート対象の配列
* @param ソートタイプ
※仕分けタイプ
* @戻る
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 小さいものから大きいものへの正の並べ替え
// 比較のラウンド数
for (int i = 1; i < data.length; i++) {
// 隣接する 2 つの数字を比較すると、大きい方が泡立ちます。
for (int j = 0; j < data.length - i; j++) {
if (データ[j] > データ[j + 1]) {
// 隣接する 2 つの数字を入れ替えます
スワップ(データ, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // 逆順に大きいものから小さいものへ並べ替えます
// 比較のラウンド数
for (int i = 1; i < data.length; i++) {
// 隣接する 2 つの数字を比較すると、大きい方が泡立ちます。
for (int j = 0; j < data.length - i; j++) {
if (データ[j] < データ[j + 1]) {
// 隣接する 2 つの数字を入れ替えます
スワップ(データ, j, j + 1);
}
}
}
} それ以外 {
System.out.println("入力した並べ替えの種類が間違っています!");
}
printArray(data);//バブルソート後の配列値を出力
}
/**
※直接選択ソート法・・・選択ソートの一種
* 方法: 各パスで、ソート対象のデータ要素から最小 (または最大) の要素が選択され、ソート対象のデータ要素がすべて配置されるまで、ソートされた配列の末尾に順序が配置されます。
※性能：比較回数 O(n^2),n^2/2
* 交換回数 O(n),n
※交換回数はバブルソートに比べて大幅に少なくなります。交換に必要なCPU時間が多いため、選択ソートはバブルソートよりも高速です。
※ただし、Nが比較的大きい場合は比較に必要なCPU時間が支配的になるため、このときの性能はバブルソートと大差ありませんが、速いのは間違いありません。
*
* @paramデータ
* ソート対象の配列
* @param ソートタイプ
※仕分けタイプ
* @戻る
*
*/
public void selectSort(int[] data, String 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 とインデックス (最大値) の 2 つの数値を交換します。
swap(データ, 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 とインデックス (最大値) の 2 つの数値を交換します。
swap(データ, data.length - i, インデックス);
}
} それ以外 {
System.out.println("入力した並べ替えの種類が間違っています!");
}
printArray(data);//直接選択ソート後の配列値を出力
}
/**
*
* 挿入ソート
*
* 方法: ソートされた順序付きリスト (おそらく空のリスト) にレコードを挿入し、レコード数が 1 増加した新しい順序付きリストを取得します。
※性能：比較回数 O(n^2),n^2/4
* コピー数 O(n),n^2/4
* 比較の数は最初の 2 つの比較の平均であり、コピーの方がスワップよりも CPU 時間が少ないため、パフォーマンスはバブル ソートの 2 倍以上で、選択ソートよりも高速です。
*
* @paramデータ
* ソート対象の配列
* @param ソートタイプ
※仕分けタイプ
*/
public void insertSort(int[] data, String 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 の 2 つの数値を交換します
スワップ(データ、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 の 2 つの数値を交換します
スワップ(データ、i、j);
}
}
}
} それ以外 {
System.out.println("入力した並べ替えの種類が間違っています!");
}
printArray(data);//挿入ソート後の配列値を出力
}
/**
*
* 配列を反転するメソッド
*
* @paramデータ
* ソース配列
*/
public void reverse(int[] data) {
int の長さ = データ.長さ;
int temp = 0;//一時変数
for (int i = 0; i < 長さ / 2; i++) {
一時 = データ[i];
データ[i] = データ[長さ - 1 - i];
データ[長さ - 1 - i] = 温度;
}
printArray(data);//変換された配列に値を出力します
}
/**
*
* クイックソート
*
* クイック ソートでは、分割統治戦略を使用して、シーケンス (リスト) を 2 つのサブシーケンス (サブリスト) に分割します。
*
*手順は次のとおりです。
* 1. シーケンスから「ピボット」と呼ばれる要素を選択します。
* 2. 基底値より小さいすべての要素が基底の前に配置され、基底値より大きいすべての要素が基底の後ろに配置されるようにシーケンスを並べ替えます (同じ番号をどちらの側に配置することもできます)。この分割後、データムは最終位置に配置されます。これをパーティション操作と呼びます。
* 3. 基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。
*
* 再帰の最も低いケースは、配列のサイズが 0 または 1 の場合、つまり配列が常にソートされている場合です。再帰を続けますが、各反復 (反復) で少なくとも 1 つの要素が最終位置に移動するため、このアルゴリズムは必ず終了します。
*
* @paramデータ
* ソート対象の配列
* @param low
* @param high
* @参照 SortTest#qsort(int[], int, int)
* @参照 SortTest#qsort_desc(int[], int, int)
*
*/
public void QuickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 小さいものから大きいものへの正の並べ替え
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // 逆順に大きいものから小さいものへ並べ替えます
qsort_desc(data, 0, data.length - 1);
} それ以外 {
System.out.println("入力した並べ替えの種類が間違っています!");
}
}
/**
*
* クイックソート、正しい順序でのソートの具体的な実装
*
* @paramデータ
* @param low
* @param high
*/
private void qsort_asc(int data[], int low, int high) {
int i、j、x;
if (low < high) { // この条件は再帰を終了するために使用されます
i = 低い;
j = 高;
x = データ[i];
while (i < j) {
while (i < j && データ[j] > x) {
j--; // x より小さい最初の数値を右から左に探します。
}
if (i < j) {
データ[i] = データ[j];
i++;
}
while (i < j && データ[i] < x) {
i++; // x より大きい最初の数値を左から右に探します。
}
if (i < j) {
データ[j] = データ[i];
j--;
}
}
データ[i] = x;
qsort_asc(データ、低、i - 1);
qsort_asc(データ、i + 1、高);
}
}
/**
*
* クイックソート、逆順ソートの具体的な実装
*
* @paramデータ
* @param low
* @param high
*
*/
private void qsort_desc(int data[], int low, int high) {
int i、j、x;
if (low < high) { // この条件は再帰を終了するために使用されます
i = 低い;
j = 高;
x = データ[i];
while (i < j) {
while (i < j && データ[j] < x) {
j--; // x より小さい最初の数値を右から左に探します。
}
if (i < j) {
データ[i] = データ[j];
i++;
}
while (i < j && データ[i] > x) {
i++; // x より大きい最初の数値を左から右に探します。
}
if (i < j) {
データ[j] = データ[i];
j--;
}
}
データ[i] = x;
qsort_desc(データ、低、i - 1);
qsort_desc(データ、i + 1、高);
}
}
/**
*
* 整数配列内の特定の整数の位置を二分探索します (再帰的)
*
* 検索線形リストは順序付きリストである必要があります
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int binarySearch(int[] データセット, int データ, int beginIndex,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(データセット、データ、midIndex + 1、endIndex);
} それ以外 {
MidIndex を返します。
}
}
/**
*
* 整数配列内の特定の整数の位置を二分探索します (非再帰的)
*
* 検索線形リストは順序付きリストである必要があります
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public int binarySearch(int[] データセット, int データ) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (データ < データセット[beginIndex] || データ > データセット[endIndex] || beginIndex > endIndex)
-1 を返します。
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> // MidIndex = と同等;
// (beginIndex +
// endIndex) / 2 ただし、効率は高くなります
if (データ < データセット[midIndex]) {
endIndex = MidIndex - 1;
else if (データ > データセット[midIndex]) {
beginIndex = MidIndex + 1;
} それ以外 {
MidIndex を返します。
}
}
-1 を返します。
}
public static void main(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(配列);
System.out.println("==========クイックソート後(逆順)=============);
sortTest.quickSort(array, "desc");
sortTest.printArray(配列);
System.out.println("==========配列内の二分探索============);
System.out.println("探している番号は次のとおりです" + sortTest.binarySearch(array, 74)
+ "座席数。(添え字は 0 から計算されます)");
}
}