一 前言

算法对于程序员来说,是一个不得不去过的门槛,除了面试,工作中用到的机会却很少,偶尔用到的算法都有封装好的库调用下,就可以了,少有机会去写一个,偶尔有机会写个和算法相关的函数,可能心中也有几分忐忑,没有充分测试,总是怀疑其中隐藏什么大bug,在不该爆发的场合突然爆发,留下的一地的尴尬。

更可气的是,算法学起来的时候看起来都明白了,很简单嘛,真正动手去写的时候,却很难写出无bug的哪怕是简单的算法代码来,说起来还是没有深刻的理解,在一些细节上总是模糊不清,似是而非。所以学习算法这件事情来说,关键是要理解深刻的背后思想,不能是简单地过一遍,而是学一分就深刻理解一分,一分不理解就不要看其他的,揉碎了融入自己的思想里面,变成自己的内功,才算有收获。

二 为什么是快速排序

首先的问题是为什么要排序,除了一些我们想知道排名的场合,比如高考排名等?如果不是这些场合是不是就不要排序了,排序是计算机里面的最基本需求,排序的目的想想还是挺多的,比如我们需要知道Top K值,比如我们需要取一个城市工资的中位数,这个数值比所谓的平均值要靠谱的多,还比如有了排序,就可以做范围查询,有了排序就可以二分查找法,快速查到要搜索的数据,40亿的排序数据查找一个数,只需要最多32次,简直称得上魔法。

那为什么是快速排序那,其实也没啥特别的,就觉得快排的思想挺有意思的,二是性能也很优秀,时间复杂度为O(nlogn), 如果面试偶尔让现场手写个快排代码,也不至于没有啥准备。

虽然快排也有很多种实现,这篇是介绍的最简单的实现,没做什么优化,虽然不是最有用的,但是因为最简单,所以容易理解深刻,也容易写,也记得住。

三 快速排序3.1 快排具体过程

总体来说,快排就三步:

从数组中选择一个基准值;以这个基准值为界,将大于这个基准值的数放在基准值的右边,将小于基准值的数放在基准值的左边;对左右两个区间递归秩序是第一步和第二步。3.1.1 基准分区

第一步和第三步都比较简单,关键是第二步,按照步骤说明下:

排列的求和公式怎么算_排列a52怎么算_排列怎么算

说明: 1) 对上述的数组选择一个基准值,最简单的办法选择第一个元素作为基准值,赋值给tmp。 选择基准值后,第一个元素相当于空出来了。

排列的求和公式怎么算_排列怎么算_排列a52怎么算

比较

说明:我们设置两个指针(其实这里面是下标),分别指向数组的头部和尾部排列怎么算,从尾部开始判断array[j]是不是大于基准值, 因为1

排列怎么算_排列的求和公式怎么算_排列a52怎么算

排列怎么算_排列a52怎么算_排列的求和公式怎么算

说明: 我们判断i处的值是否小于基准值,小于则继续对后移动,一直移动到了array[i] == 9的位置,这时候条件不满足了。

排列怎么算_排列的求和公式怎么算_排列a52怎么算

说明:因为array[i] > 基准值6,则需要将array[j] = array[i], 即将i索引处的值9 赋值到j索引指向的位置。

排列a52怎么算_排列怎么算_排列的求和公式怎么算

填上基准值

说明: i==j了,说明本轮结束了,将基准值回填,这样经过了一轮的比较,我们就得到了第一个元组的正确位置,通过6将整个集合分成了两个部分,一个是左边的子集,全部小于6,一个是右边的子集全部大于6,如下:

排列怎么算_排列a52怎么算_排列的求和公式怎么算

3.1.2 两个子集再递归

通过上图我们得到了 左边子集 + 基准元组+ 右边子集,然后我们分别对左边子集再执行类似的操作,右边子集再进行类似的操作,就完成了整个数组的排序。

左边子集的元素范围是 【 开始索引,i-1】 右边子集的范围是【i+1,结尾索引】

3.1.3 转成实际代码

