「アルゴリズム」---ソートアルゴリズム
94963 ワード
アルゴリズム#アルゴリズム#
ソースアドレス
第二章並べ替え
バブルソート泡の並べ替えの基本思想:元素の2つを比較して、大きい元素を後ろに移動して、最後まで移動して、それから次の1回を行って、泡のように、毎回最大の元素を上の まで上昇します実装ロジック: コード例
ソートの選択選択ソートの基本思想:まず、配列の中で最も小さい要素を見つけ、次に、配列の最初の要素と位置を交換します(最初の要素が最も小さい要素であれば、それは自分と交換します).次に、残りの要素の中で最小の要素を見つけ、配列の2番目の要素と位置を交換します.配列全体をソートするまで往復します.この方法は、残りの要素のうちの最小を選択し続けるため、選択ソートと呼ばれます.【泡立ち順とは逆の感じ】 ソートフィーチャーを選択:実行時間と入力は関係ありません.最小の要素を見つけるために配列をスキャンしても次のスキャンに何の情報も提供できないという性質は、場合によっては欠点です.ソートを選択する人は、秩序化された配列やプライマリ・キーがすべて等しい配列と、要素がランダムに配列された配列とで使用されるソート時間が同じ長さであることに驚くかもしれません.他のアルゴリズムは入力の初期状態をより上手に利用できることがわかります.データ移動は最小限です.交換のたびに2つの配列要素の値が変更されるため、ソートを選択するにはN回の交換が使用されます.交換回数と配列のサイズは線形関係です.我々が研究する他のいかなるアルゴリズムもこの特徴を備えていない(大部分の成長桁は線形対数または二乗レベルである). コード例
ソートの挿入挿入ソートの主な考え方:通常、人々がブリッジを整理する方法は1枚1枚であり、各カードを他の秩序あるカードの適切な位置に挿入する.コンピュータの実装では、挿入する要素に空間を空けるために、残りのすべての要素を挿入する前に右に1つ移動する必要があります.このアルゴリズムを挿入ソートと呼ぶ.選択ソートと同様に、現在のインデックスの左側のすべての要素は秩序化されていますが、最終的な位置はまだ確定していません.より小さな要素にスペースを空けるために移動する可能性があります.しかし、インデックスが配列の右端に達すると、配列ソートは完了します.選択したソートとは異なり、ソートを挿入するのに要する時間は、入力中の要素の初期順序に依存します.たとえば、大きな要素が整列している(または整列に近い)配列をソートすると、ランダムな配列や逆配列をソートするよりもずっと速くなります.総じて,挿入ソートは部分的に秩序化された配列に対して非常に効率的であり,小規模な配列にも適している.これは、これらのタイプの配列が実際の応用でよく現れ、高度なソートアルゴリズムの中間プロセスでもあるため、重要である.高度なソートアルゴリズムを学習するときに、挿入ソート に再び接触します.コード例
ヒルソートヒルソートの主な考え方:ベースはソートを挿入することです.挿入ソートは、隣接する要素のみを交換するため、要素が配列の一端から他端に少しずつ移動するしかないため、大規模な乱順配列のソートが遅い.ルソートの考え方は,配列中の任意の間隔hの要素を秩序化させることである.このような配列をh秩序配列と呼ぶ.すなわち、1つのh秩序配列は、h個の互いに独立した秩序配列が織り込まれた配列である.ソートを行うとき,hが大きいと,要素を遠くに移動し,より小さなh秩序を実現するために便利になる.このようにして,任意の1で終わるhシーケンスに対して配列をソートすることができる.これがヒルソートです. コード例
集計ソート
『アルゴリズム』の本の中の集計ソート集計ソート「アルゴリズム」の本の主な説明:集計ソートを理解するには、このメソッド呼び出しの動的状況をよく研究し、a[0...15]をソートするには、sort()メソッドがa[0...7]をソートするように呼び出し、その中でa[0...3]とa[0...1]をソートするように呼び出す.a[0]とa[1]をそれぞれ並べ替えた後、やっとa[0]とa[1]を並べ替え始めた(簡単に言えば、軌跡では単一要素の配列を並べ替える呼び出しを省略した).2回目の集計はa[2]とa[3]であり、次いでa[0......1]とa[2......3]であり、このように推定される.この軌跡から,sort()メソッドの役割は,実際には複数回のmerge()メソッド呼び出しの正しい順序を手配することにあることがわかる.後のセクションでは、この発見も使用されます. 本のコード例
学習中の集計アルゴリズムV 1バージョン主な思想:分治再帰の思想を採用して、もし全体の配列の順序を必要とするならば、まず配列を2つの半分に分けて、2つの半分の配列はそれぞれ順序を並べて、それから2つの半分の配列を1つの秩序ある配列に合併して再帰して配列を2つの半分に分けて、配列の左側と右辺がすべて1つの数だけあるまで、左右の2つの数を直接1つの秩序配列に統合すれば である.本人コード例V 1バージョン
学習中の集計アルゴリズムV 2バージョン主な考え方:V 1バージョンの欠点は、マージするたびに一時配列を作成する必要があることであり、ソートする必要がある数が非常に大きい場合、大量の一時配列の作成と破棄が発生し、空間の浪費を招くため、V 2バージョンは元の配列の長さと一致する一時配列、例えばleft-mid+1-rightの2つの配列を作成し、一時配列の長さが元の配列と一致するため、結合した要素を一時配列のleft-right位置に入れ、元の配列の同じ位置にコピーします.これにより、一時配列を作成するだけで、スペースとGCの圧力を節約できます. 本人コード例V 2バージョン
クイックソート
学習中に自分で実現した迅速なソート基本思想:高速ソートが流行しているのは、単純で、様々な異なる入力データに適用され、一般的な応用では他のソートアルゴリズムよりもずっと速いためである.高速ソートの特徴としては、その場ソート(小さな補助スタックのみ)であり、長さNの配列ソートに要する時間がNlgNに比例することが挙げられる.我々が学習したソートアルゴリズムは,この2つの利点を結びつけることができない.さらに、高速ソートの内部サイクルは、ほとんどのソートアルゴリズムよりも短く、理論的にも実際的にも高速であることを意味する.高速ソートは、分治的なソートアルゴリズムです.1つの配列を2つのサブ配列に分割し、2つの部分を独立して並べ替えます.高速ソートと集計ソートは相補的です.集計ソートは配列を2つのサブ配列に分けてそれぞれソートし、整列したサブ配列を集計して配列全体をソートします.高速ソートで配列をソートする方法は、2つのサブ配列が整列している場合、配列全体が自然に整列します.第1の場合、再帰呼び出しは、配列全体を処理する前に発生する.第2の場合、再帰呼び出しは、配列全体を処理した後に発生する.集計ソートでは、1つの配列が2つに等分されます.クイックソートでは、分割(partition)の位置は配列の内容に依存します. 個人の理解:迅速なソートを理解するには、集計ソートと比較する必要があります.集計ソートの基本思想は元の配列を切り分けることであり、左側の配列が秩序正しく、右側の配列も秩序正しくあれば、左右の両側の配列を統合して秩序ある配列にすることができる.マージプロセスは簡単です.左右の2つの秩序配列を最初の要素から遍歴し、比較すると、その小さい要素は2つの秩序配列を1つの秩序配列にマージするまで前になります.再帰の臨界条件は、ソートが必要な配列が1つの要素が残っている場合に、左右の2つの配列に分割して再帰ソートする必要はありません.デフォルトの1つの要素は秩序化されています.集計ソートの欠点は、一時的にマージされた秩序配列を格納するために一時的な配列が必要です.空間の占有は元の配列と関係があり、元の配列が大きいほど、スペースの占有量が大きくなります.高速ソートの基本思想は一部の集計ソートの思想を参考にしたが、一時配列の問題を解決し、元の配列をその場でソートさせる主な思想は、まず分割が必要な境界点を確定し、それから境界点の位置を見つけ、境界点の左側の境界点より大きい要素を右に、右の境界点より小さい要素を左に置くことである.そして左右のデータに対しても1つの分割された境界点を確定し、境界点によって左側が境界点より小さく、右側が境界点より大きい2つの配列に分割し、絶えず再帰し、両側の配列を秩序配列に変えると、全体の配列も秩序化され、左右の配列が秩序化すれば、全体の配列も秩序化され、集計に対して並べ替えられる.最後の集計操作が少なくなりました. 本人コード例
『アルゴリズム』の本の急速なソート本のコード例
プロジェクトで使用されるツールクラス
ソースアドレス
第二章並べ替え
バブルソート
public class BubblingSort {
public static void sort(int[] arr){
int length = arr.length;
while (length>0){
for(int i=1;i<length;i++){
if(arr[i-1]>arr[i]){
// ， ，
U.swap(arr,i-1,i);
}
}
length--;
}
}
}
ソートの選択
public class SelectorSort {
public static void sort(int[] arr){
if(null==arr)
throw new IllegalArgumentException(" ");
for(int i=0; i<arr.length; i++){
// i
int min = i;
for(int j=i+1;j<arr.length-1;j++){
if(arr[j] < arr[min]){
min = j;
}
}
// i
U.swap(arr,i,min);
}
}
}
ソートの挿入
public class InsertSort{
/**
* ： ， ， ，
* @param arr
*/
public static void sort(int[] arr){
for(int i=1;i<arr.length;i++){
//
//1.
int index = find(arr,0,i-1,arr[i]);
//2. ，
insertIndex(arr,index,i-1,arr[i]);
}
}
private static int find(int[] arr,int left,int right,int value){
// ，
if(value >= arr[right]){
return right+1;
}
// ，
if(value <= arr[left]){
return left;
}
//
while (right > left){
if(arr[right]==value || arr[right-1]==value){
return right;
}else if(arr[right] > value && arr[right-1] < value){
return right;
}
right--;
}
throw new IllegalArgumentException(" ");
}
private static void insertIndex(int[] arr,int index,int right,int value){
//
while (right >= index){
U.swap(arr,right,right+1);
right--;
}
arr[index] = value;
}
public static void sort_simulate(int[] arr){
for(int i=1;i<arr.length;i++){
int j = i;
while (j>0 && arr[j] < arr[j-1]){
U.swap(arr,j,j-1);
j--;
}
}
}
/**
* ， ， ，
* ： 1 N-1 i， a[i] a[0] a[i-1] 。
* i ， ， i 。
* @param arr
*/
public static void sort_book(int[] arr){
for(int i=1;i<arr.length;i++){
for(int j=i;j>0 && arr[j]<arr[j-1];j--){
U.swap(arr,j,j-1);
}
}
}
}
ヒルソート
public class ShellSort {
/**
* ： h， h=3， 3 arr ， [0,3,6,9][1,4,7,10][2,5,8]
* ， h ， 2， [0,2,4,6,8,10][1,3,5,7,9]
* 2 ， h 1， [0,1,2,3,4,5,6,7,8,9,10]，
* ， ， ， ，
* ， ， ，
* @param arr
*/
public static void sort(int[] arr){
int h = arr.length/3;
while (h>0){
for(int i=0;i<arr.length;i++){
int j = i;
while (j>=0 && (j+h)<arr.length && arr[j+h]<arr[j]){
U.swap(arr,j,j+h);
j-=h;
}
}
h--;
}
}
}
集計ソート
『アルゴリズム』の本の中の集計ソート
public class Merge {
/**
* ，
* ， ， ，
* 。 ，
* ， ， 。
* merge(a, lo,mid, hi)， a[lo..mid] a[mid+1..hi] a[lo..hi] 。
*
*/
private static void merge(int[] a,int lo,int mid,int hi){
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) // a[lo..hi] aux[lo..hi]
aux[k] = a[k];
for (int k = lo; k <= hi; k++) // a[lo..hi]
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi ) {
a[k] = aux[i++];
} else if (aux[j] < aux[i]) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
private static int[] aux; //
public static void sort(int[] a)
{
aux = new int[a.length]; //
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi)
{ // a[lo..hi]
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); //
sort(a, mid+1, hi); //
merge(a, lo, mid, hi); // （ “ ”）
}
}
学習中の集計アルゴリズムV 1バージョン
public class MyMerge {
/**
* ： ， ， ，
* 1.
* 2.
*/
public static void sort(int[] arr){
sort(arr,0,arr.length-1);
}
/**
* ， left-mid， mid+1-right
* ，
* ： ， ，
* @param arr
* @param left
* @param right
*/
private static void sort(int[] arr,int left,int right){
// ，
if(left == right){
return;
}
int mid = (left+right)/2;
//
sort(arr,left,mid);
//
sort(arr,mid+1,right);
// ，
merge(arr,left,mid,right);
}
private static void merge(int[] arr,int left,int mid,int right){
//
int[] temp = new int[right-left+1];
int temp_index = 0;
//
int temp_left = left;
int temp_right = mid+1;
// ， ，
while (temp_left<=mid && temp_right<=right){
if(arr[temp_left]<arr[temp_right]){
temp[temp_index++] = arr[temp_left++];
}else{
temp[temp_index++] = arr[temp_right++];
}
}
// ， ，
while (temp_left<=mid){
temp[temp_index++] = arr[temp_left++];
}
while (temp_right<=right){
temp[temp_index++] = arr[temp_right++];
}
// ， arr left right
for(int i=0;i<temp_index;i++){
arr[left+i] = temp[i];
}
}
}
学習中の集計アルゴリズムV 2バージョン
public class MyMergeV2 {
private static int[] tempArr;
public static void sort(int[] arr) {
tempArr = new int[arr.length];
sort(arr, 0, arr.length - 1);
}
/**
* left-right ， ，
* @param arr
* @param left
* @param right
*/
private static void sort(int[] arr, int left, int right) {
// left==right， 1，
if(left == right){
return;
}
int mid = (left+right)/2;
sort(arr,left,mid);
sort(arr,mid+1,right);
if(arr[mid]>arr[mid+1]){
//**** ： ， ， left-right ，
merge(arr,left,mid,right);
}
}
/**
*
* @param arr
* @param left
* @param mid
* @param right
*/
private static void merge(int[] arr,int left,int mid,int right){
// ， ，
int temp_left = left;
int temp_right = mid+1;
int temp_index = left;
while (temp_left<=mid && temp_right<=right){
//
if(arr[temp_left]<arr[temp_right]){
// ，
tempArr[temp_index++] = arr[temp_left++];
}else{
// ，
tempArr[temp_index++] = arr[temp_right++];
}
}
// ， ， ， ，
while (temp_left<=mid){
//
tempArr[temp_index++] = arr[temp_left++];
}
while (temp_right<=right){
//
tempArr[temp_index++] = arr[temp_right++];
}
//
for(int i=left;i<=right;i++){
arr[i] = tempArr[i];
}
}
}
クイックソート
学習中に自分で実現した迅速なソート
public class MyFastSort {
public static void sort(int[] arr){
sort(arr,0,arr.length-1);
}
private static void sort(int[] arr,int left,int right){
// left==right， ， ，
if(left >= right){
return;
}
int index = sharding(arr,left,right);
//
sort(arr,left,index);
sort(arr,index+1,right);
}
/**
* arr[left-right] ， ， ， ，
* ， ， ，
* @param arr
* @param left
* @param right
* @return
*/
private static int sharding(int[] arr, int left, int right) {
int index = left;
//
int val = arr[left];
// ， left+1 right， ， ，
int temp_left = left+1;
int temp_right = right;
while (temp_left<temp_right){
// var ， left val，
while (arr[temp_left]<=val && temp_left<temp_right){
temp_left++;
}
while (arr[temp_right]>=val && temp_left<temp_right){
temp_right--;
}
// ， val， val， val ， ，
if(temp_left==temp_right){
if(arr[temp_left]<val){
//temp_left ， temp_left val
U.swap(arr,left,temp_left);
index = temp_left;
}else{
// temp_left val ， temp_left-1 val
U.swap(arr,left,temp_left-1);
index = temp_left-1;
}
}else{
// ， val ， val ，
U.swap(arr,temp_left,temp_right);
}
}
return index;
}
}
『アルゴリズム』の本の急速なソート
public class FastSort {
public static void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
if (right <= left) {
return;
}
int j = partition(arr, left, right); // （ “ ”）
sort(arr, left, j - 1); // a[lo .. j-1]
sort(arr, j + 1, right); // a[j+1 .. hi]
}
private static int partition(int[] arr, int left, int right) { // a[lo..i-1], a[i], a[i+1..hi]
int i = left, j = right + 1; //
int v = arr[left]; //
while (true) { // ，
while (arr[++i] < v) {
if (i == right) {
break;
}
}
while (v < arr[--j]) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
U.swap(arr, i, j);
}
U.swap(arr, left, j);// v = a[j]
return j; // a[lo..j-1] <= a[j] <= a[j+1..hi]
}
}
プロジェクトで使用されるツールクラス
public final class U {
/**
*
* @param length
* @return
*/
public static int[] getArr(int length){
Random random = new Random();
int[] result = new int[length];
for(int i=0;i<length;i++){
result[i] = random.nextInt(length);
}
return result;
}
/**
*
* @param arr
*/
public static void print(int[] arr){
StringBuffer stringBuffer = new StringBuffer();
for(int i=0;i<arr.length;i++){
if(arr[i] <10 ){
stringBuffer.append(" ");
}else if(arr[i] < 100){
stringBuffer.append(" ");
}else if(arr[i] < 1000){
stringBuffer.append(" ");
}
stringBuffer.append(arr[i]).append(",");
}
System.out.println(stringBuffer.toString());
}
/**
*
* @param arr
* @param firstIndex
* @param secondIndex
*/
public static void swap(int[] arr,int firstIndex,int secondIndex){
int temp = arr[firstIndex];
arr[firstIndex] = arr[secondIndex];
arr[secondIndex] = temp;
}
/**
*
* @param s
* @return
*/
public static int[] transfer(String s){
String[] split = s.split(",");
int[] result = new int[split.length];
for(int i = 0;i<split.length;i++){
if(null!=split[i] && split[i] != ""){
result[i] = Integer.parseInt(split[i].trim());
}
}
return result;
}
/**
*
* @param high
* @param width
* @return
*/
public static int[][] getTwoArr(int high,int width){
int[][] arr = new int[high][width];
int val = 0;
for(int i=0; i<high; i++){
for(int j=0; j<width; j++){
arr[i][j] = val++;
}
}
return arr;
}
/**
*
* @param arr
*/
public static void print(int[][] arr){
for(int i=0;i<arr.length;i++){
print(arr[i]);
}
}
/**
*
* @param arr
*/
public static void assertSort(int[] arr){
int i=0;
while (i<arr.length-2){
if(arr[i] > arr[i+1]){
System.err.println(" ");
return;
}
i++;
}
System.out.println(" ");
}
/**
* /
* @param st
* @param length
*/
public static void fillST(ST<String,String> st,int length){
for(int i=0;i<length;i++){
st.put("key:"+i,"value:"+i);
}
}
public static String buildSTKey(int i){
return "key:"+i;
}
public static String buildSTValue(int i){
return "value:"+i;
}
/**
* a B
* @param a
* @param b
* @return
*/
public static boolean less(Comparable a,Comparable b){
return a.compareTo(b) < 1;
}
}