バブルソート-java実装
バブルソートは一般的なソートアルゴリズムであり,そのコア部分は二重ネストサイクルであるため,バブルソートの時間的複雑さはO(N 2)である.その基本思想は、隣接する2つの要素を比較するたびに、彼らの順序が間違っている場合は交換することです(ここで、順序は私たちが予め設定した大きいものから小さいものまで、または小さいものから大きいものまで).
たとえば、グループの数を大きいものから小さいものまでソートする必要があります.大きいものから小さいものまで並べ替えている以上、小さいものほど後ろに寄っています.隣接する2つの数を比較するたびに、後ろの数が前の数より大きい場合は、この2つの数の位置を交換します.最後の2つの数が比較されるまで比較した後、最小の数は最後の1つで、このように私たちは最小の数の位置を確定して、“1回”が完成したことを説明して、1回ごとに1つの数の位置しか確定できません.プロセス全体が気泡に似ているため、一歩一歩上に「出る」ので、「泡ソート」アルゴリズムと呼ばれます.
まとめて拡張すると,n個の数がソートされている場合,n−1個の数の位置,すなわちn−1回の操作を行うだけである.「1回ごとに」は、1位から隣接する2つの数の比較を行い、小さい数を後ろに置き、比較が終わったら1つ後ろに移動し、次の2つの隣接数の大きさを比較し続け、最後の未確定位置の数まで繰り返す必要があります.バブルソートの利点は、ソートを行うたびに比較が少なくなることが明らかである.ソートを行うたびに小さな値が見つかり、次のソートでもその数と比較する必要がないからである.
次にjavaコードでバブルソートを実現します.
たとえば、グループの数を大きいものから小さいものまでソートする必要があります.大きいものから小さいものまで並べ替えている以上、小さいものほど後ろに寄っています.隣接する2つの数を比較するたびに、後ろの数が前の数より大きい場合は、この2つの数の位置を交換します.最後の2つの数が比較されるまで比較した後、最小の数は最後の1つで、このように私たちは最小の数の位置を確定して、“1回”が完成したことを説明して、1回ごとに1つの数の位置しか確定できません.プロセス全体が気泡に似ているため、一歩一歩上に「出る」ので、「泡ソート」アルゴリズムと呼ばれます.
まとめて拡張すると,n個の数がソートされている場合,n−1個の数の位置,すなわちn−1回の操作を行うだけである.「1回ごとに」は、1位から隣接する2つの数の比較を行い、小さい数を後ろに置き、比較が終わったら1つ後ろに移動し、次の2つの隣接数の大きさを比較し続け、最後の未確定位置の数まで繰り返す必要があります.バブルソートの利点は、ソートを行うたびに比較が少なくなることが明らかである.ソートを行うたびに小さな値が見つかり、次のソートでもその数と比較する必要がないからである.
次にjavaコードでバブルソートを実現します.
package test;
public class test5 {
public static void main(String[] args) {
int a[] = {12,23,24,11,66,43,98,70,1,2};
System.out.println("sort before:");
printArray(a);
System.out.println("after bubbleSort:");
bubbleSort(a);
printArray(a);
}
public static void bubbleSort(int[] a) {
int temp = 0;
int n = a.length;
// ,n , n-1
for(int i = 0; i < n-1; i++) {
// , 1
for(int j = 0; j < n-i-1; j++) {
//
if (a[j] < a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
public static void printArray(int[] numbers) {
for (int i = 0 ; i < numbers.length ; i ++ ) {
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
}
:
sort before:
12,23,24,11,66,43,98,70,1,2,
after bubbleSort:
98,70,66,43,24,23,12,11,2,1,