最近、並べ替えのアルゴリズムを勉強しているのですが、後で忘れてしまいそうなので、自分の復習のために整理しておきます。
バブルソート
- 並べ替えが完了したことを示す、交換されていないソートダウン次の旅行まで、逆順で見つかった場合、その後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++) {
// 各ソート旅行のためのデータ交換
// array[j] array[j+1]比較は、ここで国境を越えてからデータを防ぐためにarray.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つずつ比較され、これは最初の数字と比較する各数値である
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を抽出する。
// データ交換と各ソート旅行の利便性
// これはまた、理解しやすくなる
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];
// に挿入される番号を挿入するためにarray[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--;
// a[j]<key a[j]の前に置かれるa[i]同時に、私は戻って移動する
if(i<j){
a[i] = a[j];
i++;
}
while(i<j && a[i]<key)
// 左から右へキーよりも大きい最初の値を見つけるために、シフトの背面にiを見つける
i++;
// a[i]>key a[i]の後ろに置かれるa[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];
// 各データは、このバケツに追加されるデータを置く
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
arr[index++] = bucket[i][j];
}
}
// 処理の最初のラウンドの後にそれぞれである必要があるbucketCounts[i] = 0;
bucketCounts[i] = 0;
}
System.out.println(" "+(k+1)+" arr =" + Arrays.toString(arr));
}
}
}
上記は、この記事の内容であり、最初の記事は、あなたがそれをサポートするために注意を払うことができます好きです！
