Java配列の一般的なアルゴリズム
3494 ワード
1、配列要素の最大値、最小値、平均数、総和などを求める
2、配列のコピー、反転、検索(線形検索、二分法検索)
3、データ要素の並べ替え
選択ソート(直接選択ソート、スタックソート)
スワップソート(バブルソート、クイックソート)
挿入ソート(直接挿入ソート、折半挿入ソート、Shellソート)
集計ソート
バケツソート
ベースソート
ソート方法の選択は、通常、3つの指標で測定できます.
(1)時間複雑度:分析キーワードの比較回数と記録の移動回数
(2)空間複雑度:ソートアルゴリズムの種類を分析するのにどれだけの補助メモリが必要か
(3)安定性:2つのレコードAとBのキーワード値が等しいが、ソート後のA,Bの前後順が変わらない場合、このソートアルゴリズムは安定しているという
package com.laura.algorithm;
public class ArrayAlgo {
public static void main(String[] args) {
int[] arr1 = new int[] {23, 5, 23, 64, 66, -9, 75, -77, 3};
//
int max = arr1[0];
for (int i = 1; i < arr1.length; i++) {
if (max < arr1[i]) {
max = arr1[i];
}
}
System.out.println(" :" + max);
//
int min = arr1[0];
for (int i = 1; i < arr1.length; i++) {
if (min > arr1[i]) {
min = arr1[i];
}
}
System.out.println(" :" + min);
//
int sum = 0;
for (int i = 0; i < arr1.length; i++) {
sum += arr1[i];
}
System.out.println(" :" + sum);
//
double avg = sum / (double)arr1.length;
System.out.println(" :" + avg);
}
}
2、配列のコピー、反転、検索(線形検索、二分法検索)
package com.laura.algorithm1;
public class Algorithm1 {
public static void main(String[] args) {
int[] array1, array2;
array1 = new int[] {2, 3, 5, 7, 11, 13, 15, 17, 19};
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + " ");
}
// array2 = array1; // : ( , )
array2 = new int[array1.length];
for (int i = 0; i < array2.length; i++) {
array2[i] = array1[i];
}
// array2 array1
for (int i = 0; i < array2.length; i++) {
if (i % 2 == 0) {
array2[i] = 0;
}
}
System.out.println();
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + " ");
}
// - 1
for (int i = 0, j = array1.length -1; i < j; i++, j--) {
int tmp = array1[i];
array1[i] = array1[j];
array1[j] = tmp;
}
System.out.println();
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + " ");
}
// - 2
for (int i = 0; i < array1.length / 2; i++) {
int tmp = array1[i];
array1[i] = array1[array1.length - i - 1];
array1[array1.length -i -1] = tmp;
}
System.out.println();
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + " ");
}
}
}
package com.laura.algorithm1;
public class Algorithm2 {
public static void main(String[] args) {
//
String[] arr1 = new String[] {"MM", "JJ", "GG", "DD", "AA", "BB", "CC"};
String search = "CC";
for (int i =0; i < arr1.length; i++) {
if (arr1[i].equals(search)) {
System.out.println("Found " + search + ", Index is " + i);
break;
}
}
// ( , )
int[] arr2 = new int[] {-99, -54, -2, 0, 2, 33, 43, 256, 999};
int searchNumber = 256;
int head = 0;
int end = arr2.length - 1;
while (head <= end) {
int middle = (head + end) / 2;
if (arr2[middle] == searchNumber) {
System.out.println("Found " + searchNumber + ", Index is " + middle);
break;
} else if (arr2[middle] > searchNumber) {
end = middle - 1;
} else if (arr2[middle] < searchNumber) {
head = middle + 1;
}
}
}
}
3、データ要素の並べ替え
選択ソート(直接選択ソート、スタックソート)
スワップソート(バブルソート、クイックソート)
挿入ソート(直接挿入ソート、折半挿入ソート、Shellソート)
集計ソート
バケツソート
ベースソート
ソート方法の選択は、通常、3つの指標で測定できます.
(1)時間複雑度:分析キーワードの比較回数と記録の移動回数
(2)空間複雑度:ソートアルゴリズムの種類を分析するのにどれだけの補助メモリが必要か
(3)安定性:2つのレコードAとBのキーワード値が等しいが、ソート後のA,Bの前後順が変わらない場合、このソートアルゴリズムは安定しているという