在一个排序工作的执行过程中,如果待排序的记录全部保存在内存,这种工作就称为内排序；针对外存(磁盘、磁带等)数据的排序工作称为外排序。内排序中的归并排序算法是大多数外排序算法的基础。   在考虑算法时,最基本的问题是其时间和空间复杂度。为了在某种合理的抽象层次上考虑它们的时间复杂度和空间复杂度，需要确定关注的基本操作，以其作为时间单位，时间复杂性反映排序过程中这个(或这些)操作的执行次数。还需确定某种抽象的空间单位。   现在要做的是数据记录排序,而且基于关键码比较,比较之后有可能要调整数据记录的位置(顺序)。根据这些情况可以确定两种最重要的基本操作：

  在下面讨论各种算法时,总是以被排序序列的长度(即序列中元素的个数)作为问题规模参数n,讨论在完成整个排序的过程中执行上述两种操作的次数(的量级)。以此作为评价算法效率的度量(时间复杂度)。   理论研究已经得到了一个明确的结论:基于关键码比较的排序问题，时间复杂度是 o ( n l o g n ) o ( n l o g ⁡ n ) o ( n log ⁡ n ) o(nlogn)o(nlog⁡n) o(n\log n) o(nlogn)o(nlog⁡n)o(nlogn)Rj​的前后顺序不变，就称这种排序算法是稳定的。也就是说，稳定的算法能够维持序列中所有排序码相同记录的相对位置。如果一个排序算法不能保证上述条件，它就是不稳定的。   适应性： 如果一个排序算法对接近有序的序列工作得更快,就称这种算法具有适应性。具有适应性的算法也有实际价值，因为实际中常常需要处理接近排序的序列。

https://blog.csdn.net/u012864854/article/details/79404463

https://blog.csdn.net/weixin_41725746/article/details/90300689   使用双重for循环，内层变量为i， 外层为j，在内层循环中不断的比较相邻的两个值（i, i+1）的大小，如果i+1的值大于i的值，交换两者位置，每循环一次，外层的j增加1，等到j等于n-1的时候，结束循环。

arr = [7, 4, 3, 67, 34, 1, 8] bubble_sort(arr) print(arr) # [1, 3, 4, 7, 8, 34, 67]

https://blog.csdn.net/llzk_/article/details/51628574   插入排序是将一组数据分成有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少，直到待插入组元素个数为0。在插入过程中涉及到了元素的移动。为了排序方便，一般将数据第一个元素视为有序组，其他均为待插入组。 时间复杂度：

  排序以从小到大排序为例，元素0为第一个元素，插入排序是从元素1开始，尽可能插到前面。插入时分插入位置和试探位置，元素i的初始插入位置为i，试探位置为i-1，在插入元素i时，依次与i-1,i-2······元素比较，如果被试探位置的元素比插入元素大，那么被试探元素后移一位，元素i插入位置前移1位，直到被试探元素小于插入元素或者插入元素位于第一位。

lst1 = raw_input().split() lst = [int(i) for i in lst1] #lst = input() select_sort(lst) for i in range(len(lst)): print lst[i],

https://www.cnblogs.com/chengxiao/p/6104371.html   希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。   希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。   希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。   我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。 时间复杂度： 希尔排序的复杂度和增量序列是相关的：

lst1 = raw_input().split() lst = [int(i) for i in lst1] #lst = input() shell_sort(lst) for i in range(len(lst)): print lst[i],

https://blog.csdn.net/yuzhihui_no1/article/details/44258297   整个排序主要核心就是堆化过程，堆化过程一般是用父节点和他的子节点进行比较，取最大的孩子节点和其进行交换；但是要注意这应该是个逆序的，先排序好子树的顺序，然后再一步步往上，到排序根节点上。然后又相反（因为根节点也可能是很小的）的，从根节点往子树上排序。最后才能把所有元素排序好；具体的操作可以看代码，也可以看看下面的图示： 时间复杂度：   假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

  那么总的时间计算为： s = 2 ( i − 1 ) ∗ ( k − i ) s = 2 ( i − 1 ) ∗ ( k − i ) s = 2 ( i − 1 ) ∗ ( k − i ) s=2(i−1)∗(k−i)s=2(i−1)∗(k−i) s = 2^{( i - 1 )} * ( k - i ) s=2(i−1)∗(k−i)s=2(i−1)∗(k−i)s=2(i−1)∗(k−i)(2k)