说到排序算法，就不得不提时间复杂度和稳定性！

其实一直对稳定性不是很理解，今天研究python实现排序算法的时候突然有了新的体会，一定要记录下来

稳定性: 　　稳定性指的是 当排序碰到两个相等数的时候，他们的顺序会不会发生交换。其实对于一个整数数列的排序，是否交换元素没有任何影响。 　　但是： 如果有这样一串二元组： ( 2, 5)  (1 ,6 )  ( 2 , 8 ) 　　　　我们要优先按照第一个元素排序，如果相同再按照第二个元素排序 　　　　　　我们先按照第二个元素进行排序之后再按照第一个元素进行排序， 　　　　　　里面有两个元组第一个数据都是2  如果是稳定的，那么第二个元素顺序不会发生改变，，如果不稳定，，那可能就悲剧了，，会让我们的数据排出不是我们想要的结果。 时间复杂度: 　　教科书和网络中流传的概念我觉着实在是有些难理解。我来谈一谈自己的想法。 　　对于一个算法程序，我们可以把每进行一次操作的时间记为一个时间单元，即 一次加法操作是一个时间单元，一次逻辑判断是一个时间单元 　　　　当我们一次算法的执行时间以时间单元为单位，就能得到一个时间函数 T(n)= balbala(n) ,其中n一般代表一个传入的数据，决定了循环的次数或者递归次数，T是关于n的函数。balbala是我想用它来指代一个函数的算式 　　　　比如在c++语言中一个循环:   count = 0; for( int i = 0; i

1 #传入li列表 2 def bubble_sort( li ): 3     n = len(li) #数列里有n个数，下标从0到n-1 4     #一共会发生n-1趟排序过程，限制排序次数，i 从0到n -1 ，记录当前是第i+1次排序 5     for i in range( n-1 ): 6         # 每次排序都会确定一个前面最大的数放在最后， 7         # i从0到n-1，所以经历第i+1次排序之后最后的i+1个数是正确的，只需要把前n-(i+1) 个数进行比较挑换就可以 8         for j in range( n - i - 1): 9             #如果我后面的哥们比我数小，我俩就换数值10             if li[j]>li[j+1]:11                 li[j] , li[j+1] = li[j+1], li[j]12 13 if __name__ == '__main__':14     li = [5,4,3,2,1]15     bubble_sort(li)16     print(li)

选择排序：     对于一个有n个数的数列，     第一次我们从第一个数开始选出所有数中最小的，和第一个数交换数值，这样保证第一个数是最小的     第二次我们从第二个数开始选出第一个数之后最小的数和第二个数交换数值，这样前两个数都在正确位置     。。。     最后一次 我们拿倒数第二个数跟最后一个数比较，把小的放在前面     第一次我们从第1个数开始一直到最后找最小的数     第二次我们从第2个数开始到最后找最小的数     。。。     第i次我们从第i个数开始向后找最小的数     最优时间复杂度:O(n^2)     最坏时间复杂度:O(n^2)     稳定性：不稳定的排序      例如： 5 8 5 2   第一趟排序5和2互换，那么两个5顺序就改变了

1 def select_sort(li): 2     n = len(li) #li列表中有n个数，下标从0到n-1 3     # i从0到n-1 ，我们每次拿下标为i的数跟后面数比较 标记最小的数 4     for i in range( n ): 5         temp = i #用temp做临时标记，没遇见比下标temp更小的数，就用temp标记更小的数的下表 6         # 从temp开始向后找到最后 找最小的数 7         for j in range( temp , n ): 8             #如果我们遇到比temp标记的数更小的，tamp就标记更小的数的下标 9             if li[temp] > li[j] :10                 li[temp] ,li[j] = li[j] , li[temp]11         #这次for循环之后 temp一定标记了i之后的最小的数的下标，我们把最小的数和i位置进行呼唤12         li[i] , li[temp] = li[temp] , li[i]13 14 if __name__ == '__main__':15     li = [5,4,3,2,1]16     select_sort(li)17     print(li)

 

插入排序：     对于一个n个数的数列：     拿出第二个数，跟第一个比较，如果第二个大，第二个就放在第一个后面，否则放在第一个前面，这样前两个数就是正确顺序了     拿出第三个数，跟第二个数比较，如果比第二个数小，就放在第二个数前面，再跟第一个数比，比第一个小就放在第一个前面，这样前三个数就是正确顺序     ....     拿出最后一个数，跟之前的正确顺序进行比较，插入到合适的位置当中。     可以理解成： 每次拿到一个数，他前面都是一个有序的数列，然后，找到我何时的位置，我插入进去     最坏时间复杂度: O(n^2)     最优时间复杂度: O(n)     稳定性：稳定的排序

1 def select_sort(li): 2     n = len(li) #li列表中有n个数，下标从0到n-1 3     # i从0到n-1 ，我们每次拿下标为i的数跟后面数比较 标记最小的数 4     for i in range( n ): 5         temp = i #用temp做临时标记，没遇见比下标temp更小的数，就用temp标记更小的数的下表 6         # 从temp开始向后找到最后 找最小的数 7         for j in range( temp , n ): 8             #如果我们遇到比temp标记的数更小的，tamp就标记更小的数的下标 9             if li[temp] > li[j] :10                 temp = j11         #这次for循环之后 temp一定标记了i之后的最小的数的下标，我们把最小的数和i位置进行互换12         li[i] , li[temp] = li[temp] , li[i]13 14 if __name__ == '__main__':15     li = [5,4,3,2,1]16     select_sort(li)17     print(li)

 

希尔排序：     是对插入排序的升级的版本。(插入排序： 每次拿一个数在前面有序的数列中找到位置进行插入 )     设置一个步长，一般为数列长度的一半。     把数列按照步长分组，每组相同位置的数据进行选择排序，     然后再把步长减小后分组，每组的相同位置元素进行选择排序     一直步长减小到1位置，进行选择排序     此时，数列顺序就排好了     举个例子： 对于数列  8 7 6 5 4 3 2 1     8个元素，我们按4为步长进行分组 分成了   8 7 6 5   4 3 2 1         之后 每组相同位置元素进行插入排序，即把         第一趟 8 4 (每组第一个位置)插入排序 整个数列变成： 4 7 6 5   8 3 2 1          第二趟 7 3 (每组第二个位置)插入排序 整个数列变成:  4 3 6 5   8 7 2 1          第三趟 6 2 (每组第三个位置) 进行插入排序后:       4 3 2 5   8 7 6 1         第四趟 5 1 (每组第四个位置) 进行插入排序后:       4 3 2 1   8 7 6 5     之后步长改为2  进行分组  4 3   2 1   8 7   6 5         第一趟 4 2 8 6(每组第一个数)进行插入排序后整个数列：  2 3   4 1   6 7    8 5         第二趟 3 1 7 5(每组第二个数)进行插入排序后整个数列:   2 1   4 3   6 5    8 7         上述过程是便于理解，但是对于步长为2分组后，实际上的过程是： 4 3   2 1    8 7   6 5          第一次 4 2 比  结果是  2 3   4 1   8 7   6 5          第二次 3 1 比  结果是  2 1   4 3   8 7   6 5          第三次 4 8 比  结果是  2 1   4 3   8 7   6 5          。。。。持续下去          实际上是按下标递增的方式进行的，但是每次只与它相邻组同位置元素进行比较，             分组之后，每组相同位置元素不是一次进行插入排序结束再进行第二个相同位置排序             比较顺序 是按照下表递增的方式进行的，但是比较的数据不是自己相邻的，而是相邻组相同位置的数据     之后 步长改为1 进行分组 每个元素一组 进行插入排序： 1 2 3 4 5 6 7 8     优点：设置步长，似的后边较大的元素能快速移动到前面来，前面大元素能快速移动到后面，省去了很多次比较的过程。     时间复杂度: O(n)< x < O(n^2)     稳定性: 不稳定的排序    按步长分组的时候，如果存在两个相等的数分在不同组里，插入排序后有可能本来在前面的数到后面去了

1 def shell_sort(li ): 2     n = len(li) #li列表中有n个数 下标从0到n-1 3     gep = n//2 #设置初始步长进行分组 4     #当步长大于等于1的时候 一直进行分组的插入排序 5     while gep >= 1 : 6         # 从gep的元素往后 一个一个元素对前面所有组跟自己处于相同位置的数进行插入排序 7         for j in range( gep , n ): 8             i = j   #标记下当前j的位置给i 9             # 这层循环是为了回跳i所在位置，10             # 当一个新元素对前组同位置元素交换后，当前元素还需要跟再往前组的同位置元素比较决定是不是要交换11             # i - gep 能看我当前是不是第一组位置，如果是第一组位置，我前面没有组了，就不循环了，12             # 如果我是第三组，我会跳到前二组再跟第一组的相同位置元素进行比较13             while i - gep >= 0 :14                 #如果当前数比前一组同位置数小，就交换数值15                 if li[i] < li[i-gep] :16                     li[i] , li[i-gep] = li[i-gep] , li[i]17                     #如果我和前一组同位置元素交换了，我需要继续与再往前一组同位置元素比较是否需要交换18                     #这个操作是把我当前位置回跳到上一组的同位置19                     i -= gep20                 #如果没有发生数据交换，说明前面的不用再比较了，前面的一定都比我当前数小，跳出回跳位置的循环21                 else :22                     break23         #修改步长 缩小步长24         gep//=225 26 if __name__ == '__main__':27     li = [5,4,3,2,1]28     shell_sort(li)29     print(li)