java——快速排序基准位置的选取方法和优化
一、 快速排序基准位置的选取方法
1.固定位置法（就是选取的基准是固定的、一般是数组的第一个元素）
2.随机选取基准法
/**
* 快速排序，递归实现
* 时间复杂度：好：O(无序)(nlog2n),坏(有序)：O(n^2)
* 空间复杂度：
* 稳定性：不稳定
* (每次分割比较均匀的时候 效率较高
*/
public class LianXi {
public static int partion(int[] array,int low,int high) {//一趟快排
int tmp = array[low];
while(low < high) {
while(low < high && array[high] >= tmp) {
--high;
}
array[low] = array[high];
while(low < high && array[low] <= tmp) {
++low;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void Quick(int[] array,int start,int end) {
Random in = new Random();
int pwd = in.nextInt(end-start+1)+start;//产生一个随机数
swap(array,start,pwd);
int par = partion(array,start,end);
if(par > start) {
Quick(array,start,par+1);
}
if(par < end) {
Quick(array,par-1,end);
}
}
public static void swap(int[] array,int start,int end) {//将产生的随机下标与start下标交换，而这个新的array[start]会为基准，就达到了，随机选取基准的目的
int tmp = array[start];
array[start] = array[end];
array[end] = tmp;
}
public static void QuickSort(int[] array) {
Quick(array,0,array.length-1);
}
public static void main(String[] args) {
int[] array = {20,1,9,56,25,32,87,45,12,69,54,19,98,51,25};
QuickSort(array);
System.out.println(Arrays.toString(array));
}
3、三分取基准
这个方法也就是把数组的第一个最后一个和最中间的元素拿出来比较一下，把三者中最大的放最后面，最小的放最前面，剩下那个元素放中间。然后在用递归的方式比较排序：
/**
* 1.三分取基准
*/
public class Kuaisuyouhua1 {
public static void Quick(int[] array,int start,int end) {
int par = partion(array,start,end);
if(par > start) {
Quick(array,start,par-1);
}
if(par < end) {
Quick(array,par+1,end);
}
}
public static int partion(int[] array,int low,int high) {//一趟快排
int tmp = array[low];
while(low < high) {
while(low < high && array[high] >= tmp) {
--high;
}
array[low] = array[high];
while(low < high && array[low] <= tmp) {
++low;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void new_Sort(int[] array,int start,int end) {
int mid = start+(end-start)>>>1;
if(array[start] > array[end]) {//目标 array[end] >= array[start]
swap(array,start,end);
}
if(array[start] > array[mid]) {// mid > start
swap(array,start,mid);
}
if(array[end] < array[mid]) {//end< mid
swap(array,end,mid);
}
System.out.println("经过new_Sort()后数组"+Arrays.toString(array));
Quick(array,0,array.length-1);
}
public static void QuickSort(int[] array) {
new_Sort(array,0,array.length-1);
}
public static void swap(int [] array ,int start,int end)
{
int temp = array[start];
array[start] = array[end];
array[end] = temp;
}
public static void main(String[] args) {
int[] array = {20,23,98,54,12,15,0,19,3,46,78,59,84};
System.out.println("原数组"+Arrays.toString(array));
QuickSort(array);
System.out.println("排序后数组："+Arrays.toString(array));
}
}
运行结果：
原数组[20, 23, 98, 54, 12, 15, 0, 19, 3, 46, 78, 59, 84]
经过new_Sort()后数组[0, 23, 98, 54, 12, 15, 20, 19, 3, 46, 78, 59, 84]
排序后数组：[0, 3, 12, 15, 19, 20, 23, 46, 54, 59, 78, 84, 98]
二、优化：
1、当待排序数组当中数据比较少的时候，用直插
public class LianXi{
public static int partion(int[] array,int low,int high) {//一趟快排
int tmp = array[low];
while(low < high) {
while(low < high && array[high] >= tmp) {
--high;
}
array[low] = array[high];
while(low < high && array[low] <= tmp) {
++low;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void Quick(int[] array,int start,int end) {
if(end - start+1 < 100) {
System.out.println("直插");//用于验证用的是直插，进入了if语句
insert_Sort(array);
}else {
System.out.println("快排");//用于验证用的是快排，没有进入if语句
int par = partion(array,start,end);
if(par > start) {
Quick(array,start,par-1);
}
if(par < end) {
Quick(array,par+1,end);
}
}
}
private static void insert_Sort(int[] array) {
int tmp = 0;
int j = 0;
for(int i = 1;i < array.length;i++) {
tmp=array[i];
for(j = i-1;j >= 0;j--) {
if(array[j] > tmp) {
array[j+1] = array[j];//每次排序前面已经有序，找到的一个比tmp小的交换
}
else {
break;
}
}
array[j+1] = tmp;//比tmp大的，放到当前位置+1
}
}
public static void QuickSort(int[] array) {
Quick(array,0,array.length-1);
}
public static void main(String[] args) {
int[] array = {20,1,9,56,25,32,87,45,12,69,54,19,98,51,25};
QuickSort(array);
System.out.println(Arrays.toString(array));
}
}
2、聚集相同元素法(基准一样的元素),减少递归的次数
当i和j遍历完后，也就把相同元素聚集完了，
这时，下一次基准的左右两边再次递归排序时，就不是这次基准位置的两边了，而是left的左边和right的右边。
public class LianXi{
public static int partion(int[] array,int low,int high) {//一趟快排
int tmp = array[low];
while(low < high) {
while(low < high && array[high] >= tmp) {
--high;
}
array[low] = array[high];
while(low < high && array[low] <= tmp) {
++low;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void Quick(int[] array,int start,int end) {
int par = partion(array,start,end);
int left = par-1;
int right = par+1;
int[] brray = focus(array,start,end,par);
left = brray[0];
right = brray[1];
if(par > start+1) {
Quick(array,start,left);
}
if(par < end-1) {
Quick(array,right,end);
}
}
public static int[] focus(int[] array, int start, int end, int par) {
//查找的范围
int left = par-1;
int right = par+1;
//交换的指引变量
int parLeft = par-1;
int parRight = par+1;
//左边找
for (int i = left; i >=start; i--) {
if(array[i] == array[par])
{
if(i!=parLeft)
{
swap(array, parLeft, i);
parLeft--;
}
else
{
parLeft--;
}
}
}
//右边找
for (int i = right; i <=end; i++) {
if(array[i] == array[par])
{
if(i!=parRight)
{
swap(array, parRight, i);
parRight++;
}
else
{
parRight++;
}
}
}
int [] focus = {parLeft,parRight};
return focus;
}
public static void swap(int [] array ,int start,int end)
{
int temp = array[start];
array[start] = array[end];
array[end] = temp;
}
public static void QuickSort(int[] array) {
Quick(array,0,array.length-1);
}
public static void main(String[] args) {
int[] array = {20,20,20,56,25,32,87,45,12,69,54,20,98,51,25};
QuickSort(array);
System.out.println(Arrays.toString(array));
}
运行结果：
[12, 20, 20, 20, 20, 25, 25, 32, 45, 51, 54, 56, 69, 87, 98]