各种排序方法复杂度总结

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

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

2、iarr[j]）　　temp_arr[k++]=arr[j++];　　else　　temp_arr[k++]=arr[i++];　　}　　while（i

3、arr[]，inttemp_arr[]，intstart_index，intend_index）　　{　　if（start_index

4、index，end_index）;　　}　　}　　七、堆排序　　堆排序的难点就在于堆的的插入和删除。　　堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。　　堆的删除就是——堆的删除就是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点开始将一个数据在有序

5、数列中进行“下沉”。　　因此，堆的插入和删除非常类似直接插入排序，只不是在二叉树上进行插入过程。所以可以将堆排序形容为“树上插”。