`
xinklabi
  • 浏览: 1586387 次
  • 性别: Icon_minigender_1
  • 来自: 吉林
文章分类
社区版块
存档分类
最新评论

快速排序原理及代码实现

 
阅读更多

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)。

 

   假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一趟快速排序的算法是:

 

  1)、设置两个变量IJ,排序开始的时候I=1J=N

 

  2)以第一个数组元素作为关键数据,赋值给X,即X=A[1]

 

  3)、从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,两者交换;

 

  4)、从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,两者交换;

 

  5)、重复第34步,直到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

 

                  ( 按照算法的第三步从后面开始找)

 

进行第二次交换后:  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(low==high) return;
        array[low] = array[low]  + array[high];
        array[high] = array[low] - array[high];
        array[low] = array[low] - array[high];
    }
   

分享到:
评论

相关推荐

    快速排序算法 源代码

    在这个名为"快速排序算法 源代码"的资源中,包含了一个名为`QuickSortOriginal.cpp`的C++源代码文件,它实现了一个经典的快速排序算法。C++是一种通用的、面向对象的编程语言,因其高效性、灵活性和强大的模板系统而...

    快速排序算法(c#实现)

    总的来说,快速排序是一种非常重要的排序算法,理解其工作原理并能用C#或其他编程语言实现,对于提升编程技能和解决问题的能力大有裨益。在实际项目中,根据具体场景选择合适的排序算法是优化程序性能的关键。

    直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码

    直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...

    快速排序c++源代码

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,通过一趟排序将待...通过理解并掌握快速排序的原理和C++实现,可以帮助开发者更好地解决大规模数据处理的问题。

    交换类排序(内有经典的冒泡排序和快速排序C++代码实现)

    **快速排序的实现**: ```cpp int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为基准 int i = (low - 1); // 将i设为小于基准的元素的索引 for (int j = low; j ;...

    快速排序实现原理,及Java实现

    ### 快速排序实现原理及Java实现 #### 一、快速排序算法原理 快速排序是一种高效的排序算法,基于分治法的思想。它的工作原理可以概括为以下几个步骤: 1. **选择基准值**:从待排序的序列中选择一个元素作为基准...

    快速排序 数据结构 实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R....以上就是关于快速排序的基本原理、实现细节及其测试策略的详细说明。在实际编程中,理解和掌握快速排序的这些知识点对于编写高效的排序代码至关重要。

    快速排序代码整合集合

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and ...通过学习和比较这些代码,你将能够深入理解快速排序的工作原理,并能够在自己的项目中灵活运用。

    数据结构快速排序算法实现

    实验代码提供了一个使用C语言实现的快速排序算法示例,其中定义了`Sqlist`结构体来表示顺序表,以及`Partition`和`QSort`函数来实现快速排序的分区和排序逻辑。 - `Partition`函数负责分区操作,它接收一个顺序表`L...

    确定性快速排序与随机化快速排序的比较

    快速排序的代码实现可以通过递归的方式编写,其中包含一个快速排序函数和一个分区函数。快速排序函数接受一个数组以及区间的起始和结束索引作为参数,通过递归调用自身来对子区间进行排序。分区函数则负责将输入数组...

    用java实现快速排序

    根据给定文件的信息,本文将围绕“用Java实现快速排序”的主题进行展开,不仅解析标题与描述中的核心知识点,还会对部分代码示例进行解读,最后结合这些信息给...希望本文能帮助你更好地理解快速排序的实现过程及原理。

    C语言快速排序算法实现

    标题:C语言快速排序算法实现 描述:本文将深入探讨...总结,通过使用C语言实现快速排序算法,我们可以有效地对大规模数据进行排序处理,而理解和掌握其原理及实现细节对于提高数据处理能力和算法理解具有重要意义。

    快速排序C++的实现

    5. **代码实现**:展示C++实现的快速排序代码,包括主函数、分区函数和快速排序函数。 6. **优缺点**:讨论快速排序的优缺点,如效率高、不稳定、对输入敏感等。 7. **应用实例**:列举快速排序在实际问题中的应用。...

    快速排序的原理及java代码实现

    然而,在实际应用中,由于快速排序的内部循环可以高效实现,并且对于大多数随机分布的数据,快速排序通常比其他Ο(nlogn)排序算法更快。 需要注意的是,快速排序不是稳定的排序算法,即相等的元素可能会改变它们...

    排序代码(C语言),快速排序,冒泡排序,归并排序等等

    在给定的代码中,我们可以看到快速排序的实现。首先,我们定义了一个 partition 函数,它将数组分为两部分,然后返回轴元素的索引。接着,我们定义了两个快速排序函数,quicksort1 和 quicksort2。quicksort1 使用...

    快速排序源码+排序原理说明

    快速排序的源码实现通常使用C++、Java等编程语言,其核心在于`partition`函数和递归调用。下面是一个简化的C++版本快速排序的实现示例: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { ...

    归并和快速排序c程序实现

    在实际编程中,理解这两种排序算法的原理,并根据具体场景选择合适的排序方法,对于提高代码性能至关重要。例如,如果内存空间允许,归并排序在处理大量数据时表现出色;而对于小规模或者内存有限的情况,快速排序...

    合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现

    本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...

    Python3实现快速排序(源代码)

    这段代码展示了如何使用Python3实现快速排序。需要注意的是,这种实现方式在处理大数据集时效率较低,因为它在每次分割时都会重新构建两个列表。在实际应用中,推荐使用**原地排序**的方法,通过交换数组中的元素来...

    快速排序、堆排序、归并排序、希尔排序实现

    C++中实现快速排序的关键是选取合适的基准值和分区操作。 **堆排序(Heap Sort)** 堆排序是一种基于比较的内部排序方法,它利用了完全二叉树的特性。堆可以看作是一个近似最大或最小元素的优先队列。在C++中,可以...

Global site tag (gtag.js) - Google Analytics