法前后指针版本非递归实现Hoare版本挖坑法前后指针版本快排的优化三值取中小区间优化归并排序递归实现非递归实现计数排序排序算法复杂度及稳定性分析不同算法的运行效率排序介绍

排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。

在待排序的记录序列中存在多个具有相同关键字的记录若经过排序这些记录的相对次序保持不变则称这种排序算法是稳定的。

比如A

数据元素过多而不能同时存放在内存中需要根据排序过程的要求不断在内外存之间移动数据的排序称为外部排序。

插入排序

基本思想把待排序的记录按其关键码值的代销逐个插入到一个已经排好的有序序列中知道所有的记录插入完为止得到一个新的有序序列。

直接插入排序

在待排序的数组中我们假设前n-1个元素已经是有序的了然后将第n各元素逐一进行比较然后将第n个元素放入合适的位置。

void

a[end];end--;}else{break;}}a[end

tmp;}}时间复杂度与空间复杂度

插入排序中当待排序数组是有序时是最优的情况只需当前数跟前一个数比较一下就可以了这时一共需要比较N-1次时间复杂度为

O(N)。

最坏的情况是待排序数组是逆序的此时需要比较次数最多最坏的情况是

希尔排序

希尔排序是一种插入排序又称为缩小增量排序。

希尔排序在直接插入排序的基础上引入了分组先分组进行预排序然后在通过直接插入排序完成最后的排序。

先选定一个数gap小于这个待排序数据的总数作为第一增量元素之间相差gap的元素作为一组然后分组进行直接插入排序排序完成后缩小增量在重复上述操作直到gap1实现最终的排序。

代码

void

因此对中等大小规模表现良好但对规模非常大的数据排序不是最优选择总之比一般

O(n2)

算法在执行过程中只需要几个定义的临时变量所以空间复杂度为常数级O(1)。

图示

选择排序

基本思想每一次从待排序的数据元素中选出最小或最大的一个元素放在序列的起始位置直到全部待排序的数据元素排完。

选择排序

直接选择排序也是一种简单的排序方法它的基本思想是第一次从R[0]~R[n-1]中选取最小值与R[0]交换第二次从R[1]~R[n-1]中选取最小值与R[1]交换…第i次从R[i-1]~R[n-1]中选取最小值与R[i-1]交换…第n-1次从R[n-2]~R[n-1]中选取最小值与R[n-2]交换总共通过n-1次得到一个按排序码从小到大排列的有序序列。

一个简单的优化就是反正都要遍历一次那就可以找出最大最小的值分别放到结尾和开头这样能够提高一些效率。

代码

void

对于空间复杂度来说简单选择排序仅需一个存储空间用于记录交换的暂存单元即空间复杂度为

O(1)

由于在直接选择排序中存在着不相邻元素之间的互换因此直接选择排序是一种不稳定的排序方法。

图示

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法它是选择排序的一种。

它通过堆来进行数据选择。

排升序要建大堆降序要建小堆。

代码

void

log(N1)N为树的总结点数则排序的时间复杂度为O(logN)。

但是在进行堆排序之前需要先建堆建堆的时间复杂度为O(N)。

对于空间复杂度来说堆排序仅需几个存储空间用于记录一些下标位置所以空间复杂度为

O(1)图示

所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排

序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。

冒泡排序

冒泡排序是一个很形象的形容因为它排序就像冒泡一样元素是一个一个冒出来的。

从第一个元素开始两两比较根据升序还是降序将大的或小的元素向后移。

如果一次遍历完了都没有发生交换就说明遍历的序列是有序的可以直接跳出。

这样可以提高一点效率但是效率还是比不上其他排序算法。

代码

void

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想是任取待排元素序列中的某元素作为其基准值往往是取第一个元素或者最后一个元素按照该排序码将待排序集合分为左右两个子序列左子序列中的所有元素均小于基准值右子序列中的所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。

递归实现

选出一个key值定义一个L和一个RL向右走R向左走。

需要注意的是如果key值是第一个元素R先走。

如果key值是最后一个元素L先走

R先移动遇到比key值小的就停止然后L开始移动遇到比key值大的停止然后将此时L与R的值交换然后重复以上步骤。

直到L和R相遇此时的值一定是小于key值的然后把它与key交换。

而此时的key值就放在了它应该在的位置同时将序列分成了左右两个子序列。

为什么R和L相遇时的值一定是小于key值的R在遇到小于key值的值时会停止等L移动L移动有两个结果一种是遇到比key值大的两者交换然后R继续移动另一种是没有遇到必key值大的直到相遇这个是比key值小的值。

L在停止前必然是R遇到一个比key小的值停止两者会交换。

所以造成R和L相遇的值一定小于key值的原因是R先走这是非常巧妙的一步。

如果是L先走那必然相遇位置的值是大于key值的此时的key值应该取的是最后一个元素。

代码

void

