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));
    }

}

吐槽

考试加油!!!

标签

© 2021 成都云创动力科技有限公司 蜀ICP备20006351号-1