快速排序---java

快速排序---java

目录

思路

gitee地址：

代码 

---

思路

1. 找到数组中间的节点pivot
2. 从左边找比pivot大的数与其右边比pivot小的数交换
3. 然后pivot左边的数字在进行快速排序，右边也进行快速排序，最后就可以了。 

gitee地址：

快排https://gitee.com/ALi_L/javaDataStructurs.git

代码 

package DataStructures.sort;

import java.lang.reflect.Array;
import java.util.Arrays;


public class quickSort {
    public static void main(String[] args) {
//        int[] array = {1, 2, 3, 5, 4, -1};
        int[] array = {-9, 78, 0, 23, -567, 70};
        quick(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    
    public static void quick(int[] array, int left, int right) {
        //中间的数
        int pivot = array[(right + left) / 2];
        int temp = 0;
        //left和right是数组的边界，用来保证指针l，r不能越界
        int l = left;
        int r = right;

        while (l < r) {
            //找到最左边比pivot大的数
            while (array[l] < pivot) {
                l++;
            }
            //找到最右边比pivot小的数
            while (array[r] > pivot) {
                r--;
            }
            //如果左指针超过了右指针则不用交换，直接退出循环
            if (l >= r) {
                break;
            }
            //找到后交换两数的大小，但是前提是左指针要小于右指针
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            //如果一个指针到达了中间pivot的位置，则移动另一个指针，此时该指针指向pivot
            if (array[l] == pivot) {
                r--;
            }
            //当右指针到达中间pivot的位置时，移动左指针，此时该指针指向pivot
            if (array[r] == pivot) {
                l++;
            }

        }

        //当排序一次后，两个指针相等时说明两个指针都指向pivot。
        // 此时让左指针++，右指针--；[0,r]与[l,right]是除了pivot的两组
        if (l == r) {
            l++;
            r--;
        }
        //
        if (left < r) {
            quick(array, left, r);
        }
        if (l < right) {
            quick(array, l, right);
        }


    }

}