快速排序
2018-04-10 本文已影响0人
从0到1的小姐姐
对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
| some | some |
|---|---|
| 思想 | 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 |
| 时间复杂度 | 平均情况O(Nlog2N),最坏情况O(N2)，最好情况O(Nlog2N) |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
code
public class QuickSort {
public static void main(String[] args) {
int[] p = { 34, 21, 54, 18, 23, 76, 38, 98, 45, 33, 27, 51, 11, 20, 79,
30, 89, 41 };
QuickSort Sort = new QuickSort();
long start = System.currentTimeMillis();
System.out.println("排序前为：");
Sort.show(p);
System.out.println();
Sort.quicksort(p, 0, p.length - 1);// 快速排序
System.out.println("排序后为：");
Sort.show(p);
System.out.println();
System.out.println("所用时间：" + (System.currentTimeMillis() - start));
}
public static void quicksort(int[] data, int start, int end) {
// 设置关键数据key为要排序数组的第一个元素
// 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
int key = data[start];
// 设置数组左边的索引，往右移动比key大的数
int i = start;
// 设置数组右边的索引，往左移动比key小的数
int j = end;
// 如果左边索引比右边索引小，则还有数据没有排序
while (i < j) { //从后往前，找比key小的值，找到就赋给i
while (data[j] > key && j > i) {
j--;
}
data[i] = data[j];
while (data[i] < key && i < j) { //从前往后，找比key大的值，找到就赋给j
i++;
}
data[j] = data[i];
}
// 此时 i==j
data[i] = key; //调整key值的位置，此时i已经变化了
// 递归调用
if (i - 1 > start) { //i是分界线
// 递归调用，把key前面的完成排序
quicksort(data, start, i - 1);
}
if (i + 1 < end) {
// 递归调用，把key后面的完成排序
quicksort(data, i + 1, end);
}
}
public void show(int[] p){
for (int k:p){
System.out.print(" "+k);
}
}
}
