数据结构排序算法总结

选择排序

插入排序：每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数
据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情
况下将快于冒泡排序。

冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。
堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

选择排序。
选择排序的算法原理是：第一趟从n个待排关键字中找出最小的关键字放到第一个位置，如果要找到最小关键字则必须所有元素都进行比较，所以第一趟要比较n-1次；第二趟从剩下的n-1的元素中再通过n-2次的比较找出最小的元素…………以此类推，不管初始有没有序，它都一共要进行n-1趟排序共n(n-1)/2次比较，时间复杂度始终是O（n平方）
至于其他的，拿插入排序举例：插入排序的基本思想是每次将一个待排的记录按其关键字大小插入到前面已经排好序的子序列中。试想，如果已经排好序的子序列是123，待排记录为45，插入4时，只要和3比较一次就知道排在3后面，对5排序时只要与4比较一次就知道该排在4后面，共比较2次。如果已经排好序的子序列是234，待排记录为15，插入1时，它要从后往前依次比较3次才能找到自己的位置，同样对5排序时只要与4比较一次，共比较4次。由上例可知，插入排序会随着初始数据集的顺序不同而比较次数不同。
BTW，基数排序不是基于关键字比较的排序算法。
纯手打，望采纳，不清楚还可共同探讨。

来这看的是不是都是sdu的...我咋觉得选择排序可以及时终止而最好情况下n-1呢？？？？

一、稳定排序算法
1. 冒泡排序
2. 鸡尾酒排序
3. 插入排序
4. 归并排序
5. 基数排序
6. 合并排序
7. 基数排序
8. 二叉排序树排序
二、不稳定排序算法
1. 选择排序
2. 希尔排序
3. 快速排序
4. 堆排序
5. 平滑排序
6. 快速排序排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特轮亩判别地实现为稳定。做这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
扩展资料：排序算法的分类
1. 通过时间复杂度分类：计算的复杂度（最差、平均、和最好性能），依据列表(list)的大小(n)。一般而言，好的性能是 O(nlogn)，且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。
2. 通过空间复杂度分类：存储器使用量（空间复杂度）（以及其他电脑资源的使用）
3. 通过稳定性分类：稳定的排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。
参考资料来源：百度百科-排序算法