データ構造(4)の高速ソート

クイックソート

快速並べ替え原理

クイックソート(Quick Sort)の基本的な考え方は、1つの順序で記録を独立した2つの部分に分割し、そのうちの一部の記録のキーワードは、他の部分の記録のキーワードよりも小さい場合、この2つの部分の記録を連続的に並べ替えて、順序付けの目的を達成することである.

メインプログラム

package Sort;

public class QuickSort {
	
	private void Qsort(int[] list, int low, int high){
		int privot;
		if(low < high) {
			print(list);
			/*     privot*/
			privot = Partition(list, low, high);
			/*        */
			Qsort(list, low, privot-1);
			/*        */
			Qsort(list, privot+1, high);			
		}
	}
	
	private int Partition(int[] list, int low, int high){
		/*             */
		int privotkey = list[low];
		while (low < high){
			while (low < high && list[high] > privotkey)
				high--;			
			/*               */
			swap(list, low, high);
			while (low < high && list[low] < privotkey)
				low++;
			/*               */
			swap(list, low, high);			
		}
		/*         */
		return low;
	}
	
	private void swap(int [] list,int j, int i){
		int temp;
		temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}	
	
	private void print(int[] data) {
		System.out.println("  list    ：");
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] list = {50,40,80,30,60,70,10,90,20};
		QuickSort qs = new QuickSort();
		qs.Qsort(list, 0, list.length-1);
		qs.print(list);
	}
}

　　

Qsort()解析

	private void Qsort(int[] list, int low, int high){
		int privot;
		if(low < high) {
			print(list);
			/*     privot*/
			privot = Partition(list, low, high);
			/*        */
			Qsort(list, low, privot-1);
			/*        */
			Qsort(list, privot+1, high);			
		}
	}

　　

Parttition()解析

	private int Partition(int[] list, int low, int high){
		/*             */
		int privotkey = list[low];
		while (low < high){
			while (low < high && list[high] > privotkey)
				high--;			
			/*               */
			swap(list, low, high);
			while (low < high && list[low] < privotkey)
				low++;
			/*               */
			swap(list, low, high);			
		}
		/*         */
		return low;
	}

　　

出力結果

  list    ：
50	40	80	30	60	70	10	90	20	
  list    ：
20	40	10	30	50	70	60	90	80	
  list    ：
10	20	40	30	50	70	60	90	80	
  list    ：
10	20	30	40	50	70	60	90	80	
  list    ：
10	20	30	40	50	60	70	90	80	
  list    ：
10	20	30	40	50	60	70	80	90	

　　

時間複雑度解析

最適な場合、高速ソートアルゴリズムの時間複雑度はO(nlogn)であり、空間複雑度もO(nlogn)である.