排序算法

排序算法是最基本是算法，通常是解决其他问题的第一步，需要进行结果验证，也要评估排序算法的性能，性能主要看两个方面：运行时间和额外的内存使用（即时间复杂度和空间复杂度）。
对于非基本数据类型的分组，需要让该数据类型实现Comparable接口，该数据类型中要实现一个comparaTo()方法来定义自然次序，这个方法必须实现一个完整的比较序列，即满足：

自反性，对所有的V都有V=V；
反对称性，对于所有的V

初级排序算法

主要有选择排序，插入排序，交换排序

  • 选择排序
    一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第 一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中 找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法 叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

  • 直接选择排序
    有两个鲜明的特点：
    运行时间与输入无关，一个已经有序的数组或 是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长！，其 他算法会更善于利用输入的初始状态
    数据移动是最少的，每次交换都会改变两个数组元素的值，因此选择排序用了N次交换——交 换次数和数组的大小是线性关系。我们将研究的其他任何算法都不具备这个特征（大部分的增长数 量级都是线性对数或是平方级别）。

  • 插入排序
    插入排序的意思就是说，我们把数据分成两个部分，一部分是已经排好序的数据，一部分是当前还没有完成排序的数据。那么这么说来的话，排序的过程是不是就是把没有排序的数据逐个插入到已经排好序的队列中的过程呢。
    与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给 更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。
    和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大 且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

  1. 下面是几种典型的部分有序的数组： ?

  2. 数组中每个元素距离它的最终位置都不远； ?

  3. 一个有序的大数组接一个小数组； ?
    数组中只有几个元素的位置不正确。 插入排序对这样的数组很有效，而选择排序则不然。事实上，当倒置的数量很少时，插入排序 很可能比本章中的其他任何算法都要快

  • 直接插入排序
    与自身比较的话，第一轮有序的只有一个元素也就是第一个元素，要从第二个元素开始往前逐一比较。也就是说，第一轮会帮第二个元素找到正确的位置，以此类推，第N轮帮第N+1个元素找到正确的位置，每一轮都需要比较1次到N次。

  • Shell排序
    对于大规模乱序数组，直接插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组 的一端移动到另一端。
    希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。
    iOS培训,Swift培训,苹果开发培训,移动开发培训

希尔排序，可以看成是冒泡排序的变种。它的基本思想是：首先按照一个序列递减的方法逐渐进行排序。比如说有10个数据，我们按照序列5、3、1的顺序进行排序。首先是5，那么我们对1和6、2和7、3和8、4和9、5和10进行排列；第二轮是3，那么对数据1、4、7、10排列，再对2、5、8进行排列，以及3、6、9排列；第三轮就和冒泡排序一样了，以此对每个数据进行排列。它的优势就是让整个队列基本有序，减少数据移动的次数，从而降低算法的计算复杂度。