Androidでよく使われる5種類のソートアルゴリズム
13172 ワード
androidでは、複雑な論理を実現するためにいくつかのアルゴリズムがよく使用されます.このブログでは主に5つのアルゴリズムを紹介しています.
以下を見る前に、アルゴリズム言語の表現が弱い場合があり、以下の博文を見るときはコードの上に注意しなければならない.
1.ソートの選択
配列の一端から配列の要素を選択し、比較によって最小値(または最大値)をarrayの左側(右側は主に遍歴の開始が左か右か)に置く.一つ一つ遍歴する.コードを次に示します.
2.ソートの挿入
同様に配列を1つずつ遍歴し、2つずつ比較し、遍歴した要素とその前の要素を配列する.遍歴が完了し、ソートも完了します.
3.クイックソート
次はクイックソートを見てみましょう.要素(一般的にarrayの最初の要素)を選択し、ターゲット要素としてarrayのターゲット要素より小さいものをターゲット要素の左側に、ターゲット要素より大きいものをターゲット要素の右側に配置します.そして左右のarrayを同じ方法で並べ続けます.コードを見てみましょう.
4.連結ソート
集計ソートとは、配列を分割し、比較的多くのものを挿入ソートでソートすることです.要素や複雑な状況を処理するために使用されます.分けて治め、合わせて一つにする.
5.ヒープのソート
まず、スタックを紹介します.スタックはどのルートの要素が左右の子供より大きい(または小さい)完全な二叉木のスタックの順序を備えています.実は、ずっと大きなスタックや小さなスタックを構築しています.それから、スタックと最後の要素を交換して、それからスタックを排除して、他の要素をトップスタックに再構築して、再びトップ要素を交換して、このような循環往復の過程です.OK~次はコードを見ます:
期待意見を読んでくれてありがとう
1. ;
2. ;
3. ;
4. ;
5. ;
以下を見る前に、アルゴリズム言語の表現が弱い場合があり、以下の博文を見るときはコードの上に注意しなければならない.
1.ソートの選択
配列の一端から配列の要素を選択し、比較によって最小値(または最大値)をarrayの左側(右側は主に遍歴の開始が左か右か)に置く.一つ一つ遍歴する.コードを次に示します.
/**
* */
public static int[] select(int[] array){
for (int i = 0; i < array.length; i++) {
int minPos = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minPos]){
minPos = j;
}
}
if (array[i] > array[minPos]){
int temp = array[i];
array[i] = array[minPos];
array[minPos] = temp;
}
}
return array;
}
2.ソートの挿入
同様に配列を1つずつ遍歴し、2つずつ比較し、遍歴した要素とその前の要素を配列する.遍歴が完了し、ソートも完了します.
/***
* 0 ++
* */
public static int[] insert(int[] array){
for (int i = 1; i < array.length; i++) {
int temp = array[i];
for (int j = i - 1; j >= 0 ; j--) {
if (array[j] > temp ){
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
3.クイックソート
次はクイックソートを見てみましょう.要素(一般的にarrayの最初の要素)を選択し、ターゲット要素としてarrayのターゲット要素より小さいものをターゲット要素の左側に、ターゲット要素より大きいものをターゲット要素の右側に配置します.そして左右のarrayを同じ方法で並べ続けます.コードを見てみましょう.
/**
*
* */
public static int[] quick(int[] array){
int length = array.length - 1;
sortQuick(array,0,length);
return array;
}
private static void sortQuick(int[] array, int low, int length) {
if(low < length){
int div = firstRun(array, low, length);
sortQuick(array,0,div - 1);
sortQuick(array,div + 1,length);
}
}
private static int firstRun(int[] array, int low, int length) {
int base = array[low];
while (low < length){
while (array[length] > base){
length--;
}
swrap(array,low,length);
while (array[low] < base){
low++;
}
swrap(array,low,length);
}
return low;
}
private static void swrap(int[] array, int low, int length) {
int temp = array[length];
array[length] = array[low];
array[low] = temp;
//return array;
}
4.連結ソート
集計ソートとは、配列を分割し、比較的多くのものを挿入ソートでソートすることです.要素や複雑な状況を処理するために使用されます.分けて治め、合わせて一つにする.
/**
*
* */
public static int[] mesh(int[] array){
int length = array.length - 1 ;
int[] mysort = mysort(array, 0, length);
return mysort;
}
private static int[] mysort(int[] array, int low, int length) {
int mid = (length + low)/2;
if (low < length){
mysort(array,low,mid);
mysort(array,mid + 1,length);
merge(array,low,mid,length);
}
return array;
}
private static void merge(int[] array, int low, int mid, int length) {
int[] temp = new int[length - low + 1];
int i = low;
int j = mid + 1;
int n = 0;
while (i <= mid && j <= length){
if (array[i] > array[j]){
temp[n++] = array[j++];
}else {
temp[n++] = array[i++];
}
}
while (i <= mid){
temp[n++] = array[i++];
}
while (j <= length){
temp[n++] = array[j++];
}
// array
for (int k = 0; k < temp.length; k++) {
array[low + k] = temp[k];
}
}
5.ヒープのソート
まず、スタックを紹介します.スタックはどのルートの要素が左右の子供より大きい(または小さい)完全な二叉木のスタックの順序を備えています.実は、ずっと大きなスタックや小さなスタックを構築しています.それから、スタックと最後の要素を交換して、それからスタックを排除して、他の要素をトップスタックに再構築して、再びトップ要素を交換して、このような循環往復の過程です.OK~次はコードを見ます:
/**
*
*
* */
public static int[] heap(int[] array){
int length = array.length - 1;
for (int i = 0; i < length; i++) {
buildHeap(array,length - i);
swapHeap(array,0,length - i);
}
return array;
}
private static void swapHeap(int[] array, int a, int b) {
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
private static void buildHeap(int[] array, int lastIndex) {
//
int pos = (lastIndex - 1)/2;
for (int i = pos; i >= 0; i--) {
int childL = i * 2 + 1;
int childR = i * 2 + 2;
int maxIndex = childL;
if (childR <= lastIndex){
//
if (array[childL] < array[childR]){
maxIndex ++;
}
}else if (childL <= lastIndex){
//
}
if (array[i] < array[maxIndex]){
swrap(array,i,maxIndex);
}
}
}
期待意見を読んでくれてありがとう