快速排序
快速排序是对冒泡排序的一种改进, 它是不稳定的。由C. A. R. Hoare在1962年提出的一种划分交换排序,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数,它的最好情况为O(nlogn),最坏情况为O(n^2),平均时间复杂度为O(nlogn)。
基本思想
选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以达到全部数据变成有序。
代码实现
package com.sorttext;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 4, 9, 3};
chage(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 快速排序
* @param arr 数组
* @param left 左指针
* @param right 右指针
*/
public static void chage(int[] arr, int left, int right) {
if (left > right) {//
return;
}
int i = left;
int j = right;
int key = arr[left];
int temp = 0;
while (i != j) {
while (arr[j] >= key && i < j) {
j--;
}
while (arr[i] <= key && i < j) {
i++;
}
//走到这说明 两个数字都找到了 有可能是两个数字 一大一小交换
//也有可能是一个数字 i与j重合了 自身交换位置不变
//跳出循环以后 让当前重合坐标与基点 做交换
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//走到这说明 j与i重合 让当前值与基点 做交换
arr[left] = arr[i];
arr[i] = key;
//在分别 做左右递归
chage(arr, left, i - 1);
chage(arr, j + 1, right);//注意此处最后一个参数不能用length-1
}
}