#!/usr/bin/python
# -*- coding:UTF-8 -*-
import random

def genList(length):

   '''
      生成指定长度的列表
   '''

   #  print random.randint(0, 1000)
   list = []

   for i in range(length):
       list.append(random.randint(0, 1000))
   return list



def bubbleSort(rdyList):

    '''
       冒泡排序:
       给定列表相邻的二个索引的数据进行比较和交换
       冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度是O(1),原地排序算法
       相同大小的数据在排序前后不改变数据，是稳定排序算法
    '''

    for i in range(rdyList.__len__() -1 ):
        for j in range(rdyList.__len__() -1 - i):
           #最后一位不用比较
           if(j == rdyList.__len__()-1 - i):
                continue
           #最优情况下，是不会进行交换，时间复杂度为O(n)
           #极端情况下，时间复杂度是O(n2),（n-1）!
           if rdyList[j] > rdyList[j+1]:
                rdyList[j],rdyList[j+1] = rdyList[j+1],rdyList[j]

    print "【排序后】" + ' '.join(str(i) for i in rdyList)



def insertionSort(rdyList):
      '''
         插入排序:
           银行叫号,叫到号的站好
           空间复杂度是O(1),原地排序算法
           相同大小的数据在排序前后不改变数据，是稳定排序算法
           平均时间复杂度O(n2)
      '''

      #从第2位开始比较
      for i in range(1 ,rdyList.__len__()): #时间复杂度O(n)
         #待插入数据
         value = rdyList[i]
         #已经排序好的数据长度
         j = 0
         # 查找插入的位置
         for t in range(i ,0, -1):
             if rdyList[t-1] > value:
                # 比插入值要大的，需要索引+1
                rdyList[t] = rdyList[t-1] #最坏复杂度是O(n)
             else:
                #找到插入位置
                j = t                     #最好的复杂度是O(1)
                break
         rdyList[j] = value

      print "【排序后】" + ' '.join(str(i) for i in rdyList)



def selectionSort(rdyList):
     '''
        选择排序:找到最大/小的放到队尾
        空间复杂度是O(1),原地排序算法
        ============================
        不稳定排序算法
        ============================
        时间复杂度O(n2)
     '''
     for i in range(0, rdyList.__len__()-1):
         min = rdyList[i]
         # 找到最小的与当前位置交换
         for j in range(i + 1,rdyList.__len__()):
             if rdyList[j] < min:
                 min_ = rdyList[j]
         rdyList[i], min = min, rdyList[i]

     print "【排序后】" + ' '.join(str(i) for i in rdyList)


def shellSort(rdyList):
    '''
          希尔排序(基于插入排序):
          优化点,跳跃式分组的策略,希尔排序的关键并不是随便的分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，
          实现跳跃式的移动，使得排序的效率提高
          空间复杂度是O(1),原地排序算法
          ============================
          不稳定排序算法
          ============================
          时间复杂度O(n1.5)
    '''
    n = len(rdyList)
    while (n > 0):
       #不断缩小步长
       n = n // 2
       for i in range(n):
         # 分组进行排序
         for j in range(i, len(rdyList), n):
           # 从最后一个完整的分组向前按照步调比较
           value = rdyList[j]
           # 如果后一个比前一个小，将前一个和循环比较，如果后一个比前一个大，则没有比较的必要,下一次步长会继续比较
           if (value < rdyList[j - n]):
               while (value < rdyList[j - n] and j > 0):
                  rdyList[j] = rdyList[j - n]
                  j = j - n
               rdyList[j] = value

    print "【排序后】" + ' '.join(str(i) for i in rdyList)


def mergeSort(rdyList):
    """
    归并排序
    1、将列表拆分
       递归拆分,当结束索引与开始索引一样大的时候,终止递归
    2、用一个新的列表进行合并(每一个分组的左右集合递归比较)
       左右二边的最小值分别依次比较
    参考：https://time.geekbang.org/column/article/41913
     空间复杂度是O(n)？？？谁能教教我怎么分析
     ============================
     不稳定排序算法
     ============================
     时间复杂度O(nlogn)？？？谁能教教我怎么分析
    :param rdyList:
    :return:
    """
    rdyList = merge_sort(rdyList,0,len(rdyList)-1)

    print "【排序后】" + ' '.join(str(i) for i in rdyList)


def merge_sort(ls, idx_start, idx_end):
    # 递归终止条件,当索引下标相等时,返回分拆列表
    if idx_end == idx_start : return ls[idx_start:idx_end+1]
    # 取中间值,继续拆解列表
    mid = (idx_start + idx_end) // 2
    left = merge_sort(ls, idx_start, mid)
    right = merge_sort(ls, mid+1, idx_end)
    # 进行列表合并
    i, j = 0, 0
    res = []
    while i < len(left) and j < len(right):
        #左边列表的第一个值和右边列表的第一个值比较
        if left[i] <= right[j]:
            res.append(left[i])
            #较小的值入库完毕后,下次比较是下一个索引值
            i += 1
        else:
            res.append(right[j])
            j += 1
    # 将左/右列表剩下的数据都是最大值
    if i < len(left):
     res.extend(left[i:])
    elif j < len(left):
     res.extend(right[j:])
    return res

def fastSort(rdyList):
    """
    快速排序
    1、找到一个参照物
    2、递归按照参照物将数据分组
    参考：https://time.geekbang.org/column/article/41913
    快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均时间复杂度是O(nlogn)
    :param rdyList:
    :return:
    """
    fast_sort(rdyList, 0, len(rdyList)-1)

    print "【排序后】" + ' '.join(str(i) for i in rdyList)

def fast_sort(ls, idx_start, idx_end):
    if idx_end <= idx_start : return
    #选择最后一个元素为比较
    pivot = idx_end
    i = idx_start
    for j in range(i, idx_end+1):
        #如果小于 pivot，则将其加入到已处理区间的尾部，也就是i的位置
        if ls[j] <= ls[pivot]:
            ls[i], ls[j] = ls[j], ls[i]
            # 当找到最后一个元素的时候，重新设置比较对象
            if j == pivot:
                pivot = i
            i += 1
    fast_sort(ls, idx_start, pivot-1)
    fast_sort(ls, pivot+1, idx_end)

def main():
    rdyList = genList(10)
    print "【排序前】" + ' '.join(str(i) for i in rdyList)
    # 冒泡排序
    # bubbleSort(rdyList)
    # # 插入排序
    # insertionSort(rdyList)
    # # 选择排序
    # selectionSort(rdyList)
    # 希尔排序
    # shellSort(rdyList)
    # 归并排序
    # mergeSort(rdyList)
    # 快速排序
    fastSort(rdyList)


if __name__ == "__main__":
    main()