人工智能常用的29种算法_8种常用排序算法总结(1)

先总结一下算法的时间复杂度

此文章只对前4种算法做总结

一. 冒泡排序(BubbleSort)

基本思想：

两个数比较大小，较大的数下沉，较小的数冒起来。

过程：

比较相邻的两个数据，如果第二个数小，就交换位置。

从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。

继续重复上述过程，依次将第2.3...n-1个最小数排好位置。

平均时间复杂度：O(n2)

java代码实现：

优化：

针对问题

数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

方案

设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。

这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

实例

二. 选择排序(SelctionSort)

基本思想：

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；

第二次遍历n-2个数，找到最小的数值与第二个元素交换；

。。。

第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

过程：

选择排序

平均时间复杂度：

O(n2)

java代码实现：

三. 插入排序(Insertion Sort)

基本思想：

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

过程：

插入排序

相同的场景

平均时间复杂度：

O(n2)

java代码实现：

四. 希尔排序(Shell Sort)

前言：

数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;

数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;

如果数据序列基本有序，使用插入排序会更加高效。

基本思想：

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。

然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

过程：

希尔排序

平均时间复杂度：

O(n1.5)

java代码实现：