《各种排序算法总结》由会员分享，可在线阅读，更多相关《各种排序算法总结（8页珍藏版）》请在金锄头文库上搜索。
1、各种排序算法总结排序算法是最基本最常用的算法， 不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中， 才能更好地发挥它们的优势。今天，来总结下各种排序算法。下面这个表格总结了各种排序算法的复杂度与稳定性：各种排序算法复杂度比较.png冒泡排序冒泡排序可谓是最经典的排序算法了， 它是基于比较的排序算法， 时间复杂度为 O(n2) ，其优点是实现简单， n 较小时性能较好。? 算法原理相邻的数据进行两两比较， 小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位， 第二趟也是如此， 如此类推， 直到所有的数据排序完成? c+代码实现1
2、.void bubble_sort(int arr,int len)2.3.for ( int i =0; i = i; j-)6.7.if(arrj arrj -1)8.9.int temp = arrj;10.arrj = arrj -1;11.arrj -1 = temp;12.13.14. 15. 选择排序? 算法原理先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。? c+代码实现1.void select_sort(int arr,int len)2.3.for
3、 ( inti =0; i len; i+)4.5.intindex = i;6.for(intj = i +1; j len; j+)7.8.if(arrj arrindex)9.index = j;10.11.if(index != i)12.13.inttemp = arri;14.arri = arrindex;15.arrindex = temp;16.17. 18. 插入排序?算法原理将数据分为两部分， 有序部分与无序部分， 一开始有序部分包含第 1 个元素，依次将无序的元素插入到有序部分， 直到所有元素有序。 插入排序又分为直接插入排序、 二分插入排序、 链表插入等， 这里只讨论
4、直接插入排序。它是稳定的排序算法，时间复杂度为 O(n2)c+代码实现1.voidinsert_sort(intarr,intlen)2. 3.for( inti =1; i -1 & k arrj )8.9.arrj +1 = arrj;10.j -;11.12.arrj +1 = k;13. 14. 快速排序? 算法原理快速排序是目前在实践中非常高效的一种排序算法， 它不是稳定的排序算法，平均时间复杂度为 O(nlogn) ，最差情况下复杂度为 O(n2) 。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法
5、对这两部分数据分别进行快速排序， 整个排序过程可以递归进行， 以此达到整个数据变成有序序列。? c+代码实现1.voidquick_sort(int arr,int left,int right)2.3.if(left right)4. 5.int i = left, j = right, target = arrleft;6.while (i j)7. 8.while(i target)9.j-;10.if(i j)11.arri+ = arrj;12.13.while (i j & arri target)14.i+;15.if(i j)16.arrj = arri;17. 18. arr
6、i = target;19.quick_sort(arr, left, i -1);20.quick_sort(arr, i +1, right);21. 22. 归并排序? 算法原理归并排序具体工作原理如下（假设序列共有n 个元素）：o 将序列每相邻两个数字进行归并操作（ merge)，形成 floor(n/2) 个序列，排序后每个序列包含两个元素o将上述序列再次归并，形成 floor(n/4) 个序列，每个序列包含四个元素o 重复步骤 2，直到所有元素排序完毕归并排序是稳定的排序算法，其时间复杂度为 O(nlogn) ，如果是使用链表的实现的话，空间复杂度可以达到 O(1) ，但如果是使用
7、数组来存储数据的话， 在归并的过程中， 需要临时空间来存储归并好的数据，所以空间复杂度为 O(n)? c+代码实现1.voidmerge(intarr,int temp_arr,int start_index,int mid_index,int end_index)2.3.inti = start_index, j = mid_index +1;4.intk =0;5.while (i mid_index +1 & j arrj)8.temp_arrk+ = arrj+;9.else10.temp_arrk+ = arri+;11. 12.while(i mid_index +1)13. 14
8、.temp_arrk+ = arri+;15. 16.while(j end_index +1)17.temp_arrk+ = arrj+;18.19.for(i =0, j = start_index; j end_index +1; i +, j +)20.arrj = temp_arri;21. 22.23.voidmerge_sort(int arr,int temp_arr,int start_index,int end_index)24. 25.if(start_index end_index)26. 27.intmid_index = (start_index + end_ind
9、ex)/ 2;28.merge_sort(arr, temp_arr, start_index, mid _index);29.merge_sort(arr, temp_arr, mid_index + 1, e nd_index);30.merge(arr, temp_arr, start_index, mid_inde x, end_index);31. 32. 堆排序二叉堆二叉堆是完全二叉树或者近似完全二叉树，满足两个特性? 父结点的键值总是大于或等于 ( 小于或等于 ) 任何一个子节点的键值? 每个结点的左子树和右子树都是一个二叉堆当父结点的键值总是大于或等于任何一个子节点的键值时为最
10、大堆。 当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。堆的存储一般都是数组来存储堆，i 结点的父结点下标就为 (i 1) / 2。它的左右子结点下标分别为 2 * i + 1 和 2 * i + 2 。如第 0 个结点左右子结点下标分别为和 2。存储结构如图所示：1堆结构 .png堆排序原理堆排序的时间复杂度为O(nlogn)? 算法原理（以最大堆为例）oo先将初始数据 R1.n建成一个最大堆，此堆为初始的无序区再将关键字最大的记录 R1 （即堆顶）和无序区的最后一个记录 Rn 交换，由此得到新的无序区 R1.n-1 和有序区 Rn ，且满足 R1.n-1.keys Rn.keyo 由于交换后新的根 R1 可能违反堆性质，故应将当前无序区R1.n-1 调整为堆。o 重复 2、3 步骤，直到无序区只有一个元素为止。? c+代码实现1. /*2. * 将数组 arr 构建大根堆3.* param arr待调整的数组4. * param i待调整的数组元素的下标5.* param len数组的长度6. */7.voidheap_adjust(intarr,inti,intlen)8. 9. int child;10.inttemp;11.12.for(; 2 * i +1 len; i =
