Java排序算法之快速排序

一时失言乱红尘 2022-04-04 12:40 175阅读 0赞

快速排序，顾名思义，速度快；其时间复杂度为(NlogN)，那么它是如何运作来实现高速排序的呢？先讲一下它的基本原理：

(1)寻找到一个枢纽元，也就是在一组元素中找一个元素(怎么找是有讲究的);

(2)然后在这组元素中，比这个枢纽元小的放在左边，比其大的放在右边；

(3)然后对左右重复上述两步，即可实现从小到大排序；

这三个步骤中有两个问题非常有意思。

第一：如果这个枢纽元是这组元素的最大值或是最小值，那么所有的元素都在枢纽元的一侧，所以这是最坏的一种情况，但是还能接受，因为后面递归的选取枢纽元你应该会选取到一个不大不小的枢纽元的吧。要不然，你总不会每次都很幸运的选取到那个最大的或是最小的枢纽元吧，要是这样，你可以去买彩票了。所以，是可以随便选的，一般选取第一个数，或是随机选。

第二：还是这个枢纽元的问题，假如啊，你选取的这个枢纽元在这组元素中有重复值啊，比方说这组元素中有三个8，你选取的枢纽元恰好是8，按照规则：比8小的放在左边，比8大的放在右边，那么问题来了，等于8的放在哪边？这是我们的处理是要么全放在左边，要么全放在右边。

下面画图说明快速排序的步骤，引用数组【7,10,2,4,7,1,8,5,19】，我们选取的枢纽元是第一个数7，可以看到该数组有两个7；加入我们将小于7的放在左边，大于等于7的放在右边。

先说一下游戏规则：两个指针，分别从数组的首尾开始向中间运动，左指针先运动，左指针指到的数若大于或等于枢纽元则停下来，当左指针停下来的时候，右指针运动，右指针指到的数若小于枢纽元则停下来，此时，交换左右指针指向的数，然后重复上述运动。直到左右指针相遇，运动结束。

![20181217173211898.png][]

左指针指到的数等于7，停下来；右指针指向的数大于7，继续走。。。

![20181217173302934.png][]

右指针指向的数为5，小于7，停下来；然后交换两个指针指向的数。。。

![20181217173452192.png][]

然后左指针继续走，走到10，大于7，停下来；然后右指针走，指向8，大于7，继续走，然后走到1，小于7，停下来。。。

![20181217173733977.png][]

然后交换左右两个指针的指向的值。。。

![201812171738509.png][]

然后左指针继续走，走到2，小于7，继续走，走到4，继续走，走到7，等于7，停；然后右指针走，走到7，和左指针相遇。。。

![20181217174053915.png][]

然后以7位界限，左边的都是小于7的数，右边的都是大于7的数。然后将左边的【5,1,2,4】和右边的【10,8,7,19】看成是两个数组，重复上述的步骤，就可以排成【1,2,4,5,7,7,8,10,19】这样的从小到大的有序数组。

================================================================================================        下面用代码演示：

package com.Jevin.priorityQueue;
    
    public class QuickSort {
        
        public static void quickSort(int[] arr,int low,int high){
            int i,j,temp,t;
            if(low>high){
                return;
            }
            i=low;
            j=high;
            //temp就是基准位
            temp = arr[low];
    
            while (i<j) {
                //先看右边，依次往左递减
                while (temp<=arr[j]&&i<j) {
                    j--;
                }
                //再看左边，依次往右递增
                while (temp>=arr[i]&&i<j) {
                    i++;
                }
                //如果满足条件则交换
                if (i<j) {
                    t = arr[j];
                    arr[j] = arr[i];
                    arr[i] = t;
                }
    
            }
            //最后将基准为与i和j相等位置的数字交换
            arr[low] = arr[i];
            arr[i] = temp;
            //递归调用左半数组
            quickSort(arr, low, j-1);
            //递归调用右半数组
            quickSort(arr, j+1, high);
        }
    
    
        public static void main(String[] args){
            int[] arr = {7,10,2,4,7,1,8,5,19};
            quickSort(arr, 0, arr.length-1);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
    }

运行结果是：

![20181217174531396.png][]

干得漂亮！！！

[20181217173211898.png]: /images/20220404/f92537aab52540ad93be2d873d84d1c9.png
[20181217173302934.png]: /images/20220404/4b68dab14df84c089122453a41e20487.png
[20181217173452192.png]: /images/20220404/0cf84d9af1314b6598fc41f0328ec876.png
[20181217173733977.png]: /images/20220404/bb0d6480a5d641828062752b59cd914e.png
[201812171738509.png]: /images/20220404/16e9e827d99c4addb0d166646fe75aaf.png
[20181217174053915.png]: /images/20220404/64b3556471e941fba7c2702bfbbabfd1.png
[20181217174531396.png]: /images/20220404/be58119ca73149a1ae764985f733a7ae.png