排序

排序的分类：

冒泡排序，快速排序

参考：http://www.cnblogs.com/feixuelove1009/p/6143539.html

知识部分

一、排序介绍

1、内排序和外排序

内排序：排序时，待排序的所有记录都在内存中

外排序：排序时，使用到了外部存储

2、排序按操作划分

插入排序 复杂度：O(n^2)

交换排序 复杂度：O(n^2)

选择排序 复杂度：O(n^2)

归并排序

交换排序和选择排序的复杂度相同，是因为它们的比较次数一样多，但是选择排序比交换排序中的冒泡排序时间短，是因为它的交换次数少得多，而CPU处理交换的速度比处理比较的速度慢。

3、以算法复杂度分为

简单算法：冒泡排序、简单选择排序和直接插入排序

改进算法：希尔排序、堆排序、归并排序和快速排序

重点是这七种经典排序算法

4、排序的稳定性

如果原序列之中有两个相同的元素，例如A[i] = A[j]，它们在排序前的序号分别是i和j，且i<j，如果排序完成之后，i<j依旧成立，那么说明排序是稳定。

二、冒泡排序

示例：

4, 3, 2, 1
第一次： 4, 3, 1, 2 -> 4,1,3,2 -> 1,4,3,2
...

虽然可以用python写出冒泡排序的算法，但感觉没有什么意义。因为只要你能制定出比较两者“大小”的方式，就可以使用sort(list，key=func)来实现。说起来，我倒是对python中原有的排序机理产生了兴趣。因为它涉及到了合并排序和插入排序，那就先看一下这两种排序。

三、直接插入排序

原文的代码太奇怪了，我自己写一个吧

def insert_sort(lis):
    length = len(lis)
    if not length:
        return []
    result = [lis[0]]
    for i in range(1, length):
        for j in range(len(result)):
            if lis[i] < result[j]:
                result.insert(j, lis[i])
                break
            if j == len(result)-1:
                result.insert(j+1, lis[i])
    return result

四、归并排序

感觉这个名字起得不好啊，是不是分并排序更好些？原文代码一大段，看得又头疼又无聊，所以下面还是我自己写的

def merge_sort(lis):
    # 分
    length = len(lis)
    # 长度为2或1时的排序
    if length == 1:
        return lis
    elif length == 2:
        return lis if lis[0] < lis[1] else lis[::-1]
    if length % 2 == 0:
        mid = length // 2

    else:
        mid = (length - 1) // 2
    a = merge_sort(lis[0:mid])
    b = merge_sort(lis[mid:])
    # 合并
    i = 0
    j = 0
    new = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            new.append(a[i])
            i += 1
        else:
            new.append(b[j])
            j += 1
    new += a[i:] + b[j:]
    return new

简单来说就是，使用迭代的方式先拆后合并。但是关于拆分的最小单位如何确定效率才比较高，这点我还不清楚。

三、Timsort

Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序，现在Java SE7和Android也采用Timsort算法对数组排序。

习题部分

一、数组（列表）排序

1、对于数字排序，用list.sort()方法或者sorted方法都可以，如果非要实现的话，基本与字母排序一样

2、字母排序

['-', '-', '+', '+', '+','-', '+','-', '+','-','-']

网上看到的一种解答是

def StringSort(data):
    startindex = 0
    endindex = 0
    count = len(data)
    while startindex + endindex < count:
        if data[startindex] == '-':
            data[startindex], data[count - endindex - 1] = data[count - endindex - 1], data[startindex]
            endindex += 1
        else:
            startindex += 1
    return data

data = ['-', '-', '+', '+', '+','-', '+','-', '+','-','-']
print(StringSort(data))

点评：我觉得毫无意义，数字排序不用说了，内置方法几乎可以帮你完成所有的排序方式包括自定义，而这种字母排序，我实在不能理解其中的意义。假设只有两个符号，一种排前面，一种排后面，完全可以使用以下方法

def StringSort(data):
    count_1 = data.count('+')
    count_2 = data.count('-')
    result = ['+' for i in range(count_1)] + ['-' for j in range(count_2)]
    return result

data = ['-', '-', '+', '+', '+','-', '+','-', '+','-','-']
print(StringSort(data))

结果丝毫不差，没错这不是排序，但这解决了排序问题。