並べ替えアルゴリズムのまとめ——交換並べ替え(発泡体の並べ替えと迅速な並べ替え)
2423 ワード
1.泡の並べ替え:
つまり両方を比較して最終的に並べ替えを完了します.
泡の並べ替えとその改良バージョン(いわゆる改善はマークを追加します.マークの位置が変わっていない時にはすでに並べられています.もう比較的に直接退出しなくてもいいです.)
2.快速並べ替え
早い列とは、一度に並べてある基準数(K)の左の方がこのKより小さく、右の方がKより大きいということです.次に、基準数の左または右の部分に上の並べ替えを繰り返し、最後の配列全体が小さい順から大きい順になり、逆に大きい順から小さい順になります.
順序は具体的には:穴を掘って、大根を植える.
(1)配列の下に0がiであると仮定し、配列下にはarr.length-1がjである.配列左の最初の位置を基準数として掘り出してKに保存します.
(2)jから検索を開始し、k以下の数を見つけ、掘り出してK(つまりiの位置)に植える.
(3)iから探し始めて、Kより大きい数を見つけて、掘り出して、jに載せます.
上の(2)(3)を回してiにする.
ソース:https://www.runoob.com/w3cnote/quick-sort.html
つまり両方を比較して最終的に並べ替えを完了します.
package cn.liu.made;
/**
*
* @author Dick
*
*/
public class Sort {
// m n
public static void sort(int[] arr,int m,int n) {
int temp = arr[n];
arr[n]=arr[m];
arr[m]=temp;
}
}
泡の並べ替えとその改良バージョン(いわゆる改善はマークを追加します.マークの位置が変わっていない時にはすでに並べられています.もう比較的に直接退出しなくてもいいです.)
package cn.liu.made;
import java.util.Arrays;
/**
* , , arr[arr.length-1] , arr[0];
* i+j arr.length-1
* @author Dick
*
*/
public class BubbleSort {
public static int[] bubbleSort(int[] arr) {
if(arr.length<2) {
return arr;
}
for(int i=0;iarr[j+1]) {
Sort.sort(arr, j, j+1);
}
}
System.out.println(" "+i+" :"+Arrays.toString(arr));
}
return arr;
}
//
public static int[] bubbleSortTwo(int[] arr){
if(arr.length<2) {
return arr;
}
boolean sign = false;//
for(int i=0;iarr[j+1]) {
Sort.sort(arr, j, j+1);
sign=true;
}else {
sign=false;
}
}
//
if(sign==false) break;
System.out.println(" "+i+" :"+Arrays.toString(arr));
}
return arr;
}
}
2.快速並べ替え
早い列とは、一度に並べてある基準数(K)の左の方がこのKより小さく、右の方がKより大きいということです.次に、基準数の左または右の部分に上の並べ替えを繰り返し、最後の配列全体が小さい順から大きい順になり、逆に大きい順から小さい順になります.
順序は具体的には:穴を掘って、大根を植える.
(1)配列の下に0がiであると仮定し、配列下にはarr.length-1がjである.配列左の最初の位置を基準数として掘り出してKに保存します.
(2)jから検索を開始し、k以下の数を見つけ、掘り出してK(つまりiの位置)に植える.
(3)iから探し始めて、Kより大きい数を見つけて、掘り出して、jに載せます.
上の(2)(3)を回してiにする.
ソース:https://www.runoob.com/w3cnote/quick-sort.html
package cn.liu.made;
import java.util.Arrays;
public class QuickSort {
private static int m = 0;
//
public static int[] quick(int[] arr) {
quickSort(arr, 0, arr.length-1);
return arr;
}
private static void quickSort(int[] arr,int left,int right) {
// !!(right-left+1)<2 1,
if((right-left+1)<2 || arr == null) return;
int i = left;
int j = right;
int k = arr[left];// k , arr[0]
while(ik) j--;
// arr[k]
if(i