DESKTOP-7803S27_20200904-吴远亮

问题

如何利用快速排序对数组进行排序？

解决方法

基本思想：

1，将数组 、数组的最小的下标 low 和 最大下标 high 传递给排序方法

2、找一个基准 mid ， mid=array [( low + high )/2]

3, 利用基准将数组分成两半，并且使得在数组中 位于基准 左边的元素小于基准，位于基准右边的元素大于基准；

4、让 数组中位于基准 两边 的元素 ， 分别递归调用排序方法，直到数组 low>= high 时才能结束。

代码如下：

package quicksort;
import java.util.Arrays;
public class QuickSort1 {
    public void sort(int[] array, int low,int high) {
        int l=low;
        int h=high;
        if(low<high) {
            while(l<=h) { 
                int mid= array[(low+high)/2];
                while((l<high) && (array[l]<mid)) {
                    ++l;
                }
                while((h>low) && (array[h]>mid)) {
                    --h;
                }
                if(l<=h) {
                    int temp=array[l];
                    array[l]=array[h];
                    array[h]=temp;
                    ++l;
                    --h;
                }
            }
            if(l<high) {
                sort(array,l,high);
            }
            if(h>low) {
                sort(array,low,h);
            }
        }
    }
    public static void main(String[] args) {
        int[] array= {13,65,78,96,58,78,75,98,64,71};
        
        QuickSort1 qk=new QuickSort1();
        qk.sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

}

吐槽

考试加油！！！