快速排序的原理
快速排序是对冒泡排序的一种改进，冒泡排序是通过一个个比较，从而将小的值放在一端，而大的值放在另外一端，从而达到排序的目的。
而快速排序，是先选定一个临界值，将比这临界值小的值放在一端，而比临界值大的值放在另外一端。重复上一段方法，可以把已经通过临界值分成的两边，再进行两次的分放……将其数据排序好，则整个快速排序就完成了。
快速排序的算法
核心算法：
//QuickSort
while(i < j) {
while(num[j] > tmp && j > i)
--j;
while(num[i] <= tmp && i < j) {
++i;
}
if(i < j) {
t = num[i];
num[i] = num[j];
num[j] = t;
}
}
num[left] = num[i];
num[i] = tmp;登录后复制下面是完整的QuickSort程序：
//QuickSort.java
public class QuickSort {
public static void main(String[] args) {
int[] num = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.print("Qriginal array is:");
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
System.out.println();
//QuickSort
quicksort(num, 0, 9);
System.out.print("Sorted array is:");
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
System.out.println();
}
public static void quicksort(int[] num, int left, int right) {
if(left > right)
return;
int tmp, i, j, t;
tmp = num[left];
i = left;
j = right;
while(i < j) {
while(num[j] > tmp && j > i)
--j;
while(num[i] <= tmp && i < j) {
++i;
}
if(i < j) {
t = num[i];
num[i] = num[j];
num[j] = t;
}
}
num[left] = num[i];
num[i] = tmp;
quicksort(num, left, i - 1);
quicksort(num, i + 1, right);
}
}登录后复制程序输出如下图所示：
Qriginal array is:10 9 8 7 6 5 4 3 2 1
Sorted array is:1 2 3 4 5 6 7 8 9 10
登录后复制快速排序效率相对其他排序方法较高，因此快速排序是现在最好的通用排序方法。QuickSort的时间复杂度为O(nlogn)。
以上就是Java中的快速排序的详细内容，更多请关注悠悠之家其它相关文章！
发表评论 取消回复