各种排序方法复杂度总结

《各种排序方法复杂度总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、精品文档各种排序方法复杂度总结在C中，排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，接下来小编搜集了各种排序方法复杂度总结，欢迎查看。一、冒泡排序主要思路是：通过交换相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。代码实现voidbubble_sort（intarr[]，intlen）{for（inti=0;i{for（intj=len—1;j>=i;j——）{if（arr[j]{inttemp=arr[j];arr[

2、j]=arr[j—1];arr[j—1]=temp;}}}2016全新精品资料-全新公文范文-全程指导写作–独家原创8/8精品文档}冒泡排序改进1：在某次遍历中，如果没有数据交换，说明整个数组已经有序，因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。冒泡排序改进2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序。因此设置标志位记录每次遍历中最后发生数据交换的位置可以确定下次循环的范围。二、直接插入排序主要思路是：每次将一个待排序的数组元素，插入到前面已排序的序列中

3、这个元素应该在的位置，直到全部数据插入完成。类似扑克牌洗牌过程。代码实现void_sort（intarr[]，intlen）{for（inti=1;i{intj=i—1;intk=arr[i];while（j>—1&&k{2016全新精品资料-全新公文范文-全程指导写作–独家原创8/8精品文档arr[j+1]=arr[j];j——;}arr[j+1]=k;}}三、直接选择排序主要思路是：数组分成有序区和无序区，初始时整个数组都是无序区，每次遍历都从无序区选择一个最小的元素直接放在有序区最后，直到排序完成。代

4、码实现voidselect_sort（intarr[]，intlen）{for（inti=0;i{intindex=i;for（intj=i+1;j{if（arr[j]index=j;}if（index！=i）{inttemp=arr[i];2016全新精品资料-全新公文范文-全程指导写作–独家原创8/8精品文档arr[i]=arr[index];arr[index]=temp;}}}四、快速排序主要思路是：“挖坑填数+分治法”，首先令i=L;j=R；将a[i]挖出形成打一个坑，称a[i]为基准数。然后j—

5、—从后向前找到一个比基准数小的数，挖出来填到a[i]的坑中，这样a[j]就形成了一个新的坑，再i++从前向后找到一个比基准数大的数填到a[j]坑中。重复进行这种挖坑填数，直到i=j。这时a[i]形成了一个新的坑，将基数填到a[i]坑中，这样i之前的数都比基准数小，i之后的数都比基准数大。因此将数组分成两部分再分别重复上述步骤就完成了排序。代码实现voidquick_sort（intarr[]，intleft，intright）{if（left{inti=left，j=right，target=arr[lef

6、t];while（i{2016全新精品资料-全新公文范文-全程指导写作–独家原创8/8精品文档while（itarget）j——;if（iarr[i++]=arr[j];while（ii++;if（iarr[j]=arr[i];}arr[i]=target;quick_sort（arr，left，i—1）;quick_sort（arr，i+1，right）;}}五、希尔排序主要思路是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待

7、整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”。六、归并排序主要思路是：2016全新精品资料-全新公文范文-全程指导写作–独家原创8/8精品文档当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。代码实现voidmerge（intarr[]，inttemp_arr[]，intstart_index，intmid_

8、index，intend_index）{inti=start_index，j=mid_index+1;intk=0;while（i{if（arr[i]>arr[j]）temp_arr[k++]=arr[j++];elsetemp_arr[k++]=arr[i++];}while（i{temp_arr[k++]=arr[i++];}while（jtemp_arr[k++]=arr[j++];for（i=0，j=st