並べ替えアルゴリズムのまとめ——交換並べ替え(発泡体の並べ替えと迅速な並べ替え)

2423 ワード

1.泡の並べ替え:
      つまり両方を比較して最終的に並べ替えを完了します.
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