java中如何实现快速排序

Java  /  管理员 发布于 8年前   199

下面由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中如何实现快速排序的详细内容，更多请关注其它相关文章！