排序原理：
1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
排序过程:
例::{6, 1, 2, 7, 9, 3, 4, 5, 8}
切分原理：
把一个数组切分成两个子数组的基本思想：
1.找一个基准值，用两个指针分别指向数组的头部和尾部；
2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
package com.sort;
/*--------------
* Author:Real_Q
* Date:2021-01-09
* Time:11:53
* Description:快速排序
---------------*/
public class QuickSort {
//定义排序函数
public static void quickSort(int[] array) {
int low = 0;
int high = array.length - 1;
quickSort(array, low, high);
}
//重载排序函数
public static void quickSort(int[] array, int low, int high) {
if (low >= high) {
return;
}
int index = partition(array, low, high);
quickSort(array, low, index - 1);
quickSort(array, index + 1, high);
}
//核心函数 获取基准值的索引并且返回(基准值从首元素开始找,找到合适的为返回索引)
public static int partition(int[] array, int low, int high) {
//基准值
int key = array[low];
//指向尾部
int left = low;
//指向头部
int right = high + 1;
while (true) {
//2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
while (less(key, array[--right])) {
if (right <= low) {
break;
}
}
//3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
while (less(array[++left], key)) {
if (left >= high) {
break;
}
}
//4.交换当前左边指针位置和右边指针位置的元素；
if (left >= right) {//left和right相遇,left == right,遍历完了 跳出循环
break;
} else {//符合条件 交换eft和right索引值
exchange(array, left, right);
}
}
//把key与right处的索引值交换,并且返回索引
exchange(array, low, right);
return right;
}
//比较两个元素的大小,返回比较结果
public static boolean less(int a, int b) {
return ((a - b) < 0);
}
//交换数组中的两个元素
public static void exchange(int[] array, int index1, int index2) {
int temp;
temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
测试类:
package com.testsort;
import java.util.Arrays;
import static com.sort.QuickSort.quickSort;
/*--------------
* Author:Real_Q
* Date:2021-01-09
* Time:14:36
* Description:
---------------*/
public class TestQuick {
public static void main(String[] args) {
//int[] array = {8,4,5,7,1,3,6,2};
int[] array = {6, 1, 2, 7, 9, 3, 4, 5, 8};
quickSort(array);
System.out.println(Arrays.toString(array));
}
}