排序算法(三)---快速排序2017-11-10 09:24:19

快速排序


    继插入排序,归并排序,堆排序后,今天将讲解快速排序。

    对于包含n个数的输入数组来说,快速排序的最坏情况时间复杂度为O(n^2)的排序算法,虽然最坏的时间复杂度很差,但是快速排序通常是实际排序应用中最好的选择,因为它的平均性能非常好,它的期望时间复杂度为是O(nlgn)

    与归并排序一样,快速排序也使用了分治的思想。

具体的过程:

1、 分解:数组Array[p..r]被划分为两个(可能为空)子数组Array[p..q-1] Array[q+1..r],使得Array[q]大于等于Array[p..q-1]中的所有元素,并且小于等于Array[q+1..r]中的所有元素。

2、 解决:通过递归调用快速排序,对子数组Array[p..q-1] Array[q+1..r]进行排序。

3、 合并:因为快速排序都是原址排序,所以不需要进行合并操作,数组Array[p..r]已经有序。

该算法的关键部分即是数组的划分部分,它实现了对子数组的原址重排。

代码如下:

int Partition(int* array, int p, int r) {  //p,r 为元素在数组中的序号
       int MainElement = *(array + r);
       int i = p - 1;
       int temp;
       for (int j = p; j < r; j++) {
              if (*(array + j) <= MainElement) {
                     i++;
                     temp = *(array + i);
                     *(array + i) = *(array + j);
                     *(array + j) = temp;
              }
       }
       temp = *(array + i + 1);
       *(array + i + 1) = *(array + r);
       *(array + r) = temp;
       return i + 1;
}


 

该函数传入的参数是要排序的数组,和要排序的元素的序号范围。返回的上述描述过程中的q值。

序号为的元素,将原数组一分为二,被分的两个子数组可能为空。

如何理解:

该算法先设置一个主元,即MainElement,将传入的数组,从起始元素依次与主元比较,若较小则往左边置换,i变量即是要置换元素的序号,从代码可以看出如果主元较大,则不置换,这样可以保证,从起始序号一直到i都将会比主元小。之后将i+1 置换为主元,函数执行完毕,返回主元的序号。

至此,该算法的关键步骤已经解决,然后只需对被划分的数组继续递归调用分解函数即可。

代码如下:

void QuickSort(int* array, int p, int r) {
       if (p < r) {
              int q;
              q = Partition(array, p, r);
              QuickSort(array, p, q - 1);
              QuickSort(array, q + 1, r);
 
       }
}


从该算法可以看出,实现排序的关键就是分解。

我们可以想到,快速排序的运行时间依赖于划分是否平衡,而平衡与否又依赖于用于划分的元素,即主元。最坏的情况就是划分产生的子问题分别包含了n-1个元素和0个元素,如果算法在每一层的递归上,划分都是最大程度不平衡的,那么快速排序的时间复杂度为O(n^2),与插入排序相同,即使输入的数组已经完全有序,快速排序的时间复杂度仍为O(n^2),而此时的插入排序的时间复杂度为O(n)。在可能的最大划分中,分解得到的子问题的规模都不大于n/2。此时的算法复杂度为O(nlgn)

   在讨论快速排序的平均情况性能时,我们的前提假设是,输入数据的所有排列都是等概率的。但在实际过程中,这个假设并不会总是成立。有时,我们可以通过在算法中引入随机性,从而使得算法对于所有的输入都能获得较好的期望性能。

   要使算法实现随机化,可以采用随机抽样。与始终使用Array[r]作为主元不同,随机抽样是从Array[p..r]中随机抽取一个元素作为主元,因为主元元素是随机抽取的,我们可以相信对输入数组的划分是比较均衡的。

代码如下:

int Random(int p, int q) {
       std::default_random_engine random(time(NULL));
       std::uniform_int_distribution<int> dis1(p, q);
       return dis1(random);
}
 
int RandomPartition(int* array, int p, int r) {
       int i = Random(p, r);
       int temp;
       temp = *(array + r);
       *(array + r) = *(array + i);
       *(array + i) = temp;
       return Partition(array,p,r);
}
 
void RandomQuickSort(int* array, int p, int r) {
       if (p < r) {
              int q = RandomPartition(array, p, r);
              RandomQuickSort(array, p, q - 1);
              RandomQuickSort(array, q + 1, r);
       }
}


Random()获取随机数,其他的与原来的算法相似,该算法就是快速排序的随机化版本。



linweiyu

Something should be here;

0 Thoughts

Leave a Thought