快速排序算法详细图解 快速排序法c语言?
浏览量:2418
时间:2021-03-14 01:43:28
作者:admin
快速排序法c语言?
快速排序是基于分治技术的重要排序算法,排序算法按照元素的值对它们进行划分。
划分是对给定数组中的元素的重新排序,使得A [ s ] A[s]A[s]左边的元素都小于等于A [ s ] A[s]A[s],而右边A [ s ] A[s]A[s]右边的元素都大于等于A [ s ] A[s]A[s]。
显然,建立了一个划分以后,A [ s ] A[s]A[s]已经位于它在有序数组中的最终结果,接下来我们可以继续对A [ s ] A[s]A[s]前和A [ s ]A[s]A[s]后的子数组分别进行排序(例如,使用同样的方法)。
注意,它和合并排序不同之处在:
在合并排序算法中,将问题划分为两个子问题,是很快的,算法的主要工作在于合并子问题的解;
在快速排序中,算法的主要工作在于划分阶段,而不需要再去合并子问题的解了。
在快速排序、堆排序、归并排序中,什么排序是稳定的?
- 归并排序是稳定的“快速排序和堆排序都不稳定.不稳定:就是大小相同的两个数,经过排序后,最终位置与初始位置交换了。
- 快速排序:27 23 27 3以第一个27作为pivot中心点,则27与后面那个3交换,形成3 23 27 27,排序经过一次结束,但最后那个27在排序之初先于初始位置3那个27,所以不稳定。
- 堆排序:比如:3 27 36 27,如果堆顶3先输出,则,第三层的27(最后一个27)跑到堆顶,然后堆稳定,继续输出堆顶,是刚才那个27,这样说明后面的27先于第二个位置的27输出,不稳定。”“2 归并排序(MergeSort)
- 归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。”
- 以Ai与Aj为例子快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_indexij都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。
- 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。