Java의 빠른 정렬

퀵 정렬의 원리

퀵 정렬은 버블 정렬을 개선한 것으로 하나씩 비교하므로 작은 값을 배치합니다. 정렬 목적을 달성하기 위해 한쪽 끝에는 큰 값이 있고 다른 쪽 끝에는 큰 값이 있습니다.

그리고 퀵 정렬은 먼저 임계값을 선택하고, 임계값보다 작은 값을 한쪽 끝에 두고, 그 값들을 ​한쪽 끝의 임계값보다 큰 값이 다른 쪽 끝에 배치됩니다. 앞 단락의 방법을 반복하면 임계값을 통과한 두 변을 나누어서 두 번 나눌 수 있는데... 데이터를 정렬하면 전체 퀵 정렬이 완료됩니다.

빠른 정렬 알고리즘

핵심 알고리즘:

//QuickSort
while(i < j) {
		while(num[j] > tmp && j > i)
			--j;
		while(num[i] <= tmp && i < j) {
			++i;
		}
		if(i < j) {
			t = num[i];
			num[i] = num[j];
			num[j] = t;
		}
	}
	num[left] = num[i];
	num[i] = tmp;

#🎜 🎜 #다음은 전체 QuickSort 프로그램입니다.

//QuickSort.java
public class QuickSort {
	public static void main(String[] args) {
		int[] num = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		System.out.print("Qriginal array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
		
		//QuickSort
		quicksort(num, 0, 9);
		
		System.out.print("Sorted array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}
	
	public static void quicksort(int[] num, int left, int right) {
		if(left > right)
			return;
		int tmp, i, j, t;
		tmp = num[left];
		i = left;
		j = right;
		while(i < j) {
			while(num[j] > tmp && j > i)
				--j;
			while(num[i] <= tmp && i < j) {
				++i;
			}
			if(i < j) {
				t = num[i];
				num[i] = num[j];
				num[j] = t;
			}
		}
		num[left] = num[i];
		num[i] = tmp;
		quicksort(num, left, i - 1);
		quicksort(num, i + 1, right);
	}
}

프로그램 출력은 아래와 같습니다.

Qriginal array is:10 9 8 7 6 5 4 3 2 1
Sorted array is:1 2 3 4 5 6 7 8 9 10

Quick Sort는 다른 정렬 방법보다 효율적이므로 빠릅니다. 정렬은 현재 사용할 수 있는 최고의 범용 정렬 방법입니다. QuickSort의 시간 복잡도는 O(nlogn)입니다.

위 내용은 Java의 빠른 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!