各种排序算法总结研究.docx

各种排序算法总结排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。下面这个表格总结了各种排序算法的复杂度与稳定性：各种排序算法复杂度比较.png冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。算法原理相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成c++代码实现void?bubble_sort(int?arr[],?int?len)?{???????for?(int?i?=?0;?i??len?-?1;?i++)???????{???????????for?(int?j?=?len?-?1;?j?=?i;?j--)???????????{???????????????if?(arr[j]??arr[j?-?1])???????????????{???????????????????int?temp?=?arr[j];???????????????????arr[j]?=?arr[j?-?1];???????????????????arr[j?-?1]?=?temp;???????????????}???????????}???????}?}?选择排序算法原理先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 c++代码实现void?select_sort(int?arr[],?int?len)???{???????for?(int?i?=?0;?i??len;?i++)???????{???????????int?index?=?i;???????????for?(int?j?=?i?+?1;?j??len;?j++)???????????{???????????????if?(arr[j]??arr[index])???????????????????index?=?j;???????????}???????????if?(index?!=?i)???????????{???????????????int?temp?=?arr[i];???????????????arr[i]?=?arr[index];???????????????arr[index]?=?temp;????????????}???????}???}?插入排序算法原理将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2) c++代码实现void?insert_sort(int?arr[],?int?len)???{???????for?(int?i?=?1;?i??len;?i?++)???????{???????????int?j?=?i?-?1;???????????int?k?=?arr[i];???????????while?(j??-1??k??arr[j]?)???????????{???????????????arr[j?+?1]?=?arr[j];???????????????j?--;???????????}???????????arr[j?+?1]?=?k;???????}???}?快速排序算法原理快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 c++代码实现void?quick_sort(int?arr[],?int?left,?int?right)?{???if?(left??right)???{???????int?i?=?left,?j?=?right,?target?=?arr[left];???????while?(i??j)???????{???????????while?(i??j??arr[j]??target)???????????????j--;???????????if?(i??j)???????????????