交换排序之《快速排序》

逃离我推掉我的手 2022-05-14 03:17 132阅读 0赞

**快速排序，见名知意肯定是比较快。据实验所要排序的序列越乱，快速排序的效率越高！也是一种不稳定的排序！**

**快速排序**基本思想：通过一轮的排序将序列分割成独立的两部分，其中前一部分序列的关键字（这里主要用值来表示）均比后一部分序列的关键字关键字小（递增排序）或者大（递减排序）。然后继续分别对两部分的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，因此减少了比较次数，降低了排序时间。

> **-------------------------------------------------------分割线，画图说明----------------------------------------------------------------------**

int\[\] array = \{5,1,4,8,0,7,2,9\};

确定一个在数组中的比较**标杆**，一般以数组下表0的数值作为标杆：**index=array\[0\]**, **循环条件i<j.**  
分别判断数组下表i与j处的对比标杆大小，如果下表j处的数值大于index,--j，如果下表j处的数值小于index,则把值赋予i下标位置；如果i处的数值小于index,++i,如果i处的数值大于index。则把值赋予j下标的位置。**直到i=j，循环停止**。

![70][] 下标j处的数字大于5，--j

![70 1][] 下标j处的数字小于5，i处数值赋值2 ,++i

![70 2][] 下标i处的数字小于5，++i

![70 3][] 下标i处的数字小于5，++i

![70 4][] 下标i处的数字大于5，j处数值赋值8,--j

![70 5][] 下标j处的数字大于5，--j

![70 6][] 下标j处的数字小于5，i处数值赋值0,++i

![70 7][] 此时的i不在小于j**,array\[i\]=index**

**后面再分别对前后两部分递归使用上述方法，最后就会完成对整个序列的升序排序！！！**

**下面贴代码，low和high分别代表i和j的位置。至此快拍就这么结束了，也并不难吧！主要是理解思路就变得简单!**

/**
         * 快速排序
         * @param a array name
         * @param low array begin index
         * @param high array end index
         */
        public static void quickSort(int a[],int low,int high){
    
            int i = low;
            int j = high;
            int temp = a[i];
            if(i>=j){
                return ;
            }
            while(i<j){
    
                while(i<j && a[j]>=temp){
                    j--;
                }
                if(i<j){
                    a[i]=a[j];
                    i++;
                }
                while(i<j && a[i]<=temp){
                    i++;
                }
                if(i<j){
                    a[j]=a[i];
                    j--;
                }
            }
            a[i] = temp;
            quickSort(a,low,i-1);
            quickSort(a,i+1,high);
        }

[70]: /images/20220514/bc03f4a346924e26ba9d4f3d62f3c06a.png
[70 1]: /images/20220514/9de3749345794e06b5d89cbed9170ee5.png
[70 2]: /images/20220514/8f5ad0d8e2a7431e959b2a42153f8649.png
[70 3]: /images/20220514/5bc37de1e75841a29416f679c4cf9d9b.png
[70 4]: /images/20220514/f38ea42aefbb4042b0698ff1f63222b0.png
[70 5]: /images/20220514/07c6f610de244ad981387a3765f94295.png
[70 6]: /images/20220514/b1d9be08737e4d4aa621af8880b506b4.png
[70 7]: /images/20220514/db7c124e000d43d58afcf524e96ba910.png