package com.yg.sort;/*
@author GeQiLin
@date 2020/2/26 21:00
*/
import java.util.Arrays;
public class QuickSort {
private static int max = 15;
private static int arr[];
public static void main(String[] args) {
setArr();
System.out.println("排序前： " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后： " + Arrays.toString(arr));
}
//构建数组大小和值
public static void setArr() {
arr = new int[max];
for (int i = 0; i < max; i++) {
arr[i] = (int) (Math.random() * max);
}
}
//快排
/*
将第一个数设为基准
使用两个指针r,l分别从后往前，和从前往后遍历数组
r找小于基准的数，然后给arr【l】
l找大于基准的数，找到后给arr[r]
* */
public static void quick_sort(int s[], int l, int r) {
if (l < r) {
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j) {
while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j) {
s[i] = s[j];
i++;
}
while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j) {
s[j] = s[i];
j--;
}
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
//快排
/*
将第中间的数设为基准
使用两个指针r,l分别从后往前，和从前往后遍历数组
r找小于基准的数，l找大于基准的数
然后交换arr[r]和arr[l]
* */
public static void quickSort(int[] arr, int left, int right) {
//这个if用于结束分治
if (left < right) {
int r = right;
int l = left;
int middle = arr[(r+l)/2];
int tem=0;
while (l < r) {
while (l < r && arr[r] >= middle)
r--;
while (l < r && arr[l] < middle)
l++;
// 交换
if(l<r){
tem= arr[l];
arr[l]=arr[r];
arr[r]=tem ;
}
}
arr[l] = middle;
quickSort(arr, left, l - 1);
quickSort(arr, l + 1, right);
}
}
}
3.将最后一个数作为基准排序
public class QuickSort {
public static void main(String[] args) {
int []arr={1,3,5,6,3,45,6,7,8,2,5,9};
QuickSort.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static int[]getPartition(int[] arr, int left, int right, int p){
int index=left;
int l=left-1;
int r=right+1;
while(index<r){
if(arr[index]<p){
QuickSort.swap(arr,++l,index++);
}else if(arr[index]>p){
QuickSort.swap(arr,--r,index);
}else{
index++;
}
}
return new int[]{l+1,r-1};
}
private static void sort(int[] arr, int l, int r){
if(l<r){
//p[0]记录等于目标值的最小下标，p[1]记录等于目标值的最大下标
//如12334 当目标值p为3 时 p[0]=2,p[1]=3
int[] p = QuickSort.getPartition(arr, l, r, arr[r]);
//遍历小于目标值部分
QuickSort.sort(arr,l,p[0]-1);
//遍历大于目标值部分
QuickSort.sort(arr,p[1]+1,r);
}
}
private static void swap(int[] arr, int i, int j){
int temp;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
4,随机选取基数快排解决有序集合选最后一个元素效率低问题
public class QuickSort {
public static void main(String[] args) {
int []arr={1,3,5,6,3,45,6,7,8,2,5,9};
QuickSort.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static int[]getPartition(int[] arr, int left, int right, int p){
int index=left;
int l=left-1;
int r=right+1;
while(index<r){
if(arr[index]<p){
QuickSort.swap(arr,++l,index++);
}else if(arr[index]>p){
QuickSort.swap(arr,--r,index);
}else{
index++;
}
}
return new int[]{l+1,r-1};
}
private static void sort(int[] arr, int l, int r){
if(l<r){
//随机选取参考值避免有序情况排序效率低
QuickSort.swap(arr,l+(int)(Math.random()*(r-l+1)),r);
//p[0]记录等于目标值的最小下标，p[1]记录等于目标值的最大下标
//如12334 当目标值p为3 时 p[0]=2,p[1]=3
int[] p = QuickSort.getPartition(arr, l, r, arr[r]);
//遍历小于目标值部分
QuickSort.sort(arr,l,p[0]-1);
//遍历大于目标值部分
QuickSort.sort(arr,p[1]+1,r);
}
}
private static void swap(int[] arr, int i, int j){
int temp;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