左子序列[begin,keyI)右子序列(keyI,end]QuickSortHoare(a,

begin,

对于快速排序来说比较的次数是固定的不会超过O(n)那么划分的次数就非常重要了。

如果初始序列是有序的那么此时的排序过程就非常的像冒泡排序时间复杂度为O(n)则最差的情况时间复杂度为O(n2)。

如果每次key值都在中间那么就有点像是二分法则时间复杂度为O(logn)此时的时间复杂度就是O(n*logn)了。

因为使用了递归所以在执行过程中需要在栈中保存相关的信息需要的空间和递归次数有关递归与划分的次数有关系也就是最好是O(logn)最差是O(n)。

图示

挖坑法

挖坑法是基于Hoare的他通过挖坑的方法避免了R和L相遇时的值一定小于key值的问题因为不是所有人都能理解为什么R和L相遇时的值是小于key值的。

但是像Hoare一样它也需要根据key值的选定来决定是R先走还是L先走。

挖坑法一开始会取出key值然后R移动找到比key值小的值把这里的值填到L的位置上随后L开始移动找到比key值大的值填到R的位置上然后R又开始移动重复上述步骤直到R和L相遇最后把key值填入。

代码

void

核心思想并没有什么变化换汤不换药所以时间复杂度与Hoare版本是一样的。

图示

前后指针版本

这个是Hoare的一种变形还是取一个key值然后取prev和cur分别指向第一个元素和第二个元素然后cur向后移动遇到比key小的值cur的值就和prev的值交换遇到比key大的值cur就继续走。

这样prev就两种情况与cur在同一位置或者是停留在值比key值大的位置上最后cur走到end后就把prev与key交换这样也就完成了左右子序列区分的任务。

void

找到比key小的值时与prev位置交换小的向前移动大的向后移动if

(a[cur]

首先我们要知道一个点每次递归都会开辟一次栈帧空间而栈帧空间有一个特点就是先开辟的空间最后销毁但是这也造成了一个问题如果递归层度过深就会栈溢出。

但是快排又依赖于这一先入栈后销毁的特性完成排序。

所以我们要实现非递归的快排就需要实现这一特性而在我们的数据结构中恰好有一个栈的数据结构是具备这种特性的所以如果我们要非递归实现快排就要使用栈这个数据结构。

Hoare版本

找到比key小的值时与prev位置交换小的向前移动大的向后移动if

(a[cur]

我们之前提到过如果每次key值的位置恰好在最边上那么快排的的时间效率就会变成O(n2)虽然这样的概率很小但是还是有概率会出现。

这时我们可以采用三值取中法来避免这种的情况发生。

因为key值是影响划分次数的关键三值取中就是找到首、中、尾三个位置的值比较大小将中间大小的值与key值交换这样就能保证key值的位置不会是在最边上。

int

每一层的递归都会以2倍数进行增长即1,2,4,8,16……通过这个数列我们可以发现在逻辑上只要我们减少一层递归就能减少约一半的递归次数。

所以我们可以结合其他排序进行一个判断在只有多少数的时候就采用其他排序这样就能有效的避免递归过深。

void

归并排序是建立在归并操作上的一种有效的排序算法它采用了分治的思想。

将已经有序的子序列合并得到完全有序的序列。

即先使每个子序列有序然后合并成一个有序的序列。

将两个有序表合并成一个有序表叫做二路归并。

归并排序需要先分解在合并。

void

归并排序有点类似二叉树结构高度O(logn)每层循环n次所以时间复杂度O(n*logn)

归并排序额外开辟了n个空间加上递归的logn所以空间复杂度为O(nlogn但是logn是可以忽略掉的最后的复杂度为O(n)。

图示

非递归实现

归并排序的非递归算法并不需要借助栈这个数据结构来实现如果使用了栈反而会非常的麻烦我们只需要控制每次参与合并的元素个数即可最终便能使序列变为有序。

但是我们需要考虑到一些特殊情况因为归并是两两归并的也就是它归并的元素个数是1,2,4,8,16……这样增长的那么如果元素个数不是这样标准的倍数呢这时就会有三种情况。

①最后一个分组中右侧区间元素个数不够此时我们合并序列就需要对这个区间的边界进行控制

②最后一个分组中右侧区间没有元素就是元素刚好只够左侧区间那么我们就不需要对这个分组进行合并因为它本身已经是有序的了

③最后一个分组中左侧区间的元素个数不够那么我们就不需要对该小组进行合并了。

void

归并每组数据个数从1开始因为1个认为是有序的可以直接归并int

rangeN

计数排序又称为鸽巢排序是对哈希直接定址法的变形应用是一种非比较排序。

它先统计相同元素出现的次数然后根据统计的结果将序列回收到原来的序列中。

计数排序适用于数据范围集中的序列此时效率很高但是适用的范围及场景受到限制。

代码

void

它的时间复杂度和空间复杂度都是由它自身元素的区间跨度决定的时间复杂度是O(MAX(n,范围))空间复杂度是O(范围)。

图示

排序算法复杂度及稳定性分析

排序算法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n2)O(n)O(n2)O(1)稳定简单选择排序O(n2)O(n2)O(n2)O(1)不稳定直接插入排序O(n2)O(n)O(n2)O(1)稳定希尔排序O(nlogn)~O(n2)O(n1.3)O(n2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n2)O(nlogn)~O(n)不稳定

数据过大可能会导致栈溢出所以选择非递归的快排和归并排序来测试。

void

clock();printf(InsertSort:%d\n,

end1

begin2);printf(SelectSort:%d\n,

end3

begin4);printf(BubbleSort:%d\n,

end5

begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);