C语言中快速排序和插入排序优化的实现
快速排序
快速排序思想
1962年,由C.A.R.Hoare创造出来。该算法核心思想就一句话:“排序数组时,将数组分成两个小部分,然后对它们递归排序”。然而采取什么样的策略将数组分成两个部分是关键,想想看,如果随便将数组A分成A1和A2两个小部分,即便分别将A1和A2排好序,那么A1和A2重新组合成A时仍然是无序的。所以,我们可以在数组中找一个值,称为key值,我们在把数组A分解为A1和A2前先对A做一些处理,让小于key值的元素都移到其左边,所有大于key值的元素都移到其右边。这样递归排序A1和A2,数组A就排好了。
举例
我们要排序的数组如下:
55 41 59 26 53 58 97 93
我们选取第一个元素作为key值,即55.(一般都是选取第一个元素)。假如我们有一种办法可以将数组做一步预处理,让小于key值的元素都位于其左边,大于key值的元素都位于其右边,预处理完数组如下:
41 26 53 55 59 58 97 93
这样数组就被key值划分成了两段,A[0...2]小于key,A[4...7]大于key,可见key值本身已排好序,接下来对A[0...2]和A[4...7]分别进行递归排序,那么整个数组就排好序了。预处理做的工作再次澄清下:找一个key值,把key位放到某位置A[p],使小于key值的元素都位于A[p]左边,大于key值的元素都位于A[p]的右边。到此,我们的快排模型就成型了。
/*l, u 代表待排序部分的下界和上界*/ void qsort(l, u) { /*递归结束条件是待排序部分的元素个数小于2*/ if(l >= u) { return; } /*此处进行预处理,预处理后key值位于位置p*/ qsort(l, p-1); qsort(p+1, u); }
接下来看如何做预处理。我们选取A[0]做为key值, p作为key值的位置。我们从A[1]开始遍历后面的数组,用变量i指示目前的位置,每次找到小于key的值都与A[++p]交换。开始时p=0.
55 41 59 26 53 58 97 93 i = 1,A[i]位置为41, 即A[i] < key, swap(++p , i),即p = 1:
55 41 59 26 53 58 97 93 i = 2,A[i]位置为59,A[i] > key,不做任何改变。
i = 3,A[i]位置为26,A[i] < key,swap(++p, i), 即p = 2:
55 41 26 59 53 58 97 93 i = 4,A[i]位置为53,A[i] < key,swap(++p, i),p = 3:
55 41 26 53 59 58 97 93 i = 5,A[i]位置为58,A[i] > key,不做任何改变。
i = 6,A[i]位置为97,A[i] > key,不做任何改变.
i = 7,A[i]位置为93,A[i] > key,不做任何改变.结束循环。此时p为key的最终位置。还需一步把key值填入p位置。
最后swap(l, p)即把Key值放到最终位置上了。至于为什么要交换l,p的位置,可以另拿一组数据试一下:55,41,59,26,99,58,97,93。
完整的程序1
/*l, u 代表待排序部分的下界和上界*/
void qsort(int l, int u) { /*递归结束条件是待排序部分的元素个数小于2*/ if(l >= u) { return; } int p = l; for(int i = l+1; i <= u; i++) { if(A[i] < A[l]) { swap(++p, i); } } swap(l, p); qsort(l, p-1); qsort(p+1, u); }
这就是第一代快速排序算法,正常情况下其复杂度为nlogn,但在考虑一种极端情况:n个相同元素组成的数组。在n-1次划分中每次划分都需要O(n)的时间,所以总的时间为O(n^2)。使用双向划分就可以避免这个问题。
双向划分快速排序
/*l, u 代表待排序部分的下界和上界*/ void qsort(int l, int u) { /*递归结束条件是待排序部分的元素个数小于2*/ if(l >= u) { return; } key = A[l] for(int i = l, j = u+1; i <= j;) { do i++ while(i <= u && A[i] < key)); do j-- while(A[j] > key); if(i > j) { break; } swap(i, j); } swap(l, j); qsort(l, j-1); qsort(j+1, u); }
插入排序优化
插入排序的精髓就是首先将第一个元素视为有序子数组x[0...0],然后插入x[1]...x[n-1].思想很简单,代码也很简单,简单的代码有没有优化的空间呢?编程珠玑中提供了几个优化后的方案,效率提高了70%之多。
简单的实现(sort1)
void insertSort(int *array, size_t size) { for(size_t i = 1; i < size; i++) { for(int j = i; j > 0 && array[j - 1] > array[j]; j--) { swap(array[j - 1], array[j]); } } }
优化思路
内循环的swap函数可能不如内联函数快些,所以第一步优化将该swap函数展开,据作者说,展开后效率提高了60%。
优化代码(sort2)
void insertSort(int *array, size_t size) { for(size_t i = 1; i < size; i++) { for(int j = i; j > 0 && array[j - 1] > array[j]; j--) { int t = array[j]; array[j] = array[j - 1]; array[j - 1] = t; } } }
优化思路
由于内循环中总是给变量t赋同样的值(x[i]的初始值),所以内循环关于t的两条赋值语句移出循环,据说这么做的效率又提高了15%。
优化代码(sort3)
void insertSort(int *array, size_t size) { for(size_t i = 1; i < size; i++) { int j = i; int t = array[j]; for(; j > 0 && array[j - 1] > array[j]; j--) { array[j] = array[j - 1]; } array[j] = t; } }
《编程珠玑》书中给出了三种排序的运行时间:
插入排序的效率总是O(n2),效率差在比较的次数以及交换的频率,如果交换的频率减少的话就可以大大提高插入排序的效率,这也是为什么元素基本有序时插入排序效率高的原因。
个人观点
代码调优以及性能优化都可能带来一系列的副作用,比如程序的正确性,可读性,可维护性等。是否需要调优要看问题性质,调优既是华而不实的“花活”,也是一把利刃,区别就在于使用的场合。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- c# n个数排序实现代...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25