21.快速排序

1.快速排序介绍

快速排序是对冒泡排序的改进。基本思想：通过一趟排序将一组数组分成两部分，一部分的元素都比另一部分的元素小，然后按照此方法对两部分数据分别进行快排，最终达到将这组数据变为有序数据的目的。

2.思路分析

• 选取数组中的第一个元素作为基准值，左右分别设置一个哨兵。
• 右边哨兵从数组的最后一个元素开始向左寻找比基准值小的元素，找到就停下来
• 左边哨兵从第一个元素开始向右找比基准值大的元素，找到就停下来
• 如果说此时左右两个哨兵没有相遇，那么就交换两个哨兵所在位置的元素的值
• 如果相遇，就将此时哨兵所在位置的元素与基准值交换位置，此时基准值左边的元素都比基准值小，右边的元素都比基准值大
• 然后对两边的元素分别递归使用快排

3.代码实现

    public static void quickSort2(int arr[],int left,int right){
        int i,j,base,temp;
        if(left>right){
            return;
        }
        i = left;j=right;base=arr[left];
        while (i<j){
            while(arr[j]>=base&&i<j){
                j--;
            }
            while (arr[i]<=base&&i<j){
                i++;
            }
            if(i<j){
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = base;
        quickSort2(arr,left,j-1);
        quickSort2(arr,j+1,right);
   }