자바 기초 - 빠 른 정렬 알고리즘 자바 구현

빠 른 정렬 알고리즘 자바 구현
1 알고리즘 개념.빠 른 정렬 (Quicksort) 은 거품 정렬 에 대한 개선 입 니 다.C. A. R. Hoare 가 1962 년 에 제기 했다.2 알고리즘 사상.한 번 의 정렬 을 통 해 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 었 습 니 다. 그 중에서 일부분 의 모든 데 이 터 는 다른 부분의 모든 데이터 보다 작 습 니 다. 그 다음 에 이 방법 에 따라 이 두 부분의 데 이 터 를 각각 신속하게 정렬 하고 전체 정렬 과정 은 재 귀 하여 전체 데 이 터 를 질서 있 는 서열 로 바 꿀 수 있 습 니 다.3. 사고방식 을 실현 한다.① 첫 번 째 키워드 K 1 을 제어 문자 로 하여 [K 1, K 2,..., K n] 을 두 개의 서브 구역 으로 나 누 어 왼쪽 구역 의 모든 키 워드 를 K 1 보다 작 게 하고 오른쪽 구역 의 모든 키 워드 는 K 1 보다 크 며 마지막 으로 제어 글 자 는 두 개의 서브 구역 중간의 적당 한 위치 에 있다.자구 내 데이터 가 아직 무질서 한 상태 에 있다.② 왼쪽 구역 을 하나의 전체 로 하고 ① 의 절차 로 처리 하 며 오른쪽 구역 은 똑 같이 처리한다.(즉, 재 귀) ③ ① ② 단 계 를 반복 하여 왼쪽 구역 이 처 리 될 때 까지 한다.4 코드 구현 (재 귀 방식)

static void quicksort(int n[], int left, int right) {
	int dp;
	if (left < right) {
		dp = partition(n, left, right);
		quicksort(n, left, dp - 1);
		quicksort(n, dp + 1, right);
	}
}

static int partition(int n[], int left, int right) {
	int pivot = n[left];
	while (left < right) {
		while (left < right && n[right] >= pivot)
			right--;
		if (left < right)
			n[left++] = n[right];
		while (left < right && n[left] <= pivot)
			left++;
		if (left < right)
			n[right--] = n[left];
	}
	n[left] = pivot;
	return left;
}

5 코드 구현 (비 귀속 방식)

package sort.algorithm;
import java.util.Stack;
//          ，      stack
public class QuickSortNonRecursion {
 public static void main(String[] args) {
	 QuickSortNonRecursion qsnr = new QuickSortNonRecursion();
	 int[] array = {0, 2, 11, 121, 18, 99, 3, 5, 101, 22, 9, 100};
	 qsnr.quicksort(array);
	  for (int i : array) {
			System.out.print(i + "  ");
	  }
	}
			 
	public void quicksort(int[] array) {
		if (array == null || array.length == 1) return;
		//         
		Stack s = new Stack(); 
		//         
		s.push(0); 
		s.push(array.length - 1); 
		//       
		while (!s.empty()) { 
			int right = s.pop(); 
			int left = s.pop(); 
			//              ，     
			if (right <= left) continue; 
					 
			int i = partition(array, left, right); 
			if (left < i - 1) {
				s.push(left);
				s.push(i - 1);
			} 
			if (i + 1 < right) {
				s.push(i+1);
				s.push(right);
			}
		} 
	}
	//    ，    
	public int partition (int[] data, int first, int end)
	{
		int temp;
		int i=first,j=end;
		if(firsti&&data[j]>temp)j--;
				if(idata[i])i++;
				if(i