Python 实现的十大经典排序算法

一、需求：

对一个无序数组，根据某个关键字排序；

二、划分方法：

  1. 排序算法划分方法有：稳定性、内外排序、时空复杂度。
  2. 按照稳定性划分：稳定排序：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；而不稳定可能出现在b后面；
  3. 按照内外排序划分，内排序所有操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能完成。

三、常见排序方法

3.1 选择排序（Selection sort）

这种场景最符合人类思维的排序方式，工作原理：首先在未派逊序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，一次类推，直至所有元素均排序完毕。

    ### 选择排序1
    def selection_sort(arr):
        length = len(arr)
        for i in range(length):
            for j in range(i,length):
                if arr[i] > arr[j]:
                    arr[i],arr[j] = arr[j],arr[i]
        return arr

      #选择排序2
      def selection_sort(self,arr):
          length = len(arr)
        
          for i in range(length-1):
              min_index = i
              for j in range(i+1,length):
                  if a[j] < a[min_index]:
                      min_index = j
              arr[i],arr[min_index] = arr[min_index],arr[i]
          return arr      

算法分析：时间负责度，n是数组的长度；

3.2 冒泡算法（Bubble Sort）

冒泡排序时针对相邻元素之间的比较，可以将大的数慢慢“沉底”（数组尾部）。

### 冒泡排序
  def bubble_sort(arr):
      length = len(arr)
      for i in range(length):
          for j in range(1,length-i):
              if arr[j-1] > arr[j]:
                  arr[j-1],arr[j] = arr[j],arr[j-1]
      return arr

算法分析：内排序，时间负责度：

3.3 插入排序（Insert Sort）

插入排序是前面已排序数组中找到插入的位置；

    ### 插入排序：
    def insert_sort(self,arr):
        length = len(arr)
        for i in range(1,length):
            while i>0 and arr[i-1] > arr[i]:
                arr[i-1],arr[i] = arr[i],arr[i-1]
                i -= 1
        return arr

始发分析： 稳定排序，时间负责度：

3.4 希尔排序（Shell Sort）

插入排序的进阶版
算法描述：
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 步骤1：选择一个增量序列，其中；
• 步骤2：按增量序列个数k，对序列进行k 趟排序；
• 步骤3：每趟排序，根据对应的增量，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

    #希尔排序
    def shell_sort(arr):
        length = len(arr)
        
        gap = length // 2
        while gap:
            for i in range(gap,length):
                while i - gap >= 0 and arr[i-gap] > arr[i]:
                    arr[i-gap] ,arr[i] = arr[i],arr[i-gap]
                    i -= gap
            gap //= 2
        return arr