자바에서 빠른 정렬을 구현하는 방법

다음 칼럼에서는 java 입문 학습 칼럼에서 Java로 빠른 정렬을 구현하는 방법을 소개하겠습니다. 이 알고리즘 정렬이 여러분에게 도움이 되기를 바랍니다!

빠른 정렬의 시간 복잡도는 고정되어 있지 않습니다. 최악의 경우(원래 역정렬된 배열에서 첫 번째 요소를 기본 요소로 선택) 속도가 상대적으로 느려서 O(n^2)(및 선택)에 도달합니다. 정렬은 효율적이지만 이상적인 상황에서는 시간 복잡도가 O(nlogn)인 경우입니다.

빠른 정렬 구현의 핵심은 먼저 배열에서 숫자를 선택한 다음 배열의 숫자를 두 부분으로 나누는 것입니다. 선택한 숫자보다 작은 숫자는 배열의 왼쪽으로 이동하고 그보다 큰 숫자는 배열의 왼쪽으로 이동됩니다. 선택한 숫자가 배열의 왼쪽으로 이동됩니다. 이는 분열과 정복의 사상을 반영합니다.

이 함수를 구현해 보겠습니다.

int Partition(int data[],int length,int start,int end)
{
	if(data == nullptr || length <= 0 || start < 0 || end >=length)
		throw new std::exception("Invalid Parameters");
	int index = RandomInRange(start,end);
	Swap(&data[index],&data[end]);
	int small = start - 1;
	for(index = start; index < end; index++)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				Swap(&data[index],&data[small]);
		}
	}
	++small;
	Swap(&data[small],&data[end]);
	return small;
}
int RandomInRange(int min, int max)
{
	int random = rand()%(max - min +1) +min;
	return random;
}
int Swap(int *num1, int *num2)
{
	int temp = *num1;
	*num1 = num2;
	*num2 = temp;
}

위 코드의 RandomInRange 함수는 시작과 끝 사이의 난수를 생성하는 데 사용되고, Swap 함수는 두 숫자를 교환하는 데 사용됩니다.

아래에서는 재귀를 사용하여 빠른 정렬 코드를 구현합니다.

void QuickSort(int data[], int length, int start, int end)
{
	if(start == end)
		return;
	int index = Partition(data, length, start, end);
	if(index > start)
		QuickSort(data, length, start, index -1);
	if(index < end)
		QuickSort(data, length, index + 1, end);
}

위 내용은 자바에서 빠른 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!