快速排序算法(java实现)-蒲公英云

快速排序算法(java实现)

Bertha 。 2022-03-01 16:20 282阅读 0赞

一.思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据都要小,然后再用递归方法对着两部分分别进行快速排序,当每一部分不能再细分时完成排序.

二,解释

初始数组

初始数组

下标	0	1	2	3	4	5	6	7
值	6	4	7	9	2	8	1	10

l = 0, h = 7, k = 6

2.一趟排序(对于每一趟排序都分为两部分,先是从右边找比自己小的,后是从左边找比自己大的)

一趟排序

下标	0	1	2	3	4	5	6	7
值	1	4	7	9	2	8	6	10

I = 0, h = 6, k = 6

一趟排序

下标	0	1	2	3	4	5	6	7
值	1	4	6	9	2	8	7	10

I = 2, h = 6, k = 6

注意:只要l < h,排序还要进行下去,直到不满足循环条件为止,此时一趟排序完成,然后对左右两部分递归上述操作即可

三.代码

package 快速排序;
public class FastSort {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int []a = {6, 4, 7, 9, 2, 8, 1, 10};
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
        sort(a, 0, a.length-1);
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");
        }
    }
    public static void sort(int []a, int low, int high){
        int l = low;
        int h = high;
        int k = a[low];
        while(l < h){
            while(l < h && a[h] >= k){
                h--;
            }
            if(l < h){
                int temp = a[h];
                a[h] = a[l];
                a[l] = temp;
                l++;
            }
            while(l < h && a[l] <= k){
                l++;
            }
            if(l < h){
                int temp = a[l];
                a[l] = a[h];
                a[h] = temp;
                h--;
            }
        }
        if(l-1 > low)
            sort(a, low, l-1);
        if(h+1 < high)
            sort(a, h+1, high);
    }
}