Javaによる高速ソートアルゴリズム

高速ソートはソートアルゴリズムの中で最も効率的なもので、再帰的な原理を利用して、すべてのデータがソートされるまで配列を無制限に2つの部分に分けます.
高速ソートはバブルソートの改良である.その基本思想は、1回のソートによってソートするデータを独立した2つの部分に分割することであり、その一部のすべてのデータは他の部分のすべてのデータよりも小さくなり、この方法でこの2つの部分のデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行うことができ、データ全体が秩序化されたシーケンスになることを達成することができる.
ソートする配列がA[1]......A[N-1]の場合、まず任意のデータ(通常は最初のデータを選択)を中間データとして選択し、次にそれより小さいすべての数をその前に配置し、それより大きいすべての数をその後ろに配置する.このプロセスを1つの高速ソートと呼ぶ.1つの高速ソートのアルゴリズムは以下の通りである.
(1)2つの変数i,jを設定し,ソート開始時:i=1,j=N–1とする.
(2)最初の配列要素を中間データとしてprivot,すなわちpivot=A[0]に付与する.
(3)jから前方探索を開始し,すなわち後から前方探索を開始し(j−),X未満の最初の値を見つける.
(4)iから後方探索を開始し、すなわち、前から後方探索(i++)を開始し、Xより大きい最初の値を見つけ、前のステップで見つけた数字と交換する.
(5)i>=jになるまで3,4ステップ目を繰り返す.
(6)そしてjが存在する数字をpivotと交換する.
(7)最後にj以前の配列とjから最後の配列を並べ替え,再帰的な高速ソートを行う.
 
以下に、このトピックのコード実装を示します.

  1 package com.fhcq.quicksort;
  2 
  3 public class QuickSort {
  4 
  5 	public static void main(String[] args) {
  6 		// TODO Auto-generated method stub
  7 
  8 		int[] a = new int[] { 5, 9, 8, 4, 7, 3, 6, 2 }; //    
  9 		print(a); //       
 10 		sort(a, 0, a.length-1); //  
 11 		print(a); //        
 12 	}
 13 
 14 	//    
 15 	private static void print(int[] before) {
 16 		// TODO Auto-generated method stub
 17 		for (int i = 0; i < before.length; i++) { //  
 18 			System.out.print(before[i] + ""); //  ，     
 19 		}
 20 		System.out.println(); //  
 21 	}
 22 
 23 	//    
 24 	 static void sort(int[] a, int low, int high) {
 25 		// TODO Auto-generated method stub
 26 		if(low >= high){ //low     high,     
 27 			return;
 28 		}
 29 		if((high - low) == 1){ //        ，     
 30 			if(a[0] > a[1]){
 31 				swap(a, 0, 1);
 32 				return;
 33 			}
 34 		}
 35 		int pivot = a[low]; //          
 36 		//         ，  2     ，       
 37 		int left = low + 1;
 38 		int right = high; //         
 39 		while(left < right){ //    
 40 			//      
 41 			while(left < right && left <= high){ //           
 42 				if(a[left] > pivot){ //        
 43 					break;
 44 				}
 45 				left++; //         
 46 			}
 47 			//      
 48 			while(left <= right && right > low){ //           
 49 				if(a[right] <= pivot){ //        
 50 					break;
 51 				}
 52 				right--; //        
 53 			}
 54 			if(left < right){ //      ，     
 55 				swap(a,right,left);
 56 			}
 57 
 58 		swap(a,low,right); //      
 59 		sort(a,low,right); //       
 60 		sort(a,right+1,high); //      
 61 		}
 62 	}
 63 
 64 	 //    
 65 	private static void swap(int[] array, int i, int j) {
 66 		// TODO Auto-generated method stub
 67 
 68 		int temp;
 69 		temp = array[i];
 70 		array[i] = array[j];
 71 		array[j] = temp;
 72 	}
 73 
 74 }
 75 

転載先:https://www.cnblogs.com/justlove/p/6985220.html