ソートアルゴリズム関連

一般的なソートアルゴリズムを整理します.
 
筆記試験では選択ソート、面接ではクイックソートを推奨
 
安定性:ソートシーケンスにおいて、値が等しいレコードに対して、ソート前後の相対順序が変わらないことを安定と呼ぶ.
 
泡のソート:
紹介:二層反復、隣接する数の大きさを比較して、結果によって位置を交換します
時間の複雑さ:O(n*n)、nの平方階を読みます
安定性あんていせい:安定性あんていせい
メモ:最も遅いソートアルゴリズム
 
ソートを選択:
紹介:二層反復、最小数の比較と記録、外層反復の要素と交換
時間複雑度:O(n*n)
安定性あんていせい:不安定
備考:バブルアルゴリズムより優れている
 

public class ChooseSort {
	public static void main(String[] args) {
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c);
		for (Comparable data : c) {
			System.out.print(data + " ");
		}
	}

	public static void sort(Comparable[] c) {
		for (int i = 0; i < c.length; i++) {
			Comparable min = c[i]; //    
			int no = i; //      
			for (int j = i; j < c.length; j++) {
				if (c[j].compareTo(min) < 0) {
					min = c[j];
					no = j;
				}
			}
			c[no] = c[i];
			c[i] = min;
		}
	}
}

 
 
ソートの挿入:
小さい左、大きい右
時間複雑度:O(n*n)
安定性あんていせい:安定性あんていせい
備考:ほとんどがソートされている場合
 
クイックソート:
紹介:高級バブルは、最初の値を中枢データとして選択し、左右同時に比較を開始し、1回のソート後に中枢データの左側が小数であることを保証し、右側が大数であり、最後に小数配列と大配列を再帰的にソートする.
時間複雑度:O(n*logn)
安定性あんていせい:不安定
備考:効率が良い
コード:http://baike.baidu.com/view/19016.htm
 

public class QuickSort {
	public static void sort(Comparable[] data, int low, int high) {
		//    ,               
		Comparable pivotKey = data[low];
		//        i,j;i     ,j     
		int i = low;
		int j = high;
		if (low < high) {
			//              
			while (i < j) {
				while (i < j && data[j].compareTo(pivotKey) > 0) {
					j--;
				}// end while
				if (i < j) {
					//             
					data[i] = data[j];
					i++;
				}// end if
				while (i < j && data[i].compareTo(pivotKey) < 0) {
					i++;
				}// end while
				if (i < j) {
					//             
					data[j] = data[i];
					j--;
				}// end if
			}// end while
			//            
			data[i] = pivotKey;
			//          
			sort(data, low, i - 1);
			//          
			sort(data, i + 1, high);
		}// end if
	}// end sort

	public static void main(String[] args) {
		//  JDK1.5    ,            
		// int,double             Comparable  
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c, 0, c.length - 1);
		for (Comparable data : c) {
			System.out.print(data + " ");
		}
	}
}