java中如何實作快速排序

以下由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用來產生一個在start和end之間的隨機數，函數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);
}

以上是java中如何實作快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！