快速排序原理及代码完成ITeye - 亚美娱乐

快速排序原理及代码完成ITeye

2019年03月05日14时30分33秒 | 作者: 怜雪 | 标签: 排序,快速,数据 | 浏览: 346

快速排序是对冒泡排序的一种改善。它的基本思维是:经过一躺排序即将排序的数据切割成独立的两部分,其间一部分的一切数据都比别的一不部分的一切数据都要小,然后再按次办法对这两部分数据别离进行快速排序,整个排序进程能够递归进行,以此到达整个数据变成有序序列。最坏状况的时刻复杂度为O(n2),最好状况时刻复杂度为O(nlog2n)。

 

   假定要排序的数组是A[1]……A[N],首要恣意选取一个数据(一般选用榜首个数据)作为要害数据,然后将一切比它的数都放到它前面,一切比它大的数都放到它后边,这个进程称为一躺快速排序。一趟快速排序的算法是:

 

  1)、设置两个变量I、J,排序开端的时分I:=1,J:=N;

 

  2)以榜首个数组元素作为要害数据,赋值给X,即X:=A[1];

 

  3)、从J开端向前查找,即由后开端向前查找(J:=J-1),找到榜首个小于X的值,两者交流;

 

  4)、从I开端向后查找,即由前开端向后查找(I:=I+1),找到榜首个大于X的值,两者交流;

 

  5)、重复第3、4步,直到I=J;

 

  例如:待排序的数组A的值别离是:(初始要害数据X:=49)

 

                  A[1]    A[2]    A[3]    A[4]    A[5]     A[6]    A[7]: 

 

                    49       38      65      97      76      13       27

 

进行榜首次交流后:  27       38      65      97      76      13       49

 

                  ( 依照算法的第三步从后边开端找)

 

进行第2次交流后:  27       38      49      97      76      13       65

 

                 ( 依照算法的第四步从前面开端找 X的值,65 49,两者交流,此刻I:=3 )

 

进行第三次交流后:  27       38      13      97      76      49       65

 

( 依照算法的第五步将又一次履行算法的第三步从后开端找)

 

进行第四次交流后:  27       38      13      49      76      97       65

 

( 依照算法的第四步从前面开端找大于X的值,97 49,两者交流,此刻J:=4 )

 

     此刻再履行第三步的时分就发现I=J,然后完毕一躺快速排序,那么经过一躺快速排序之后的成果是:27       38      13      49      76      97       65,即所以大于49的数悉数在49的后边,所以小于49的数悉数在49的前面。

 

     快速排序就是递归调用此进程——在以49为中点切割这个数据序列,别离对前面一部分和后边一部分进行相似的快速排序,然后完结悉数数据序列的快速排序,最终把此数据序列变成一个有序的序列,依据这种思维关于上述数组A的快速排序的全进程如图6所示:

 

 初始状况                       {49    38    65    97    76    13    27}   

 

进行一次快速排序之后划分为     {27    38    13}    49  {76    97    65}

 

别离对前后两部分进行快速排序   {13}   27   {38} 

 

                               完毕        完毕   {49   65}   76   {97}

 

                                                   49  {65}        完毕

 

                                                       完毕

 

                         图6   快速排序全进程

 

 

 

1)、设有N(假定N=10)个数,存放在S数组中;

 

2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起意图就是在定出T应在排序成果中的方位K,这个K的方位在:S[1。。K-1] =S[K] =S[K+1..N],即在S[K]曾经的数都小于S[K],在S[K]今后的数都大于S[K];

 

3)、使用分治思维(即大化小的战略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组目标只要一个数据停止。

 

如详细数据如下,那么榜首躺快速排序的进程是:

 

数组下标: 1     2     3     4     5     6     7     8     9     10

 

          45    36    18    53    72    30    48    93    15     36

 

          I                                                       J

 

(1)     36    36    18    53    72    30    48    93    15     45

 

(2)     36    36    18    45    72    30    48    93    15     53

 

(3)     36    36    18    15    72    30    48    93    45     53

 

(4)     36    36    18    15    45    30    48    93    72     53

 

(5)     36    36    18    15    30    45    48    93    72     53

 

经过一躺排序将45放到应该放的方位K,这儿K=6,那么再对S[1。。5]和S[6。。10]别离进行快速排序。

 

    /**

 

     *交流指定数组a的两个变量的值

 

     *@parama数组使用

 

     *@parami数组下标

 

     *@paramj数组下标

 

     */

 

    publicstaticvoid swap(int a[], int i, int j) {

 

       

 

        if(i j) return;

 

 

 

        int tmp = a[i];

 

 

 

        a[i] = a[j];

 

 

 

        a[j] = tmp;

 

 

 

    }

 

 

 

    /**

 

     *

 

     *@paramarray待排序数组

 

     *@paramlow数组下标下界

 

     *@paramhigh数组下标上界

 

     *@returnpivot

 

     */

 

    publicstaticint partition(int array[], int low, int high) {

 

        //当时方位为榜首个元素所在方位

 

        int p_pos = low;

 

        //选用榜首个元素为轴

 

        int pivot = array[p_pos];

 

        

 

        for (int i = low + 1; i = high; i++) {

 

 

 

            if (array[i] pivot) {            

 

               

 

                p_pos++;

 

 

 

                swap(array, p_pos, i); 

 

 

 

            }

 

 

 

        }

 

 

 

        swap(array, low, p_pos);

 

 

 

        return p_pos;

 

 

 

    }

 

    /**

 

     *快速排序完成

 

     *@paramarray

 

     *@paramlow

 

     *@paramhigh

 

     */

 

    publicstaticvoid quickSort(int array[], int low, int high) {

 

 

 

        if (low high) {

 

 

 

            int pivot = partition(array, low, high);

 

 

 

            quickSort(array, low, pivot - 1);

 

 

 

            quickSort(array, pivot + 1, high);

 

 

 

        }

 

 

 

    }

 

 

  上面的代码是从网上找的,选取的是数组榜首个数作为比较数,下面是自己写的,以中心的数为比较数,其实思维都是每次比较后把比较数放中心,然后不断递归下去罢了:

 

public static void x_quickSort(int[] array, int low, int high){
        if(low high){
            int midDataIndex = x_partition(array, low, high);
            if(midDataIndex-1 low)
                x_quickSort(array, low, midDataIndex-1);
            if(midDataIndex+1 high)
                x_quickSort(array, midDataIndex+1, high);
        }
    }
   
    public static int x_partition(int[] array, int low, int high){
        int midData = array[(low+high)/2];
        x_swap(array, low, (low+high)/2);
        int midDataIndex = low;
        low++;
        boolean low_found = false;
        while(low high){
            if(array[low] midData !low_found)
                low++;
            else
                low_found = true;
            if(array[high] midData)
                high;
            else if(low_found){
                x_swap(array, low, high);
                low_found=false;
                high;
            }
        }
        if(array[low] midData)
            x_swap(array, low, midDataIndex);
        else
            x_swap(array, low-1, midDataIndex);
        return low;
    }
   
    public static void x_swap(int[] array, int low, int high){
        if(lowhigh) return;
        array[low] = array[low]  + array[high];
        array[high] = array[low] - array[high];
        array[low] = array[low] - array[high];
    }
   

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表亚美娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1
  • 2
  • 3
  • 4
  • 5

    Digester 解析XMLITeye

    元素,参数,解析
  • 6

    运用文件体系ITeye

    目录,读取,是否
  • 7
  • 8
  • 9

    Deep diving into CloningITeye

    文章,摘自,首先
  • 10

    Spring 整合 junit4 测验ITeye

    测验,配置文件,试用