算法之快速排序

基本思想

快速排序基本思想：对一组无序的数据随机取一个作为基准数，然后进行一次排序，划分成左右两个部分。左边区间的数比基准数小，右边的数比基准数大，然后再使用同样的方法对左右区间在各自进行排序，就能得到有序的序列。

算法设计

（1）.随机取一个数记作基准数key，一般使用数组第一个数。

（2）.定义首尾两个指针，尾指针向前搜索,找到小于等于key的数，然后放到首指针所在的位置，并让首指针位置往后移一位。
首指针向后搜索,找到大于key的数，然后放到尾指针所在的位置，并让尾指针位置往前移一位。

如果在查找中找不到对应的值，则继续往下查找。

（3）.重复第二个步骤，直到首尾指针相遇，此时一轮排序结束。

（4）.一轮排序结束后，需要把中位数的值放到最后的坑位。

案例代码

//Java实现
public class QuickSort {

public static void solutionHole(int[] arr,int begin,int end){

    if(begin >= end){
        return;
    }
    //取一个中间值
    int mid = arr[begin];
    //定义首尾指针
    int left = begin;
    int right = end;

    while (left<right){
        //右区间查找比mid小的数，放到左边
        while (left < right && arr[right]>mid){
            right--;
        }
        if(left < right){
            arr[left] = arr[right];
            left++;
        }
        //左区间查找比mid大的数，放到右边
        while (left < right && arr[left]<mid){
            left++;
        }
        if(left < right){
            arr[right] = arr[left];
            right--;
        }
        //两个指针重叠时，查找完毕，把中位数的值放进去
        if(left == right){
            arr[left] = mid;
        }
        System.out.println(Arrays.toString(arr));
    }
    //递归调用，分别对左右区间在排序一次
    solutionHole(arr,begin,left-1);
    solutionHole(arr,right+1,end);

}

public static void main(String[] args) {
    int [] arr = {47,29,71,99,78,19,24,19};
    int begin = 0;
    int end = arr.length-1;
    solutionHole(arr,begin,end);
}
}

注意点

• 先从右边开始查找，在到左边，顺序不能乱。
• 查找完之后当前指针位置不变，然后交替移动指针位置。
• 排序结束后需要把基准值填入最后的坑位，并对左右区间在进行排序。
• 有两种解法：交换法和挖坑法，两种实现方式不太一样，这里以挖坑法为主。

本作品采用《CC 协议》，转载必须注明作者和本文链接