选择排序：
首先，找到数组中最小的那个元素，其次，将他和数组中的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将他和数组的第二个元素交换位置。如此往复，知道将整个数组排序。
算法思想：
将序列分为两个部分，有序序列（刚开始时有序序列就是整个序列的第一个元素）和无序序列，总是在无序序列中找到最小的记录放到有序序列的末端，这样有序序列慢慢变大，无序序列中没有元素时，整个排序完成。
算法分析：
排序中最主要的操作是比较和交换，选择排序比较的次数和规模n有关。整个排序比较的次数是
（n-1 ) + (n-2) + (n-3) + ........ + 1 = n(n-1)/2
交换元素的此时是 n 次。
所以排序算法的时间复杂度是 O(N^2)
算法优点：简单容易理解。
算法不足：运行时间和输入无关，哪怕是对一个有序序列进行排序，他的时间复杂度仍然是O(N^2)，造成这一特点的原因是，该算法每次在无序序列中选择最小值时都要进行一次遍历，而这一次遍历对下一次遍历没有提供任何有用的信息。
不稳定排序。
插入排序：
首先以第一个元素作为参照，将第二个元素插入到第一个元素的左边或者右边，然后在将第三个元素插入到【1,2】元素的何时位置，以此类推，直到所有元素都已经插入。
算法思想：动态规划
同样将序列分为两个部分，有序序列（刚开始时有序序列就是整个序列的第一个元素）和无序序列。总是取第一个无序序列的第一个元素，插入到有序序列的合适位置（插入时要保证有序序列继续有序），直到无序序列没有元素时，整个排序完成。
在往有序序列中插入元素的过程中可以有多种处理方式：
1. 直接插入。先插入到有序序列的末尾（其实无序序列的第一个元素就是在有序序列的最后，无需插入），然后依次和前一个元素进行比较和交换（有点像冒泡，上浮）。
2. 折半插入。直接找到插入的位置（一般用二分法查找），将位置后面的所有元素向右移动一位，腾出插入位置。
算法分析：
直接插入：主要操作是比较和交换，每次插入时，需要比较的次数最多是n次（有序序列的规模），最少1次就OK了，取平均n/2次。交换的次数也是一样，最多n次，最少0次。所以直接插入在平均情况下需要比较1/2*(1 + 2 + 3 + ..... + n) = n(n + 1) / 4次，交换1/2*(1 + 2 + 3 + ..... + n) = n(n + 1) / 4次。最坏情况下是n(n + 1) / 2次和n(n + 1) / 2次，最好情况下是需要 n-1 次比较和 0 次交换。所以直接插入排序的时间复杂度是 O(N^2)。
折半插入：主要操作是比较和元素的移动，每次遍历需要先用二分法找到插入位置，二分法查找的比较次数是 log(n),元素移动的次数和直接插入的交换次数一样（但是元素移动比元素交换减少了一般的数组访问）。最好情况下是0次，最差情况下是 n 次，平均情况是 n/2 次。所有折半插入总的比较次数是：log(1) + log(2) + ...... + log(n) = n*log(n) - n 次，总的移动的平均次数是n(n + 1) / 4次，所以折半插入排序的时间复杂度是 O(N^2)。
虽然折半插入排序的时间复杂度和直接插入的相同，但是效率上的差别还是很大的，其一是因为二分法查找减少了比较的次数，其二是因为元素移动比元素交换更快。
算法优点：
1. 可以说插入排序是对选择排序的改进，选择排序每次遍历时都要从无序序列中获取最小值，这样在获取最小值的过程中不能为下一次遍历提供有用的信息。而插入排序每次遍历都是在有序序列中进行，这个有序序列是上一次排序的结果（跟动态规划的概念符合）。也就是说，插入排序中每次遍历为下一次遍历提供有用的信息。这导致以一个结果：如果初始的序列不是随机的，而是有一定的局部有序性，这样插入排序的效率会得到很大的提升。极端情况下，你输入一个有序的序列，插入排序的时间复杂度变为O(n) 而选择排序依然是O(n^2)。
2.插入排序是稳定的排序。
算法不足：依然不是效率最高的排序算法，并且存在大量的数组移动操作，特别是在序列规模比较大时。所以插入排序在序列规模比较大时有很大的优化空间。
两种算法比较：上面已经说的很清楚了，对于随机排序的无重复主键的无序序列，两种排序算法的时间复杂度都是平方级别的，两者这比应该是一个较小的常数。插入排序比选择排序快常数级别。而且插入排序对于那些局部有序的序列排序更快。
冒泡排序
算法思想：
其实冒泡排序是选择排序的一种，前面的选择排序将序列分为两个部分，有序序列和无序序列，总是在无序序列中找到最小的记录放到有序序列的末端，但是并没有说明在无序序列中如何找到最小值。有一种方法是，记录一个临时变量，从头遍历无序序列，和临时变量作比较，然后临时变量记录较小的值，一次遍历下来就能找到最小值。冒泡排序也是一种选择排序，不过他找到最小变量的方式并不是通过临时变量，而是从尾部遍历无序序列，比较相邻的两个元素，较小的放在前面，通过冒泡的方式将最小值移到无序序列的头部。
选择排序的查找最小值伪代码：
int k = 无序序列[0];
for(int i = 0; i < 无序序列.length; i++) {
if(无序序列[i] < k) {
k = 无序序列[i];
}
}
冒泡排序查找最小值伪代码：
for(int i = 无序序列.length - 1; i > 0; i--) {
if(无序序列[i] < 无序序列[i-1]) {
无序序列交换i，i-1的值
}
}
算法分析：
从上面伪代码可以看出，普通选择排序进行了n次比较和一次交换（最小值和第一个元素交换），而冒泡排序最坏情况下进行了n次比较和n次比较，相比普通选择排序效率更低。二者效率比是常数级别的。冒泡排序的的时间复杂度是O(n^2)。冒泡排序有着和普通选择排序相同的不足，他们都是遍历无序序列，没法为下一次遍历提供有效信息。
不过冒泡排序是稳定的。
希尔排序
在理解希尔排序之前，先理解这样一个原理。在一个无序序列中随机取一个子序列，然后对子序列进行排序后再按原位置放回去，不停的执行此操作，只要执行的次数足够多，则原序列就会慢慢的趋近于有序。因为每次的排序都会使原序列更加有序一点。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
算法思想：贪心思想，将大规模的数据分成若干小规模的数据，然后对小规模的数据求局部最优解，然后得到整体最优解。
希尔排序其实是对直接插入排序的一种改进，在分析插入排序时说过，输入的随机序列的有序性对插入排序的效率有很大影响，最好情况下是输入一个有序序列，插入排序的效率提升到O(n)。另外对于插入排序而言，要进行大量的元素移动操作，在规模很大时就很严重影响效率。希尔排序先将序列进行分组，很大程度上减小了序列的规模，分别在分组的子序列上进行插入排序。慢慢的将分组间隔减小，原序列也慢慢的趋近于有序。当分组间隔为 1 时，就相当于对整个序列进行插入排序，此时整个序列已经趋近于有序了，插入排序的效率会趋近于O(n)
希尔排序的时间复杂度是O(n*log(n)) ~ O(n^2) 最好情况是 O(n^1.3) 最差情况是O(n^2)
是不稳定的排序算法。至于复杂度怎么算的不想去想，太复杂了。
网友评论