常见排序算法总结

一、冒泡排序(Bubble Sort

冒泡排序是一种in-place的排序算法,它的时间复杂度是O(n2)最好情况下与最坏情况下的时间复杂度都是O(n2)。

java实现:

二、插入排序(Insertion Sort

插入排序是一种in-place的排序算法,它的时间复杂度是O(n2)最好情况下它的时间复杂度是O(n)最差情况下它的时间复杂度是O(n2)。

java实现:

三、选择排序(Selection Sort

选择排序是一种in-place的排序算法,它的时间复杂度是O(N2),最优的时间复杂度是O(n2),最差的时间复杂度也是O(n2)。选择排序的基本思想是每次从序列中找出最小的元素并将它排在已排序序列的末尾。

java实现:

四、归并排序(Merge Sort

并归排序是分治法(Divide and conquer)的典型应用。并归排序是一种in-place的排序算法。算法的时间复杂度是O(nlogn),最优的时间复杂度是O(n),最差的时间复杂度是O(nlogn)。并归排序最差的空间复杂度是O(nlogn)。

五、快速排序(Quick Sort

快速排序采用分治法,它不是一种in-place的排序算法。但是因为它的内部循环(inner loop)可以在大多数平台上很有效率的实现出来,所以它比大多数时间复杂度为O(nlogn)的算法要快。快速排序的时间复杂度是O(nlogn),最优的时间复杂度O(nlogn),最差时间复杂度O(n2),最差时间复杂度的情况并不常见。


六、希尔排序(Shell Sort

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注