How to implement quick sort in java

The following column java introductory learning will introduce how to implement quick sorting in java. I hope this algorithm sorting can help everyone!

The time complexity of quick sort is not fixed. If in the worst case (selecting the first element as the base element in an originally reverse-sorted array) the speed is relatively slow, reaching O(n^2 ) (an efficiency similar to selection sorting), but if the time complexity is O(nlogn) under ideal circumstances.

The key to implementing quick sorting is to first select a number in the array, and then divide the numbers in the array into two parts. The number smaller than the selected number is moved to the left of the array, and the number smaller than the selected number is moved to the left of the array. The larger number is moved to the right of the array. This reflects the idea of ​​divide and conquer.

Let’s implement this function:

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;
}

The function RandomInRange in the above code is used to generate a random number between start and end, and the function Swap is used to exchange Two numbers.

Below we use recursion to implement quick sorting code:

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);
}

The above is the detailed content of How to implement quick sort in java. For more information, please follow other related articles on the PHP Chinese website!