排序算法中用的最多的是快速排序和归并,还有堆排序。因为效率比较高,时间复杂度均为O(nlogn)。
用l,r表示待排序数组左右端点
快速排序
快速排序的步骤:
1、确定分界点x 一般是l,r,或者mid。
2、调整范围
把数组整理成两部分以j位置为分界点,j左边的数都小于等于x,右边的数都大于等于分界点x,这是j位置上的数不一定是x。(根据下面的代码)其他的算法书上有将j位置归位为x的代码(见算法4)。
3、递归处理两边
代码如下
1 | void quick_sort(int q[ ],int l,int r) |
应用:快速选择
本题要求找第k大的数。为了理解方便,转化为第_k小的数。
这里可以应用快速排序的模板+二分的思想。每次把数组分为左右两边的时候,判断第k是否在j位置的左边,如果k<=j我们要找的目标一定在[l,j]中。反之则向右边递归。递归终止条件l==r。即区间只有一个元素。
代码如下
1 | int findKthLargest(vector<int>& nums, int k) { |
归并排序
归并排序是典型的分治思想
步骤如下
1、明确分界点。即mid=(l+r)/2
2、递归排序左右
3、归并(核心)
代码如下
1 | void merge_sort(int q[ ], int l,int r) |
核心是将每次归并的结果放入一个临时数组再放回我们的待排序数组,在归并的过程中用到了两个指针,每次将小的那个指针指向的数放入数组,并将指针后移。
应用:
求逆序对的数量 剑指offer51
这题主要是应用了归并排序分治的思想,以中点为界,我们可以将逆序对分为三类 1、都出现在数组左边 2、都出现在数组右边 3、一个在左边一个在右边。
定义我们的merge_sort函数可以将数组排序,并返回当前区域中逆序对的数量。同时考虑更新当前逆序对的数量用res表示。前两类逆序对数量很好求,直接递归调用
1 | res=merge_sort(l,mid)+merge_sort(mid+1,r) |
在归并的那步中,可以求出第三类逆序对的数量。
当q[i]>q[j]时可以得出对于q[j]的第三类逆序对数量为mid-i+1。
代码如下
1 | class Solution { |
堆排序
堆是一种完全二叉树。它可以在O(1)时间访问优先级最高的节点,所以可以用来实现优先级队列。对于堆的增删查改操作,主要是要维护堆顶元素一直为最大或者最小。堆排序的过程就是将序列建为最小堆,然后把最小堆的堆顶依次输出删除即可。
那么如何维护最小堆(最大堆也是同理)。首先就是关键的操作up和down。我们要维护的是堆中最小的元素一直在堆顶,顾名思义up就是将小元素上浮,当前元素比父节点元素小,不满足堆的定义,就与父节点交换位置 。那么down操作就是将大的元素下沉。
再来看一下删除操作,对于堆来说删除堆顶元素,实际上是将堆的最后一个元素覆盖堆顶元素,维护一个size变量,size–,再执行down操作,调整元素位置。
堆排序算法实际上就只用到down操作。
down的实现如下
1 | void down(int u) |
建堆的话可以从n/2开始,因为最下面一层的元素是不需要down的。
1 | for(int i=n/2;i;i--) down(i); |
堆排序的复杂度也是O(nlogn)。