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中實現快速排序的方法就分享到這里了，希望以上內容可以對大家有一定的參考價值，可以學以致用。如果喜歡本篇文章，不妨把它分享出去讓更多的人看到。