会社の新入社員の女の子に、この7つの並べ替えアルゴリズムとその実装を教えると、彼女は感心したように私を見た。

序文

最近、並べ替えのアルゴリズムを勉強しているのですが、後で忘れてしまいそうなので、自分の復習のために整理しておきます。

バブルソート

• 並べ替えが完了したことを示す、交換されていないソートダウン次の旅行まで、逆順で見つかった場合、その後2つの2つの交換は、隣接する要素を比較するために、前から後ろにソートされるシーケンスを通じて
• バブルソートは、各トリップの最大値を決定します。

import java.util.Arrays;
public class BubbleSort {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 for (int i = 0; i < array.length ; i++) { //各ソートをループする
 for (int j = 0; j < array.length-1-i ; j++) {
// 各ソートのデータ交換
// 配列[j]は配列[j+1]比較は、データがここの配列の境界を越えてから防ぐために.length 
 int temp = 0;
 if (array[j]>array[j+1]){
 temp = array[j+1];
 array[j+1] = array[j];
 array[j] = temp;
 }
 }
 }
// 2つの方法の出力
// 1.フォーマットされた出力で、すべてのコードのデモの後、インポートする必要がある
 System.out.println(Arrays.toString(array));
// 2.forループ出力
 for (int i = 0; i < array.length ; i++) {
 System.out.print(array[i]+" ");
 }
 }
}

選択ソート

• 最初のソートはarray[0]からarray[array.length-1]までで、array[0]と交換するarray[n]の最小値を見つけ、最初のソートはarray[1]からarray[array.length-1]までで、array[1]と交換するarray[n]の最小値を見つけ、ソートが完了するまで行います。ソートが完了するまでスワップ
• 選択ソートは、各ソートの最小値を決定します。
• 以下は3つの異なるコードの実装です。

import java.util.Arrays;
public class SelectSortDemo01 {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 for (int i = 0; i < array.length-1 ; i++) {
 for (int j = 1+i; j < array.length; j++) {
// このアルゴリズムはバブリングアルゴリズムに似ているが、バブリングアルゴリズムでは各ソートが2対2の比較であるのに対し、このアルゴリズムでは最初の数同士を比較する。
 int temp = 0;
 if (array[i] > array[j]){
 temp = array[j];
 array[j] = array[i];
 array[i] = temp;
 }
 }
 }
 System.out.println(Arrays.toString(array));
 }
}

import java.util.Arrays;
public class SelectSortDemo02 {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 int temp = 0;
 for (int j = 0; j <array.length-1 ; j++) {
 for (int i = 1; (i+j)< array.length ; i++) {
//このアルゴリズムは上のものと似ており、同じ結果を得ることができるので、自分の考えに従って適切なアルゴリズムを選択することができる。
 if (array[j] > array[i+j]) {
 temp = array[i+j];
 array[i+j] = array[j];
 array[j] = temp;
 }
 } 
 }
 System.out.println(Arrays.toString(array));
 }
}

public class SelectSortDemo02 {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 for (int i = 0; i < array.length-1 ; i++) { 
 // 前の2つの方法とは異なり、このアルゴリズムは、各ソートのi番目の数が最小の値を持つことを直接仮定し、現在の添え字iを抽出する。
 // 各ソートでi番目のデータを交換するのが便利である。
 // これも理解しやすい
 int min = array[i];
 int minIndex = i;
 for (int j = 1 + i; j < array.length; j++) {
 if (min > array[j] ){
 // これは、想定される最小値が最小ではないことを示している、あなたは最小値をリセットする必要があり、その後、値を割り当てる必要があるだけで、それを交換する必要はない
 // 最小の値が代入されるまでループを終了させる。
 min = array[j];
 minIndex = j;
 }
 }
// 最も小さい値をarrに入れる[0], 
 if (minIndex != j) {
 array[minIndex] = arr[j];
 array[j] = min;
 }
 }
 System.out.println(Arrays.toString(array));
 }
}

挿入ソート

• n個の数字がある場合、最初の並べ替えは最初の2つの数字を比較して順番に並べ、次の並べ替えは3つの数字を比較して順番に並べます。
• これは、家主のタッチカードとして理解することができ、最初に2つのJとKに触れ、Kの前にJを置くために、JとKの前に配置される6のタッチで、6とJの間に配置される10のタッチで、タッチの行は、注文の終了に相当します。

