「ソート」「単純数学計算」「単純アルゴリズム」「Java実装」(データ構造とアルゴリズム)(復習)(継続更新)を検索します.
ソート法
さいさじかんぶんせき
へいきんじかんふくざつさ
あんていど
くうかんふくざつさ
バブルソート
O(n2)
O(n2)
あんてい
O(1)
クイックソート
O(n2)
O(n*log2n)
ふあんてい
O(log2n)~O(n)
ソートの選択
O(n2)
O(n2)
ふあんてい
O(1)
ツリーのソート
O(n2)
O(n*log2n)
あんてい
O(n)
ソートの挿入
O(n2)
O(n2)
あんてい
O(1)
ヒープのソート
O(n*log2n)
O(n*log2n)
ふあんてい
O(1)
ヒルソート
O
O
ふあんてい
O(1)
半値検索(再帰的でない)
はんてんたんさく
直接挿入ソート
一般に,挿入ソートはin−placeを用いて配列上で実現される.具体的なアルゴリズムは以下の通りである:(wiki)
最初の要素から、この要素はに並べ替えられたと考えられる.
次の要素を取り出し、並べ替えられた要素のシーケンス内で後方からをスキャンする.
要素(並べ替えられた)が新しい要素より大きい場合は、要素を次の位置に移動します.
並べ替えられた要素が新しい要素より小さいまたは等しい場所が見つかるまで、手順3を繰り返します.
新しい要素をこの位置に挿入する手順2~5 を繰り返す
バブルソート
並べ替える数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.このアルゴリズムの名前の由来は,小さな要素ほど交換を介して徐々に数列の先端に「浮かぶ」からである.
バブルソートアルゴリズムは次のように動作します.
隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.
各ペアの隣接要素について同じ作業を行い、最初のペアから最後のペアまで行います.この点では、最後の要素が最大の数になるはずです.
最後の1つを除いて、すべての要素について上記の手順を繰り返します.
比較する必要がなくなるまで、ますます少ない要素に対して上記の手順を繰り返します.
バブルアルゴリズム2、小さいから大きいまで並べ替えて、左から右まで、更にバブルの思想に合って、小さい数字は上へ
単純選択ソート
その動作原理は以下の通りです.まず、ソートされていないシーケンスで最小要素を見つけ、ソートシーケンスの開始位置に保存し、残りのソートされていない要素から最小要素を探し続け、ソートシーケンスの最後に配置します.すべての要素がソートされるまで、このようにします.
さいさじかんぶんせき
へいきんじかんふくざつさ
あんていど
くうかんふくざつさ
バブルソート
O(n2)
O(n2)
あんてい
O(1)
クイックソート
O(n2)
O(n*log2n)
ふあんてい
O(log2n)~O(n)
ソートの選択
O(n2)
O(n2)
ふあんてい
O(1)
ツリーのソート
O(n2)
O(n*log2n)
あんてい
O(n)
ソートの挿入
O(n2)
O(n2)
あんてい
O(1)
ヒープのソート
O(n*log2n)
O(n*log2n)
ふあんてい
O(1)
ヒルソート
O
O
ふあんてい
O(1)
半値検索(再帰的でない)
/**
* （ ）
*
* @param array
* @param key
* @return
*/
public static int Bsearch(int array[], int key) {
int mid;
int low = 0;
int high = array.length - 1;
while (low <= high) {
mid = (low + high) / 2;
if (key == array[mid])
return mid;
else if (key < array[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}はんてんたんさく
/**
* （ ）
* @param array
* @param low
* @param high
* @param key
* @return
*/
public static int BsearchRec(int array[], int low, int high, int key) {
int mid;
if (low <= high) {
mid = (low + high) / 2;
if (key == array[mid])
return mid;
else if (key < array[mid])
return BsearchRec(array, low, mid - 1, key);
else
return BsearchRec(array, mid + 1, high, key);
}
return -1;
}直接挿入ソート
一般に,挿入ソートはin−placeを用いて配列上で実現される.具体的なアルゴリズムは以下の通りである:(wiki)
最初の要素から、この要素はに並べ替えられたと考えられる.
次の要素を取り出し、並べ替えられた要素のシーケンス内で後方からをスキャンする.
要素(並べ替えられた)が新しい要素より大きい場合は、要素を次の位置に移動します.
並べ替えられた要素が新しい要素より小さいまたは等しい場所が見つかるまで、手順3を繰り返します.
新しい要素をこの位置に挿入する手順2~5 を繰り返す
/**
*
*
* @param array
* @return
*/
public static int[] InsertSort(int array[]) {
int n = array.length;
int i, j;
for (i = 0; i < n; i++) {// ：n
int temp = array[i];
for (j = i; j > 0 && temp < array[j - 1]; j--) {
// ，
array[j] = array[j - 1];
}
array[j] = temp;//
}
return array;
}public void insertSort(int a[]) {
int n = a.length;
int temp;
int j;
for (int i = 1; i < n; i++) {
temp = a[i];
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}バブルソート
並べ替える数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.このアルゴリズムの名前の由来は,小さな要素ほど交換を介して徐々に数列の先端に「浮かぶ」からである.
バブルソートアルゴリズムは次のように動作します.
隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.
各ペアの隣接要素について同じ作業を行い、最初のペアから最後のペアまで行います.この点では、最後の要素が最大の数になるはずです.
最後の1つを除いて、すべての要素について上記の手順を繰り返します.
比較する必要がなくなるまで、ますます少ない要素に対して上記の手順を繰り返します.
/**
*
*
* @param array
* @return
*/
public static int[] BubbleSort(int array[]) {
boolean flag = true;
int n = array.length;
int temp = 0;
for (int i = 0; i < n - 1; i++) {// ：n-1 ，
flag = true;
for (int j = 0; j < n - i - 1; j++) {// ：j j+1 ，j n-i-1
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}// ， for flag true，
}
if (flag == true)
break;
}
return array;
}バブルアルゴリズム2、小さいから大きいまで並べ替えて、左から右まで、更にバブルの思想に合って、小さい数字は上へ
/**
* 2， ， ， ，
*
* @param array
* @return
*/
public static int[] BubbleSort2(int array[]) {
boolean flag = true;// ， ， i 。
int n = array.length;
int temp = 0;
for (int i = 0; i < n - 1; i++) {// n-1 （ ）
flag = true;
for (int j = n - 1; j > i; j--) {// ， i
if (array[j] < array[j - 1]) {
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
flag = false;
}
}
if (flag == true)
break;
for (int k = 0; k < array.length; k++) {
System.out.print(array[k] + " ");
}
System.out.println("");
}
return array;
}
単純選択ソート
その動作原理は以下の通りです.まず、ソートされていないシーケンスで最小要素を見つけ、ソートシーケンスの開始位置に保存し、残りのソートされていない要素から最小要素を探し続け、ソートシーケンスの最後に配置します.すべての要素がソートされるまで、このようにします.
/**
*
*
* @param array
* @return
*/
public static int[] SelectSort(int array[]) {
int n = array.length;
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {// n-1 ， ，
min = i;
for (j = i + 1; j < n; j++)
//
if (array[j] < array[min])
min = j;
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
return array;
}
（Divide and conquer） （list） （sub-lists）。
：
- ， " "（pivot），
- ， ， （ ）。 ， 。 （partition） 。
- （recursive） 。
， ， 。 ， ， （iteration） ， 。
/**
*
*
* 1） I、J， ：I=0，J=N-1；
* 2） ， key， key=A[0]；
* 3） J ， （J=J-1）， key A[J]， 4；
* 4） I ， （I=I+1）， key A[I]， A[I] A[J] ； 5） 3、4 ，
* I=J； (3,4 j=j-1，i=i+1， 。 i，
* j 。 i=j i+ j- 。）
*
* @param array
* @param low
* @param high
*/
public void QuickSort(int array[], int low, int high) {
int pivotkey, i, j;
if (low < high) {
pivotkey = array[low];
i = low;
j = high;
while (i < j) {
while (i < j && array[j] >= pivotkey)
j--;
if (i < j)
array[i++] = array[j];
while (i < j && array[i] <= pivotkey)
i++;
if (i < j)
array[j--] = array[i];
}
array[i] = pivotkey;
QuickSort(array, low, i - 1);
QuickSort(array, i + 1, high);
}
}
ソート/**
* ：
*
* @param arrayA
* @param arrayB
* @return
*/
public static int[] MergeSort(int[] arrayA, int[] arrayB) {
int[] arrayC = new int[arrayA.length + arrayB.length];
int k = 0;
int i = 0;
int j = 0;
while (i < arrayA.length && j < arrayB.length) {
if (arrayA[i] < arrayB[j])
arrayC[k++] = arrayA[i++];
else
arrayC[k++] = arrayB[j++];
}
while (i < arrayA.length)
arrayC[k++] = arrayA[i++];
while (j < arrayB.length)
arrayC[k++] = arrayB[j++];
return arrayC;
}
ヒルソート
アルゴリズムの :
まずnより さい d 1を のインクリメントとして り、ファイルのすべての をd 1のグループに け、すべての d 1 の を じグループに く.まず、 グループ で ソートを います. いで、2 のインクリメンタルd 2public void shellSort(int a[]) {
int n = a.length;
int d = n / 2;
int temp;
int i;
int j;
int k;
while (d != 0) {
for (i = 0; i < d; i++) {
for (j = i + d; j < n; j = j + d) {
temp = a[j];
for (k = j - d; k >= 0 && temp < a[k]; k = k - d) {
a[k + d] = a[k];
}
a[k + d] = temp;
}
}
d = d / 2;
}
}
public class ShellSort {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
public static void main(String args[]) {
int i; //
int Index = a.length;//
System.out.print(" : ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
shellSort(Index - 1); //
//
System.out.print(" : ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
}
public static void shellSort(int Index) {
int j, k; //
int Temp; //
boolean Change; //
int DataLength; //
int Pointer; //
DataLength = (int) Index / 2; //
while (DataLength != 0) //
{
//
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // Data[j] ,
Pointer = j - DataLength; //
//
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
//
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
//
a[Pointer + DataLength] = Temp;
if (Change) {
//
System.out.print(" : ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; //
}
}
}
、 がり public static int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
/**
*
*
* @param num1
* @param num2
* @return
*/
public static int gcd(int num1, int num2) {
int r = 0;
while (num2 != 0) {
r = num1 % num2;
num1 = num2;
num2 = r;
}
return num1;
}
～// x y
public static int gcd(int x, int y) {
if (x < y)
return gcd(y, x);
if (y == 0)
return x;
else
return gcd(x - y, y);
}
の で り し の も いその ( に がある)を します/**
*
* @param array
*
* @param num
* （ ）
*/
public static int FindRepeatest(int array[], int num) {
// （ ）
int[] assistArray = new int[num];
//
int max = 0;
for (int i = 0; i < array.length; i++) {
assistArray[array[i]]++;
if (assistArray[array[i]] > assistArray[max])
max = array[i];
}
return max;
}
フィボナッチシーケンスpublic class Fibonacci {
public int F(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return F(n - 1) + F(n - 2);
}
}
public class Fibonacci2 {
public int F2(int a, int b, int n) {
if (n == 1)
return a;
else if (n == 2)
return b;
else
return F2(a, b, n - 1) + F2(a, b, n - 2);
}
}
ハノータ :public class Hanoi {
private int c = 0;
public void hanoi(int n, char x, char y, char z) {
if (n == 1) {
move(x, 1, z);
} else {
hanoi(n - 1, x, z, y);
move(x, n, z);
hanoi(n - 1, y, x, z);
}
}
public void move(char x, int n, char z) {
System.out.println(++c + ". " + n + " " + x + " " + z);
}
public static void main(String[] args) {
Hanoi hanoi = new Hanoi();
hanoi.hanoi(3, 'x', 'y', 'z');
}
}