빠른 순서의 에세이

먼저 코드를 올리세요. 다음은 인터넷 코드를 결합하여 수정한 빠른 정렬의 demo입니다.
먼저 "정렬"의 허기류를 만들자.

public abstract class AbstractSorter<E extends Comparable<E>> {
	
	public abstract void sort(E[] array,int low ,int high);
	
	public final void sort(E[] array)
    {
        sort(array,0,array.length-1);
    }
	/**
        *     */
	public final void swap(E[] array, int i, int j){
		E tempE = array[i];
		array[i] = array[j];
		array[j] = tempE;
	}
}

빠른 정렬 상속 추가:

public class QuickSorter<E extends Comparable<E>> extends AbstractSorter<E> {

	public QuickSorter() {
		// TODO Auto-generated constructor stub
	}

	@Override
	public void sort(E[] array, int low, int high) {
		if(low < high){
			int pivot = partition(array, low, high);
			this.sort(array, low, pivot-1);
			this.sort(array, pivot+1, high);
		}

	}

	private int partition(E[] array, int low, int high) {
		E pivotContent = array[high];
		int itrace = low;
		for(int j=low;j<high;++j){
			if(array[j].compareTo(pivotContent)<0){
				swap(array, itrace++, j);
			}
		}
		swap(array, itrace, high);
		return itrace;
	}
}

그래, 사실 나는 이전에 빠른 정렬이 무엇인지 잘 몰랐는데, 지금은 코드를 연구하면 비교적 분명해진다.
빠른 정렬이란 대기열에서 원소를 지점으로 선택하여 지점을 한 위치에 놓는 것이다. 이 위치의 왼쪽은 모두 그것보다 작은 원소이고 오른쪽은 모두 그것보다 큰 원소이다. 즉, 지점과 좌우 두 단락으로 말하자면 대기열은 이미 정렬된 것이다.그리고 좌우 두 단락의 귀속을 신속하게 정렬하여 마지막에 질서정연한 대열을 얻었다.
빠른 정렬의 관건은 선택한 지점 요소를 자기가 있어야 할 위치에 정확하게 넣는 것이다.상술한 실현에서 선택한 것은 이 세그먼트의 최대 인덱스 요소가 지점이다.그리고 왼쪽에서 오른쪽으로 그룹을 훑어보고 지점 원소보다 큰 것을 발견하면 건너뛰고 지점 원소보다 작은 것을 발견하면 이 원소와'가능한 왼쪽'의 untouched 원소를 대조한다.이른바 untouched란 이전에 건너뛴 원소, 즉 지점 원소보다 큰 원소, 아니면 바뀐 원소, 필연적으로 지점 원소보다 큰 원소이다.이 모든 것은 itrace 변수 즉 교환 진도를 나타내는 변수에 의해 제어되고 매번 교환이 발생할 때마다 한 번씩 증가한다.모든 원소가 check가 지나간 후에 itrace의 현재 위치의 원소와 최대 인덱스의 원소를 바꾸십시오.itrace, 즉 지점 요소의 인덱스이자 마지막 질서정연한 인덱스로 되돌아와 정렬을 완성했습니다.다음은 itrace 좌우 두 단락에 대해 상기 정렬 과정을 각각 수행하는 것입니다~
설명: 위에서 말한 바와 같이itrace 변수는 교환 진도를 나타내는 변수로 매번 교환이 발생할 때마다 한 번씩 증가한다.실제로 itrace의 의미는 왼쪽의 원소는 모두 지점 원소보다 작기 때문에 한 번의 수조를 훑어보았을 때 모든 지점보다 작은 원소는 itrace가 가리키는 색인 왼쪽으로 운집되었다는 것이다.마지막으로 itrace 인덱스에 있는 현재 원소(틀림없이 지점보다 큰 원소)와 지점을 교환하면 지점 원소는 적절하게 배치되고 모든 왼쪽 원소는 그것보다 작으며 모든 오른쪽 원소는 그것보다 크다.
마지막으로 빠른 정렬의 시간 복잡도는 O(nlogn)이고 최악의 경우(본 예에서 선택한 지점이 마지막 요소일 경우 역순으로 최악(미검증))는 O(n^2)이다.
테스트용main 함수는 다음과 같습니다.

/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] array = {12,15,7,2,8,10};
		AbstractSorter<Integer> sorter = new QuickSorter<Integer>();
		sorter.sort(array);
		
		for(int i = 0;i<array.length;i++){
			System.out.print(array[i].intValue()+" ");
		}
	}