import java.util.Arrays;
public class InsertSortDemo01 {
 public static void main(String[] args) {
 int[] array = {5, 2, -1, 4, 7};
 for (int i = 1; i < array.length; i++) {
// 選択ソートの3番目のタイプと同様に、最初に挿入するデータと挿入の位置を定義するので、その後の値を割り当てることは容易である。
 int insertVal = array[i];
// を配列に挿入する。[i]の最初の位置は
 int insertIndex = i - 1;
// 挿入する位置は0以上でなければならず、配列が範囲外にならないようにする。
 while (insertIndex >= 0 && insertVal < array[insertIndex]) {
// データを交換せずに直接代入する
 array[insertIndex + 1] = array[insertIndex];
// i番目の数字が前の数字と比較され、値が割り当てられるためには、前の条件は必要ないが、配列が境界を越える心配はない。
 insertIndex--;
 }
// insertIndex + 1 = i i番目のラウンドが順序付けられたことを示す
 if (insertIndex + 1 != i) {
 array[insertIndex + 1] = insertVal;
 }
 }
 System.out.println(Arrays.toString(array));
 }
}

ヒルソート

• ヒルソートは挿入ソートを最適化することと同じであり、縮小インクリメンタルソートです。
• Hill sort first trip according to the arraylength2 for grouping, each group, respectively, direct insertion sort, the second trip according to the arraylength2 for grouping, each group, respectively, direct insertion sort, until increment is reduced to one, whole file is divided into group of exactly
• 以下は2つの異なるコードの実装です。

import java.util.Arrays;
// スワップ法は、このメソッドの速度は非常に遅い。
// 挿入ソートは、比較後に直接シフトするのに対し、このタイプのメソッドは、逆順に遭遇するとすぐに交換するからだ。
// スワップ法はバブルソートに似ているが、スワップし続けるのは非効率的である。
public class ShellSortDemo02 {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 int temp = 0;
 for (int len = array.length/2; len > 0;len/=2) {
// 各グループ化をループする
 for (int i = len; i < array.length; i++) {
// 各グループのすべての要素を繰り返し、lenグループがある
 for (int j = i - len; j >= 0; j -= len) {
 if (array[j] > array[j + len]) {
 temp = array[j];
 array[j] = array[j + len];
 array[j + len] = temp;
 }
 }
 }
 }
 System.out.println(Arrays.toString(array));
 }
}

import java.util.Arrays;
public class ShellSortDemo03 {
// シフトを利用した、スワップによるヒルのソートの最適化。
// 挿入される数が最小の場合、後方への移動の数が大幅に増加するため、グループ挿入ソートを使用すると大幅に効率を向上させる。
 public static void main(String[] args) {
 int[] array = {, -3, 6, 8, 1, -6, -5, 4};
// まだインクリメンタルlenを使用して、徐々にインクリメントを縮小する
 for (int len = array.length / 2; len > 0; len /= 2) {
// 直接挿入ソートは、グループごとに実行される。
 for (int i = len; i < array.length; i++) {
 int j = i;
 int temp = array[j];
 if (array[j] < array[j - len]) {
 while (j-len >= 0 && temp < array[j - len]) {
// シフト、および直接挿入ソートは、これとは異なるレンデータシフト間の距離であり、直接挿入ソートは2つのシフトによって2である
 array[j] = array[j - len];
 j -=len;
 }
// whileループを抜けると、tempが挿入される場所が見つかる。
 array[j] = temp;
 }
 }
 }
 System.out.println(Arrays.toString(array));
 }
}

ラピッドソート

• ラピッドソートは、バブルソートの改善であり、ベンチマークとしての番号の真ん中に最初の旅行の並べ替えは、この番号の左側に彼の小さい数よりも、この番号の右側に彼の大きい数よりも、配列は、ベンチマークとしての番号の最初の並べ替えの真ん中の右と左に最初の旅行に2番目の旅行の並べ替えは、上記の操作のそれぞれの繰り返しで

import java.util.Arrays;
public class QuickSortDemo01 {
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 quickSort(array,0,array.length-1);
 System.out.println(Arrays.toString(array));
 }
 public static void quickSort(int a[],int l,int r){
 if(l>=r)
 return;
 int i = l; int j = r; int key = a[(l+r)/2];
// 最初の数字をキーとして、配列の真ん中の数字を例として選ぶ。
 while(i<j){
 while(i<j && a[j]>=key)
// 右から左へキーより小さい最初の値を見つけ、見つけたらjを前に進める。
 j--;
//  [j]<key [j]が一番前に置かれる。[i]同時に、iは後ろにシフトされる
 if(i<j){
 a[i] = a[j];
 i++;
 }
 while(i<j && a[i]<key)
// 左から右へキーより大きい最初の値を見つけ、iを見つけたら戻る。
 i++;
//  [i]>key [i]の後ろに置かれる。[j]同時に、jは前方にシフトされる
 if(i<j){
 a[j] = a[i];
 j--;
 }
 }
 //i == j
 a[i] = key;
 quickSort(a, l, i-1);//再帰呼び出し
 quickSort(a, i+1, r);//再帰呼び出し
 }
}

