java - 数据结构 - 快速排序

alicelmx 2019-11-12

- -网上找结果很多都是无法排序有重复数据的,因此查了查资料写个改良版

百度百科:

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。 
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。 

思路:

1. low和high作为指针,

2. 起始以数组最左边(low)的数据作为基准base(所以右移一格,从第二个数开始判断排序)

3. low 从左往右直到大于等于base,保证low左边的地方,数据都小于base

4. high从右往左直到小于base,保证high经过的地方,数据都大于等于base。

5. 如果high <= low, 说明两个指针交叉了,也就是遍历完毕了。结束循环

6.如果high > low, 说明遍历没结束,交换low 和 high的数值 

循环2,3,4,5,6直到触发5结束循环

7.循环结束后,high左边的数字全小于等于base,右边的全部大于base,high目前指向的数字是在目前的low左边或者和low一样,因此肯定小于base。

这时候交换base 和 high指向的数字。 这样就把base放在了中间位置,左边小于他,右边大于等于他。

8. 进行递归, 对base的左边和右边重复1-7的步骤,直到所有部分排序完毕。

package sort;


public class Sort {
    public static void main(String[] args){
        int[] a = new int[]{3,5,2,6,6,7,8,7,7,7,7,7,7,7,7,7,7,7,74,13,3,0,9,6,4,9,8};
        //int[] a = new int[]{5, 4, 3, 2, 1};
        Sort s = new Sort();
        s.quickSort(a, 0, a.length - 1);
        showArray(a);
    }



    public int[] quickSort(int[] a, int start, int end){

        if(start >= end) { //递归到达最底层
            return a;
        }

        int base = start;
        int low = start + 1;
        int high = end;

        while(true){

            while(low < end && a[low] < a[base]){
                low++;
            }
            while(high > start && a[high] >= a[base]){
                high--;
            }
            //找到位置看看是不是遍历完毕走过头了
            if(high <= low){
                break;
            }
            else{
                //没走过头,交换high 和 low
                int i = a[low];
                a[low] = a[high];
                a[high] = i;
            }
        }

        //showArray(a);

        //此时high所在位置是一个< a[base]的数, 前面全小于a[base],后面全大于等于a[base] ,交换a[high]和a[base]把基准放在中间
        int i = a[base];
        a[base] = a[high];
        a[high] = i;

        //递归
        quickSort(a, start, high - 1  );
        quickSort(a, high + 1, end);

        return a;
    }


    public static void showArray(int[] a){
        for(int i:a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

相关推荐