《各种排序算法总结.doc》由会员分享，可在线阅读，更多相关《各种排序算法总结.doc（12页珍藏版）》请在三一文库上搜索。
1、各种排序算法总结排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不 同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。下面这个表格总结了各种排序算法的复杂度与稳定性：Si册序O(n2)O(T?)O(n)0(O0(n2)0(n20(1)0()O(loffn)丁诵走0并沪O(nlntjn)O(l|O(nlcffn)OfnfiDTi)0(1)卜绽昨;网E呼O(mj) 10(1)下號O(lngaB)0(吨朋)二受枉1扌丰带O(n/ogn)?(T1】谢走O(rt + k 11O(n + kO(n - k)各种排序算法复
2、杂度比较.png冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为0(nA2)，其优点是实现简单，n较小时性能较好。*算法原理相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来， 最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数 据排序完成C+代码实现1.voidbubble_sort(int arr,int len)2.3.for ( inti =0; i = i; j-)6.7.if (arrj arrj -1)8.9.inttemp =arrj;10.arrj=arrj -1;11.arrj -1 = temp;12. 13. 1
3、4. 15. 选择排序*算法原理先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然 后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序 列的末尾。以此类推，直到所有元素均排序完毕。*C+代码实现1.voidselec;t_sort(int arr,intlen)2.3.for(inti =0; i len; i+)4.5.intin dex = i;6.for(int j = i +1; j len; j+)7.8.if (arrj arri ndex)9.in dex =j;10.11.if(in dex != i)12.13.int temp = arri;14
4、.arri = arri ndex;15.arrin dex = temp;16.17.18. 插入排序*算法原理将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元 素，依次将无序的元素插入到有序部分， 直到所有元素有序。插入排序又 分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排 序。它是稳定的排序算法，时间复杂度为 0(n A2)C+代码实现1.voidin sert_sort(int arr,int len)2.3.for(int i =1; i -1 & k arrj)8.9.arrj +1 = arrj;10.11.12.arrj +1 = k;int
5、k = arri;13.14.快速排序*算法原理快速排序是目前在实践中非常高效的一种排序算法， 它不是稳定的排序算法，平均时间复杂度为0(nlogn)，最差情况下复杂度为0(nA2)。它的基 本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部 分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这两 部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个 数据变成有序序列。C+代码实现1. void quick_sort(int arr,int left,int right)2. 3.if(left right)4.5.int i = left, j = ri
6、ght, 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.arri = target;19.quick_sort(arr, left, i -1);20.quick_sort(arr, i +1, right);21. 22. 归并排序1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.算法原理归并排序具体工
7、作原理如下(假设序列共有n个元素)：o将序列每相邻两个数字进行归并操作(merge)，形成floor(n/2) 个序列，排序后每个序列包含两个元素o将上述序列再次归并，形成floor( n/4)个序列，每个序列包含四个元素o重复步骤2,直到所有元素排序完毕归并排序是稳定的排序算法，其时间复杂度为 0(nlogn)，如果是 使用链表的实现的话，空间复杂度可以达到 O(1)，但如果是使用 数组来存储数据的话，在归并的过程中，需要临时空间来存储归并 好的数据，所以空间复杂度为O(n)C+代码实现void merge( int arr, int temp_arr, int startndex, int
8、 mid_i ndex, int end_in dex)int i = start_i ndex, j = mid_i ndex +1;1 & j endn dex +1)1)int k =0;while (i arrj) temp_arrk+ = arrj+;elsetemp_arrk+ = arri+;while (i mid_i ndex +temp_arrk+ = arri+;while (j end_in dex +temp_arrk+ = arrj+;1)19. for (i =0, j = startndex; j end_in dex +1；i +, j +)20. arrj
9、= temp_arri;21. 22.23. void merge_sort( int arr, int temp_arr, int start_in dex,int end_in dex)24. 25. if (start_i ndex end_in dex)26. 27. int mid_i ndex = (start_i ndex + end_in dex)/ 2;28. merge_sort(arr, temp_arr, start_i ndex, mid_in dex);29. merge_sort(arr, temp_arr, mid_i ndex +1, end_in dex);
10、30. merge(arr, temp_arr, startndex, midndex, end_in dex);31. 32. 堆排序二叉堆 二叉堆是完全二叉树或者近似完全二叉树，满足两个特性*父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值*每个结点的左子树和右子树都是一个二叉堆当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。堆的存储一般都是数组来存储堆，i结点的父结点下标就为(i - 1) / 2 。它的左右子结 点下标分别为2* i + 1 和2*i + 2 。如第0个结点左右子结点
11、下标分别为1 和2。存储结构如图所示：逻SB结构123025423$50堆结构.png堆排序原理堆排序的时间复杂度为0( nlogn)算法原理(以最大堆为例)o先将初始数据R1.n建成一个最大堆，此堆为初始的无序区 o再将关键字最大的记录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.* pa
12、ram i待调整的数组元素的下标5. * param len 数组的长度6. */7. void heap_adjust( int arr, int i, int len)8. 9. int child;10. int temp;11.12. for (; 2 * i +1 len; i = child)13. 14. child = 2 * i + 1; / 子结点的位置 = 2 *父结点的位置 + 115./ 得到子结点中键值较大的结点16.if (child arrchild)17.child +;18./ 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点19.if(
13、arri =0; i-)38. 39. heap_adjust(arr, i, len);40. 41.42. for (i = len -1; i 0; i-)43. 44. / 将第 1 个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的45.int temp = arr0;46.arr0 = arri;47.arri= temp;48./ 不断缩小调整heap 的范围，每一次调整完毕保证第一个元素是当前序列的最大值49.heap_adjust(arr,0, i);50. 51. 编辑推荐】1. 移动开发者服务联盟第二期线下公开课总结：高效，高效，还是高效！2. Java 习惯用法总结3. 3 年代码总结分享4. 使用 Playground 学习数值算法5. Android 6.0 中的新技术总结