Javaでのソートアルゴリズムの直接挿入ソート、バブルソート、簡単な選択ソート、高速ソート
4121 ワード
シーン:配列を入力し、配列をソートします.
(一)直接挿入ソート:
アイデア:
ソートする一連の数では、前(n−1)[n>=2]の数が既に順番に並んでいると仮定し、n番目の数を前の有序数に挿入し、n番目の数も順番に並んでいるようにする.このように繰り返して、すべて順番が整うまで.接続挿入ソートは、2つのネストされたループから構成されます.外層ループは、比較する数値を識別し、決定する.内側レイヤループは、比較される数値の最終位置を決定します.直接挿入ソートは、比較する数値を前の数値と比較するので、外層サイクルは2番目の数値から始まります.現在の値が比較対象値より大きい場合は、比較対象値より小さい値が見つかって比較対象値を次の位置に配置して終了するまで、比較を継続します.従って、外層サイクルは2番目の数値から始まる.現在の数値が比較対象の数値より大きい場合は、比較対象の数値より小さい値が見つかるまで比較対象の数値を次の位置に配置し、サイクルを終了します.
時間複雑度:O(n 2)*空間複雑度:O(1)*安定性:安定性
2層の循環があり、外層の循環は比較の数値を確定し、tempに格納、第2層の循環はtempと配列inpu[j]の値を比較する.
tempがinpu[j]の値より小さい場合、inpu[j]はinpu[j+1]に後方に移動し、後方に移動し、j--、その後、tempとそのinpu[j-1]の値をj=0になるまで比較し続ける.
ただしtempがinpu[j]の値より大きい場合はinpu[j+1]に配置される.
(二)泡立ちソート:
基本思想:
1回目の発泡ソート:
①まず1番目のレコードのキーワードと2番目のレコードのキーワードを比較し、逆順であれば2つのレコードを交換する.
②次に、2番目のレコードと3番目のレコードのキーワードを比較する.このようにn−1番目のレコードとn番目のレコードのキーワードが比較されるまで.
ソート結果:キーワードの最大レコードが最後のレコードの位置に配置されます.
2回目のバブルソート:前のn−1個の記録を同様に操作し、その結果、キーワードの大きい記録をn−1個目の記録の位置に配置した.
*時間的複雑度:O(n 2)*空間的複雑度:O(1)*安定性:安定ソート
(三)単純選択ソート
基本思想:並べ替える配列の中で第1の最小値と配列の第1の位置を交換して、それから残りの配列の中で、第2の最小値を探し出して、第2の位置と交換して、このように循環して、数列がすべて秩序正しくなるまで.
*時間複雑度:O(n 2)*空間複雑度:O(1)*安定性:不安定
(四)クイックソート
基本思想:ソートする配列の中で1つのkeyを探して、1回のソートを行った後、それより小さい要素はすべてその左側に並んで、それより大きい要素はその右側に並んで、再帰的な思想を利用してそれを並べます.
1回のソート方法:
1、i=0、j=A.lenght-1を定義し、iは最初の数の下付き記号であり、jは最後の数の下付き記号2であり、配列の最後の数Ajから右から左に探し、keyより小さい最初の数を見つけ、Ajと記す.3、配列の最初の数Aiから左から右に探して、最初のkeyより大きい数を見つけて、Aiと記入します.4,交換AiとAj 5,この過程を繰り返して、i=j 6まで、keyの位置を調整して、A[i]とkeyを交換します
時間複雑度:O(nlog 2 n)*空間複雑度:O(nlog 2 n)*安定性:不安定
(一)直接挿入ソート:
アイデア:
ソートする一連の数では、前(n−1)[n>=2]の数が既に順番に並んでいると仮定し、n番目の数を前の有序数に挿入し、n番目の数も順番に並んでいるようにする.このように繰り返して、すべて順番が整うまで.接続挿入ソートは、2つのネストされたループから構成されます.外層ループは、比較する数値を識別し、決定する.内側レイヤループは、比較される数値の最終位置を決定します.直接挿入ソートは、比較する数値を前の数値と比較するので、外層サイクルは2番目の数値から始まります.現在の値が比較対象値より大きい場合は、比較対象値より小さい値が見つかって比較対象値を次の位置に配置して終了するまで、比較を継続します.従って、外層サイクルは2番目の数値から始まる.現在の数値が比較対象の数値より大きい場合は、比較対象の数値より小さい値が見つかるまで比較対象の数値を次の位置に配置し、サイクルを終了します.
時間複雑度:O(n 2)*空間複雑度:O(1)*安定性:安定性
2層の循環があり、外層の循環は比較の数値を確定し、tempに格納、第2層の循環はtempと配列inpu[j]の値を比較する.
tempがinpu[j]の値より小さい場合、inpu[j]はinpu[j+1]に後方に移動し、後方に移動し、j--、その後、tempとそのinpu[j-1]の値をj=0になるまで比較し続ける.
ただしtempがinpu[j]の値より大きい場合はinpu[j+1]に配置される.
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int inpu[] = new int[n];
int i ;
// n
for(i=0;i=0&&inpu[j]>temp;j--) {
inpu[j+1]=inpu[j];
}
inpu[j+1]=temp;
}
//
for( i =0;i
(二)泡立ちソート:
基本思想:
1回目の発泡ソート:
①まず1番目のレコードのキーワードと2番目のレコードのキーワードを比較し、逆順であれば2つのレコードを交換する.
②次に、2番目のレコードと3番目のレコードのキーワードを比較する.このようにn−1番目のレコードとn番目のレコードのキーワードが比較されるまで.
ソート結果:キーワードの最大レコードが最後のレコードの位置に配置されます.
2回目のバブルソート:前のn−1個の記録を同様に操作し、その結果、キーワードの大きい記録をn−1個目の記録の位置に配置した.
*時間的複雑度:O(n 2)*空間的複雑度:O(1)*安定性:安定ソート
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int inpu[] = new int[n];
int i ;
// n
for(i=0;iinpu[j+1]) {
int temp =inpu[j];
inpu[j]=inpu[j+1];
inpu[j+1]=temp;
}
}
}
//
for( i =0;i
(三)単純選択ソート
基本思想:並べ替える配列の中で第1の最小値と配列の第1の位置を交換して、それから残りの配列の中で、第2の最小値を探し出して、第2の位置と交換して、このように循環して、数列がすべて秩序正しくなるまで.
*時間複雑度:O(n 2)*空間複雑度:O(1)*安定性:不安定
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int inpu[] = new int[n];
int i ;
// n
for(i=0;i
(四)クイックソート
基本思想:ソートする配列の中で1つのkeyを探して、1回のソートを行った後、それより小さい要素はすべてその左側に並んで、それより大きい要素はその右側に並んで、再帰的な思想を利用してそれを並べます.
1回のソート方法:
1、i=0、j=A.lenght-1を定義し、iは最初の数の下付き記号であり、jは最後の数の下付き記号2であり、配列の最後の数Ajから右から左に探し、keyより小さい最初の数を見つけ、Ajと記す.3、配列の最初の数Aiから左から右に探して、最初のkeyより大きい数を見つけて、Aiと記入します.4,交換AiとAj 5,この過程を繰り返して、i=j 6まで、keyの位置を調整して、A[i]とkeyを交換します
時間複雑度:O(nlog 2 n)*空間複雑度:O(nlog 2 n)*安定性:不安定
import java.util.Scanner;
public class Sort {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int inpu[] = new int[n];
int i;
for (i = 0; i < n; i++) {
inpu[i] = sc.nextInt();
}
sc.close();
QuickSort(inpu);
for (i = 0; i < n; i++) {
System.out.print(inpu[i] + " ");
}
}
public static void QuickSort(int a[]) {
if (a.length > 0) {
QuickSort(a, 0, a.length - 1);
}
}
public static void QuickSort(int a[], int low, int upper) {
//
if (low >= upper) {
return;
}
int i = low;
int j = upper;
int key = a[low];
while (i < j) {
while (i < j && a[j] > key) {
j--;// ,
}
while (i < j && a[i] <= key) {
i++;// ,
}
if (i < j) {
//
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// key a[i]
// key
int te = a[i];
a[i] = a[low];
a[low] = te;
// key
QuickSort(a, low, i - 1);
// key
QuickSort(a, i + 1, upper);
}
}