快速排序
要求算法实现二背下来
时间复杂度:O(nlogn)
- 快排的性能
快排在排序算法中性能最好,数据越大排序最优,但在最坏的极端情况下会退化成O(n²)
。若前提已知待处理的数据会出现极端的情况下,可以选择比较稳定的归并排序。
最坏的情况:每次所取的基准都是最小的
算法实现:
public void test(){
int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };
//记得传入右边边界要减一
sort(n,0,n.length-1);
for (int m : n) {
System.out.println(m+"\t");
}
}
public void sort(int[] n,int left,int right){
//制定递归出口
if (left<right) {
int index = quicksort(n, left, right);
//确定好下标,为第二次递归做准备
sort(n, left, index - 1);
sort(n, index + 1, right);
}
}
public int quicksort(int[] n,int left,int right){
//将随机一个数与最左边的一个数交换
swap(n,new Random().nextInt(right-left+1)+left,left);
int temp = n[left];
int tempIndex = left;
while (right>left){
while (temp<=n[right] && right>left){
right--;
}
while (temp>=n[left] && right>left){
left++;
}
//该交换为将大于基数的数移至基数左边
//小于基数的数移至基数右边
swap(n,left,right);
}
//该交换为基准与确定好的位置交换
swap(n,tempIndex,left);
//回传的是确定好位置的基准元素下标
return left;
}
public void swap(int[] n,int i,int j){
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}
写法二:
public class QuickSort {
private int[] array;
public QuickSort(int[] array) {
this.array = array;
}
public void sort() {
quickSort(array, 0, array.length - 1);
}
public void print() {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/**
* 递归排序
* @param src
* @param begin
* @param end
*/
private void quickSort(int[] src, int begin, int end) {
if (begin < end) {
int key = src[begin];
int i = begin;
int j = end;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i] = src[j];
i++;
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j] = src[i];
j--;
}
}
src[i] = key;
quickSort(src, begin, i - 1);
quickSort(src, i + 1, end);
}
}
}