各种排序算法总结

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 < len -1; i+)4.5.for (int j = len -1; j >= i; j-)6.7.if (arrj < arrj -1)8.9.i

3、nttemp =arrj;10.arrj=arrj -1;11.arrj -1 = temp;12. 13. 14. 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 &l

4、t; arri ndex)9.in dex =j;10.11.if(in dex != i)12.13.int temp = arri;14.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.fo

5、r(int i =1; i < len; i +)4.5.int j = i -1；6.7.while(j > -1 && k < arrj)8.9.arrj +1 = arrj;10.11.12.arrj +1 = k;int k = arri;13.14.快速排序*算法原理快速排序是目前在实践中非常高效的一种排序算法， 它不是稳定的排序算法，平均时间复杂度为0(nlogn)，最差情况下复杂度为0(nA2)。它的基 本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部 分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这两 部分数据分

6、别进行快速排序，整个排序过程可以递归进行，以此达到整个 数据变成有序序列。C+代码实现1. void quick_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 < j && arrj >target)9.j-;10.if (i < j)11.arri+ = arrj;12.13.while (i < j && arri<

7、; 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. 归并排序..8.算法原理归并排序具体工作原理如下(假设序列共有n个元素)：o将序列每相邻两个数字进行归并操作(merge)，形成floor(n/2) 个序列，排序后每个序列包含两个元素o将上述序列再次归并，形成floor( n/4)个序列，每个

8、序列包含四个元素o重复步骤2,直到所有元素排序完毕归并排序是稳定的排序算法，其时间复杂度为 0(nlogn)，如果是 使用链表的实现的话，空间复杂度可以达到 O(1)，但如果是使用 数组来存储数据的话，在归并的过程中，需要临时空间来存储归并 好的数据，所以空间复杂度为O(n)C+代码实现void merge( int arr, int temp_arr, int startndex, int mid_i ndex, int end_in dex)int i = start_i ndex, j = mid_i ndex +1;1 && j < endn dex +1)1)i

9、nt k =0;while (i < mid_i ndex +if (arri > 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 = temp_arri;21. 22.23. void merge_sort( int

10、 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);30. merge(arr, temp_arr, startndex, mi

11、dndex, end_in dex);31. 32. 堆排序二叉堆 二叉堆是完全二叉树或者近似完全二叉树，满足两个特性*父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值*每个结点的左子树和右子树都是一个二叉堆当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。堆的存储一般都是数组来存储堆，i结点的父结点下标就为(i - 1) / 2 。它的左右子结 点下标分别为2* i + 1 和2*i + 2 。如第0个结点左右子结点下标分别为1 和2。存储结构如图所示：逻SB结构123025423$50堆结

12、构.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.* param i待调整的数组元素的下标5. * param len 数组的

13、长度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 < len -1 && arrchild +1 > arrchild)17.child +;18./ 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换

14、它的父结点19.if(arri < arrchild)20.21.temp =arri;22.arri =arrchild;23.arrchild = temp;24.25.else26.break ;28. 29.30. /*31. * 堆排序算法32. */33. void heap_sort( int arr, int len)34. 35. int i;36. / 调整序列的前半部分元素， 调整完之后第一个元素是序列的最大的元素37. for ( int i = len /2 - 1; i >=0; i-)38. 39. heap_adjust(arr, i, len);40. 41.42. for (i = len -1; i >0; i-)43. 44. / 将第 1 个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的45.int t