マージソート

• 合併アルゴリズムの中核となる考え方は、合併で分解することです、つまり、パーティション、分解が再帰的に使用することができます、低としてインデックス付けされた右端の要素の配列を設定し、高さとしてインデックス付けされた左端の要素、/ 2としてインデックス付けされた中央の要素は、各分解は、低==高さ、配列全体が各要素に分解されるときに見つけることができる、合併は、それが順序付けされるまで、2つの順序マージセグメントの合併です。整列されたマージセグメントに対して、整列された

import java.util.Arrays;
public class MergeSortDemo01 {
 //マージ機能
 public static void merge(int[] array,int low,int mid,int height){
 int s1 = low;
 int s2 = mid+1;
 int[] ret = new int[height-low+1];
 int i = 0;//はret配列の添え字である
 while (s1<=mid && s2<=height){
 if (array[s1]<=array[s2]){
 ret[i++] = array[s1++];
 }else{
 ret[i++] = array[s2++];
 }
 }
 while (s1<=mid){
 ret[i++] = array[s1++];
 }
 while (s2<=height){
 ret[i++] = array[s2++];
 }
 for (int j=0;j<ret.length;j++){
 array[low+j] = ret[j];
 }
 }
 public static void mergeSort(int[]array,int low,int height){
 if (low>=height){
 return;
 }
 int mid = (low+height)/2;
 mergeSort(array,low,mid);//左半分の再帰的分解
 mergeSort(array,mid+1,height);//再帰的に右半分を分解する
 merge(array,low,mid,height);//マージ操作
 }
 public static void main(String[] args) {
 int array[] = {,-3,6,8,1,-6,-5,4};
 System.out.println(Arrays.toString(array));
 mergeSort(array,0,array.length-1);
 System.out.println(Arrays.toString(array));
 }
}

ベースソート

• 基本的に、整数は桁ごとに異なる数字に切り分けられ、各桁ごとに別々に比較されます。
• 10番号0〜9の一次元配列を定義し、各桁の数は、配列の対応する番号に配置された見つけ、次に桁の数を取り出す配列の対応する番号に配置された、順番にそれを取るために最高位まで！
• ベースオーダーは最も効率的な安定オーダー法

import java.util.Arrays;
public class RadixSortDemo01 {
 public static void main(String[] args) {
 int array[] = {, , , 48};
 radixSort(array);
 }
 //基本ソートアルゴリズム
 public static void radixSort(int[] arr) {
 int max = arr[0];
// 最初の数が最大の数であると仮定する
 for (int i = 0; i < arr.length; i++) {
 if (arr[i] > max) {
 max = arr[i];
 }
 }
 int maxLength = (max + " ").length();
// 10バケットの2次元配列を定義し、各バケットは、データの1次元配列である。
// 数値を入れる際にデータのオーバーフローを防ぐため、各1次元配列のサイズはarrを配置する。.length
 int[][] bucket = new int[10][arr.length];
// 各バケットに格納されている実際のデータ量を記録するために、1次元配列を定義し、各バケットに毎回入れられたデータの数を記録するために1次元配列を定義する。
 int[] bucketCounts = new int[10];
 for (int k=0,n=1;k<maxLength-1;k++,n *=10){
 for (int i = 0; i < arr.length; i++) {
// 各要素の最初の桁を取り出す
 int digitOfElement = arr[i] / n % 10;
// 対応するバケツに入れる
 bucket[digitOfElement][bucketCounts[digitOfElement]] = arr[i];
// バケツにデータを入れるたびに、バケツ内のデータが1つずつ増えていく。
 bucketCounts[digitOfElement]++;
 }
// バケツの順序によると
 int index = 0;
// 各バケツを繰り返し、バケツ内のデータを元の配列に入れる。
 for (int i = 0; i < bucketCounts.length; i++) {
// バケツの中にデータがあれば、それを元の配列に入れる。
 if (bucketCounts[i] != 0) {
 for (int j = 0; j < bucketCounts[i]; j++) {
// 要素を取り出して配列に入れる
 arr[index++] = bucket[i][j];
 }
 }
// 処理の最初のラウンドの後、各バケットを置く必要があるCounts[i] = 0;
 bucketCounts[i] = 0;
 }
 System.out.println(" "+(k+1)+"回転配列=" + Arrays.toString(arr));
 }
 }
}