// 分区
int partion(int a[], int l, int r) {
  int tmp = a[l];
  while (l  tmp && l < r) {
      r--;
    }
    // 小于则赋值给首个元素,即将值移动到前面
   // 如果l==r 则相当于a[0] = a[0] 无影响
    a[l] = a[r];
  // 从前对后判断是否小于基准值,小于等于对后移动
    while (a[l] <= tmp && l < r) {
      l++;
    }
    // 将值移动到后面
    a[r] = a[l];
  }
  a[r] = tmp;
  return r;
}
void qsort(int a[], int left, int right) {
  if (left < right) {
    int mid = partion(a, left, right);
    // 对前面的子集进行排序
    qsort(a, left, mid - 1);
   // 对右边的子集进行排序
    qsort(a, mid + 1, right);
  }
}

虽然代码没做任何其他优化,好处是便于理解也足够简单。

3.2 快排的时间复杂度

复杂度重点在于按照基准值的分区,其他的只是递归计算而已,因为分区的时候我们用的两个指针的技术条件是i == j,扫描了整个数组空间,所以分区函数的时间复杂度是O(n),所以总的时间复杂度为: O(n) = n + T(L) + T(R) 然后T(L)和T(R) 又可以做递归分解,我们按照树的形式将时间分解如下:

排列的求和公式怎么算_排列a52怎么算_排列怎么算

排列怎么算_排列的求和公式怎么算_排列a52怎么算

如上图所示,整个算法的耗时,就是每层耗时,而每层耗时的时间即是分区函数的时间:

第一层: n个元素,分区所占时间为n;

第二层:L子集分区时间为L,R子集分区时间为R,那第二层整体的分区所占时间为L+R,而L+R = n- 1 所以第二层耗时看作是n-1.

第三层:LL +LR+RL+RR = L-1+R -1 即n-3, 依次类推: O(n) = n + n-1 + n-3 + ….看这个是不是等差数列,不,别上当,再计算一层看看:

第四层:LLL+ LLR+LRL+LRR +RLL+RLR+RRL+RRR = LL -1 + LR -1 + RL-1 +RR -1 = (LL+LR)-2 + (RL+RR)-2 = L -1 -2 + R-1 -2 = L+R -6 = n – 7 看到了吧,这种树如果是完全二叉树,每层耗时递减得很快,完全二叉树的数量: 2的h次方(h为树高度)减去1,指数级别的增加;

完全二叉树的高度最低为log2n ,n为节点数,按照刚刚每次计算的耗时,如果n很大,每层接近耗时为n,则总耗时为树的高度* 每层耗时 = nlog2n,即时间复杂度为O(nlog2n)这是最好的情况,如果特殊情况,本身是倒序的,那么树就变成链表,就是nn最坏的时间复杂度为O(n^2)。

四 应用和优化4.1 快排找第k大元素

快速排序算法除了可以排序外,还可以方便找第k大的元素,因为我们每次快排都找到了第一个元组的正确位置index,如果我们要找的第k大元素的k 小于index,那么我们就在小于基准值的集合里面去继续找第k大元素,如果第k大元素大于index,那么第k大元素在大于基准值的集合去找,但是不是找第k元素了,而是找第k-index的元素,这样每次我们都能过滤掉一个集合,性能显然很快。

4.2 优化快排

单边递归优化 分区后,继续对左右两边排序,我们可以把一边在本轮直接处理了,所以叫单边优化:

quick_sort(arr, l, x - 1); // 对左子集排序
quick_sort(arr, x + 1 , r); // 对右子集排序

可以做成:

void quick_sort(int *arr, int l, int r) {
    while (l < r) {
        // 分区
        int ind = partition(arr, l, r);
        // 对大于基准值的右子集正常调用递归函数 
        quick_sort(arr, ind + 1, r);
        // 用本层处理左侧的排序
        r = ind - 1;
    }
    return ;
}

减少了递归的层次,提升了性能。

三点取中法 如果基准值选择得好,那么整个递归排序展开就是完全二叉树,性能最好排列怎么算,所以基准值选择很重要,有种优化是选择开头元素,结束元素,中间元素三个元素中,中间那个,当然上面的代码就不适用了,很大程度上避免选择基准值的问题。

分区函数优化 分区的时候我们每次只是将其中i处和j处的值其中一个赋值给另外一个,如果我们只要满足条件就做移动,直到i和j都不满足的时候,交换两者的值,减少赋值过程,这样性能更快。

———END———
限 时 特 惠: 本站每日持续更新海量各大内部创业教程,一年会员只需98元,全站资源免费下载 点击网站首页每天更新
站 长 微 信: aiwo51889