快速排序原理（java实现）

刺骨的言语ヽ痛彻心扉 2022-06-10 08:27 114阅读 0赞

快速排序也是排序算法的一种，他的基本思想是这样的：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（摘自百度百科）  
　　  
　　好，上面的东西，很难理解，很难想象，我知道，那咱们还是举个例子，假定现在有一个整型数组\{1,2,6,8,5,3,4,7,9\}，首先，我们定义一个整型变量i指向数组的最左边，定义一个整型变量j指向数组的最右边，之后，随便在数组中选择一个数，不妨我们就选择最中间的那个数字5（我们称之为支点pivot），然后，用i指向的数据与这个5进行比较，也就是1跟5比较，1比5小，那么就让i++，再用2跟5比，2比5小，接着i++，6跟5比，6比5大，这时，就先不管i了，去看j，用j指向的数据与5进行比较，也就是9跟5比，9比5大，然后，j- -，用7跟5比，7比5大，j- -，用4跟5比，4比5小，这时，注意了，只要将j中的数据，和刚刚i中的数据进行交换，那么，数组就变成了\{1,2,4,8,5,3,6,7,9\}，可以发现，5左边比5大的数少了一个，右边比5大的数多了一个，之后再让i++，j- -，继续刚刚的比较，先找到左边比5小的，再找到右边比5大的，一交换，就行了，重复这个过程，直到i>j，那么此时我们就可以保证，5左边的数，全部都是比5小，右边的数全部都是比5大，再对左边的数据以及右边的数据分别进行一次快速排序（递归调用），那么整个数组就被排好序了

class Demo
    {
        //定义快速排序函数
        public static void quickSort(int[] arr,int L,int R)
        {
            //让i指向数组的最左边
            int i = L;
            //让j指向数组的最右边
            int j = R;
            //随便选取一个支点，这里选择最中间的数组
            int pivot = arr[(L+R)/2];
            //当i<=j的时候，执行循环
            while(i<=j)
            {
                //通过循环找到第一个左边不小于支点的数
                while(arr[i]<pivot)
                {
                    i++;
                }
                //通过循环找到第一个右边不大于支点的数
                while(arr[j]>pivot)
                {
                    j--;
                }
                //为了防止循环过程中出现i>j的情况时，依旧执行交换，故设置此条件
                //读者可以自己走一遍就明白为什么了
                if(i<=j)
                {
                    //交换i，j中的值
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }
            //对左边的数据进行快速排序
            if(L<j)
            {
                quickSort(arr,L,j);
            }
            //对右边的数据进行快速排序
            if(i<R)
            {
                quickSort(arr,i,R);
            }
        }
    
        public static void main(String[] args)
        {
            //定义一个整型数组
            int[] arr = {
       1,2,6,8,5,3,4,7,9};
            //调用快速排序函数
            quickSort(arr,0,arr.length-1);
            //输出排序后的数组
            for(int i=0;i<arr.length;i++)
            {
                System.out.print(arr[i]+" ");
            }
        }
    }