排序的稳定性和复杂度

      不稳定：

      选择排序（selection sort）— O(n²)

      快速排序（quicksort）— O(nlogn) 平均时间, O(n²) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序

      希尔排序 （shell sort）— O(nlogn)

  稳定：

      插入排序（insertion sort）— O(n²)

      冒泡排序（bubble sort） — O(n²)

      归并排序 （merge sort）— O(n log n); 需要 O(n) 额外存储空间

 

      每种排序的原理和Python实现

选择排序

      遍历数组，遍历到i时，a₀,a₁...a_i-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。

1 def selection_sort(a):2     for i in range(0, len(a) - 1):3         index = i4         for j in range(i + 1, len(a)):5             if a[index] > a[j]:6                 index = j7         a[i], a[index] = a[index], a[i]

快速排序

      快速排序首先找到一个基准，下面程序以第一个元素作为基准（pivot），然后先从右向左搜索，如果发现比pivot小，则和pivot交换，然后从左向右搜索，如果发现比pivot大，则和pivot交换，一直到左边大于右边，此时pivot左边的都比它小，而右边的都比它大，此时pivot的位置就是排好序后应该在的位置，此时pivot将数组划分为左右两部分，可以递归采用该方法进行。快排的交换使排序成为不稳定的。

1 def patition(l,low,high): 2     left=low 3     right=high 4     pos=l[low] 5     while left
     
      =l[left]: 7             left+=1 8         while pos
     

希尔排序

      希尔排序是对插入排序的优化，基于以下两个认识：1. 数据量较小时插入排序速度较快，因为n和n²差距很小；2. 数据基本有序时插入排序效率很高，因为比较和移动的数据量少。

      因此，希尔排序的基本思想是将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

      希尔排序的时间复杂度和增量的选择策略有关，上述增量方法造成希尔排序的不稳定性。

1 def shellsort(nums):2     step=int(len(nums)/2)3     while step>0:4         for i in range(step,len(nums)):5             if step<=i and nums[i-step]>nums[i]:6                 nums[i-step],nums[i]=nums[i],nums[i-step]7                 i-=step8         step=int(step/2)9     return nums

 

插入排序

      遍历数组，遍历到i时，a₀,a₁...a_i-1是已经排好序的，取出a_i，从a_i-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较是，原来靠后的还是拍在后边，所以插入排序是稳定的。

      当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。

1 def insert_Sort(a): 2     length = len(a) 3     for i in range(1, length): 4         x = a[i] 5         #如果第i个元素小于第j个，则第j个向后移动， 6         for j in range(i, -1, -1): 7             if x < a[j - 1]: 8                 a[j] = a[j - 1] 9             else:10                 #如果不小于，则放在正在比较的元素之后11                 break12         a[j] = x

 冒泡排序

      冒泡排序的名字很形象，实际实现是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。

1 def bubble_sort(a):2     n = len(a)3     for j in range(0, n - 1):4         for i in range(0, n - 1 - j):5             if a[i] > a[i + 1]:6                 a[i], a[i + 1] = a[i + 1], a[i]

归并排序

      归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行.logn.次，因此，总的时间复杂度为O(nlogn)。

     归并排序在归并过程中需 要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。

     归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

1 def merge(a,b): 2     merged=[] 3     i, j = 0, 0 4     while i