常见的排序python实现

#时间复杂度o(n**2) 空间复杂度o(1)
#思路后面的元素插入前面已经排序好的序列里,稳定

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

 

def insert_sort(data):
    length_data = len(data)
    for i in range(1,length_data):
        temp = data[i] #插入第i位置的数
        j = i-1
        while j >= 0 and temp < data[j]:#如果大于则后移
            data[j+1] = data[j]
            j -= 1
        data[j+1] = temp
    return data

2. 插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

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

希尔排序的示例：

#希尔排序，只是特殊的插入排序 ，为了解决插入排序的特殊情况
def shell_insert(data,start,gap):
    length_data = len(data)
    for i in range(start+gap,length_data,gap):
        temp = data[i]
        j = i - gap
        while j >=0 and temp < data[j]:
            data[j + gap] = data[j]
            j -= gap
        data[j + gap] = temp
def shell_sort(data):
    gap = len(data)//2
    while gap > 0:

        shell_insert(data,0,gap)
        gap = gap//2
    return data

3. 选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

 

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

#简单的选择排序
def option_sort(data):
    length_data = len(data)
    for i in range(length_data-1):
        min_index = data.index(min(data[i:]))
        if data[min_index] < data[i]:
            data[min_index],data[i] = data[i],data[min_index]
        else:
            continue
    return data

5. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

 

#冒泡排序
def bubing_sort(data):
    length = len(data)
    for i in range(length):
        exchange = 0
        print(i)
        for j in range(length - i - 1):
            if data[j] > data[j + 1]:
                data[j],data[j+1] = data[j+1],data[j]
                exchange = 1
        if exchange == 0: #如果已经完全排序好了，则就停止
            break

    print(data)
    return data

6. 交换排序—快速排序（Quick Sort）

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：

（a）一趟排序的过程：

（b）排序的全过程

#只是完成一次的快速排序 
def partion(data,left,right):
    key = data[left]
    low = left
    high = right
    while low < right:
        while low < high and data[high] >= key:
            high -= 1
        data[low] = data[high] #一但出现了比key小则放到key的位置
        while low < high and data[low] <= key:
            low += 1
        data[high] = data[low] #出现了比key大放到上边腾出的位置上
        data[low] = key
    return low
def quick_sort(data,left,right):
    if left < right:
        p = partion(data,left,right)
        partion(data,left,p-1)
        partion(data,p+1,right)
    return data