快速排序, 顾名思义, 排序速度很快, 也是面试常常被问到的排序算法之一.
快速排序关键在于一个轴, 让其他的数字和这个轴的值相比较, 如果小于等于这个轴把数字放到轴的左边, 否则放到右边. 这样你会发现, 这个轴现在在的位置就是他应该在的位置了.
那么第一次循环后就变成这个样子, 然后分别指定两边的数组的轴, 分别对两个数组进行同样的步骤即可. 其实从某种角度来讲, 他和选择排序类似, 选择排序是选择一个数字比较找到最小的值往前放, 而快速排序是指定一个数字, 找到他的位置. 来看代码怎么实现吧
- package test;
- /**
- * <p></p>
- *
- * @author zy 刘会发
- * @version 1.0
- * @since 2020/4/16
- */
- public class QuickSort {
- public static void main(String[] args) {
- int arr[] = new int[]{5, 7, 3, 1, 6, 9, 4, 0};
- sort(arr, 0, arr.length - 1);
- print(arr);
- }
- public static void sort(int arr[], int leftBound, int rightBound) {
- // 因为这里要用到递归, 所以必须给他一个出口
- if (leftBound>= rightBound) return;// 这里左边界应该永远小于右边界, 否则直接返回.
- int compare = compare(arr, leftBound, rightBound);// 这个时候已经将数组分成两个部分了, 而返回值也就是分界 (轴), 因为轴在这个方法调用的结束就已经确定了他的位置, 所以不再需要排序了
- // 排左边
- sort(arr, leftBound, compare - 1);
- // 排右边
- sort(arr, compare + 1, rightBound);
- }
- public static int compare(int arr[], int leftBound, int rightBound) {
- int axis = arr[rightBound];// 轴的值, 定义左右边的的边界值就是轴
- int left = leftBound;// 左只针的位置
- int right = rightBound - 1;// 右指针的位置
- while (left <= right) {// 只要左指针小于有指针就一直查找
- while (left <= right && arr[left] <= axis) left++;// 左指针的开始寻找一个比轴大的数字
- while (left <= right && arr[right]> axis) right--;// 右指针开始寻找一个比轴小的数字
- if (left < right)// 如果左指针小于右指针交换
- swap(arr, left, right);// 如果找到了就交换位置
- }
- // 然后把轴和左指针位置交换
- swap(arr, rightBound, left);
- // 这个时候, 左指针指的位置就是轴的位置, 将他返回.
- return left;
- }
- public static void swap(int arr[], int on, int off) {
- int temp = arr[on];
- arr[on] = arr[off];
- arr[off] = temp;
- }
- public static void print(int arr[]) {
- for (int i = 0; i < arr.length; i++) {
- System.out.printf("%d,", arr[i]);
- }
- }
- }
上边的代码是以有边界作为轴, 当然轴的位置是你自己定的, 不一定非得是右边界.
来源: http://www.bubuko.com/infodetail-3509104.html