概述：
由于排序非常重要而且可能非常耗时，所以它已经成为一个计算机科学中广泛研究的课题，
而且人们的确已经研究出一些非常成熟的方法。在这篇文中将看到三个简单排序的算法：
冒泡，选择，插入排序，还有另外两种高级排序算法，希尔和快速排序。插入排序比较重要，
它比冒泡和选择排序有时更有效率，而且对于小规模和基本有序的文件，插入排序算法能比
快速排序算法更为有效。
这篇文中阐述三种简单排序算法，下一篇文中阐述高级排序算法。
从三个角度来阐述算法：代码，执行效率（大O表示法）以及不变性。
不变性：在许多算法中，有些条件在算法执行时是不变的，这些条件被称为不变性。认识
不变性对理解算法是有用的。在一定的情况下它们对调试也有用；可以反复检查不变性是否
为真，如果不是的话就标记出错。
阐述语言：Java
冒泡排序
冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡
排序算法在刚开始研究排序技术时是一个非常好的算法。
代码：
//冒泡排序
public void bubbleSort()
{
int out,in;
for(out = nElms - 1;out > 0;out --)
for(in = 0;in < out; in++)
if(array[in] > array[in + 1])
swap(in,in+1);
}
不变性：它的不变性是指out右边的所有数据项有序，在算法的整个运行过程中这个条件始终为真。
效率：
比较次数：数组中有N个数据项，第一趟排序中有N-1次比较，第二趟有N-2次比较，如此类推，
最后一趟需要1次比较
故比较次数为：（N-1）+ (N-2) + ... + 1 = N(N-1)/2
交换次数为 0 - N(N-1)/2，两个极端情况，完全有序和完全逆序时交换次数分别为0和N(N-1)/2。，
故平均比较次数为：N(N-1)/4
大O表示法要忽略常数，故BubbleSort的时间复杂度为0（N²）
ps:无论何时，只要看到一个循环嵌套在另一个循环里，就可以怀疑这个算法的运行时间为
0(N²)时间级别。
选择排序
算法描述：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全
部待排序的数据元素排完。
与冒泡比较：
交换的复杂度降为0（N），不幸的是比较复杂度仍然保持为0(N²)
代码：
//选择排序
public void selectSort()
{
int out,in,min;
for(out = 0;out < nElms - 1;out ++)
{
min = out;
for(in = out + 1;in < nElms;in ++)
if(array[in] < array[min])
min = in;
swap(min,out);
}
}
不变性：在算法执行过程中，下标小于或等于out的位置的数据项总是有序的。
效率：
比较次数为：N(N-1)/2
交换次数为：N/2
仍然维持在0(N²)。但是如果交换的时间级比比较的时间级大得多时，选择排序实际上是相当
快的。
ps:综上，实际编程中，能用选择排序的时候就不要用冒泡排序，冒泡排序好像只是学习排序
算法的一块垫脚石。
插入排序
算法描述：在未排序序列中，依次循环将元素插入到已排序的序列当中去。知道所有的数据
序列有序。
代码：
//插入排序
public void insertionSort()
{
int out,in;
for(out = 1;out < nElms ; out ++)
{
int temp = array[out];
in = out;
while(in > 0 && array[in - 1] >= temp )
{
array[in] = array[in - 1];
--in;
}
array[in] = temp;
}
}
不变性：在外层循环每趟结束时，比out变量下标号小的数据项都是局部有序的。
效率：
比较次数：每次循环最多的比较次数依次为1,2，......,N-1.最坏情况下和冒泡排序一样，次数为N(N-1)/2，
那平均只有一半数据项进行了比较，故比较次数为N(N-1)/4.
复制次数：复制次数大致等于比较次数，即为N(N-1)/4.
用大O表示法，那仍然维持在O（N²）。
三种算法比较：
从比较次数而言：
冒泡和选择排序的时间复杂度是一样的，而插入排序的效率是冒泡和选择排序的两倍。
从交换（复制）次数而言：
插入排序的效率是冒泡排序的3倍(一次交换的复杂度约等于三次复制，冒泡排序中是要交换，而插入排序时要复制就可以了)。
插入排序相对选择排序而言，如果都转化成复制的效率，选择时间复杂度为：选择排序为(N/2)*3,而插入排序为N(N-1)/4，
并体现不了插入排序的优势。
总结：
除非手边没有算法书可参考，一般情况几乎不太使用冒泡排序。
在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中
最好的选择。在实际应用中插入排序使用时最多的。
原文链接：https://www.qiquanji.com/post/8505.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知