1.内置排序函数

Python的内置函数sorted()和列表的sort()方法是最简单的排序方式。

• sorted()函数返回一个新的排序列表，原列表保持不变。
• sort()方法直接在原列表上进行排序，不返回新列表。

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]  
sorted_numbers = sorted(numbers)  
print(sorted_numbers)  # 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]  
  
numbers.sort()  
print(numbers)  # 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

2.自定义排序逻辑

在Python中，自定义排序逻辑通常通过sorted()函数或列表的sort()方法的key参数来实现。key参数接受一个函数，这个函数会被应用到序列的每个元素上，然后返回的结果将被用来进行比较排序。这个函数通常被称为“键函数”（key function）。

下面是一些使用自定义排序逻辑的示例：

示例一：根据对象的属性排序

假设你有一个自定义类的实例列表，并且你想要根据对象的某个属性来排序这些实例。你可以通过定义一个键函数来实现这一点。

class Person:  
    def __init__(self, name, age):  
        self.name = name  
        self.age = age  
  
# 创建一个Person对象列表  
people = [Person('Alice', 25), Person('Bob', 20), Person('Charlie', 23)]  
  
# 使用sorted()函数和自定义键函数对年龄这个属性进行进行排序  
sorted_people = sorted(people, key=lambda person: person.age)  
  
# 输出排序后的人员列表  
for person in sorted_people:  
    print(person.name, person.age)

在这个示例中，lambda person: person.age是一个键函数，它接受一个Person对象并返回其age属性。sorted()函数使用这个键函数的结果来对people列表进行排序。

示例二：根据复杂条件排序

有时你可能需要根据多个条件或更复杂的逻辑来进行排序。你可以通过在键函数中实现这些逻辑来实现这一点。

# 假设你有一个字典列表，每个字典代表一个学生，包含'name'和'score'两个键  
students = [{'name': 'Alice', 'score': 90}, {'name': 'Bob', 'score': 85}, {'name': 'Charlie', 'score': 90}]  
  
# 你想要首先按照分数从高到低排序，如果分数相同则按照名字字母顺序排序  
sorted_students = sorted(students, key=lambda student: (-student['score'], student['name']))  
  
# 输出排序后的学生列表  
for student in sorted_students:  
    print(student['name'], student['score'])

在这个示例中，键函数返回一个元组，元组的第一个元素是负数的分数（为了实现降序排序），第二个元素是名字。Python在比较元组时会按照元组的元素顺序进行比较，因此首先比较分数，如果分数相同则比较名字。

3.排序算法实现

Python允许你实现自己的排序算法，如冒泡排序、选择排序、插入排序、归并排序、快速排序等。这些算法不仅有助于深入理解排序的原理，还可以在某些特定场景下提供性能优化。

1. 冒泡排序

原理：通过相邻元素之间的比较和交换，使得每一趟排序后，最大（或最小）的元素被交换到序列的一端。

步骤：

1. 从第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大（升序排序），则交换它们的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

特点：冒泡排序简单易懂，但效率较低，特别是对于大数据集。

def maopao(a):
    n = len(a)
    for i in range(n-1):
        for j in range(n-i-1):
            if a[j] > a[j+1]:
                a[j],a[j+1] = a[j+1],a[j]
    return a
a = [3,5,8,9,2,6,7]
print(maopao(a))

2. 选择排序

原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

特点：选择排序是不稳定的排序方法

def xuanze(a):
    n=len(a)
    for i in range(n-1):
        #第i次从[i,n-1]找最小值
        min_value = a[i]
        min = i
        for j in range(i,n):
            if(a[j]<min_value):
                min_value=a[j]
                min = j
        #将最小值和最前面的元素交换
        a[min],a[i] = a[i],a[min]
    return a

3.插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

def charu(arr):  
    # 遍历从1到列表长度的所有元素  
    for i in range(1, len(arr)):  
        # 当前需要排序的元素  
        key = arr[i]  
        # j是已排序序列的最后一个元素的索引  
        j = i - 1  
        # 将大于key的元素后移  
        while j >= 0 and key < arr[j]:  
            arr[j + 1] = arr[j]  
            j -= 1  
        # 找到key的插入位置，插入key  
        arr[j + 1] = key  
    return arr  
  
# 示例  
arr = [4, 3, 2, 10, 12, 1, 5, 6]  
sorted_arr = charu(arr)  
print("排序后的数组:", sorted_arr)

4. 归并排序

原理：将数组拆分为子数组，先使每个子序列有序，在将子数组合并

步骤：

1. 分解：将数组分解成两个较小的子数组，直到子数组的大小为1。
2. 递归进行排序并合并：递归地对子数组进行排序，并将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。

特点：归并排序是稳定的排序方法，

def mix(A,B):
    '''
    递归
    :param A: 有序列表
    :param B: 有序列表
    :return: A与B合并的有序列表
    '''
    result = []
    while len(A) != 0 and len(B) != 0:
        # A与B比较，将小的放到新列表中，并将放过的数去除
        if A[0] <= B[0]:
            result.append(A.pop(0))
        else:
            result.append(B.pop(0))
    # 最后在末尾加上非0列表的剩余部分
    result.extend(A)
    result.extend(B)
    return  result


def fen(A):
    """
    先将一个大列表进行拆分，两个小列表，然后再对左边的小列表拆分，这样重复一直拆分
    直到mid<2也就是：左边的列表长度为1，然后再对右边进行重发操作，再对这两个小列表运用mix函数进行排序，得到一个有序的小列表
    之后一直运用mix函数进行排序，就可以完成排序。
    """
    if len(A) < 2:
        return A
    mid = len(A) // 2


    left = fen(A[:mid])
    right = fen(A[mid:])

    return mix(left,right)

a = [3,5,8,9,2,6,7]
fen(a)   #建议：在此处设置断点观看变化
print(fen(a))

5.快速排序

原理：通过一次排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

步骤：

1. 选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小。
2. 再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**特点：**效率更快。

def partition(a,left,right):
    index = left+1
    #假设left为基准值，left+1用于标记，方便交换
    for i in range(left+1,right+1):
        if a[i]<=a[left]:
            #如果当前元素小于基准值
            a[i],a[index]=a[index],a[i]
            #将比基准值小的交换到基准值后面
            index+=1
            #标记交用于换到的位置

    a[index-1],a[left]=a[left],a[index-1]
    #将基准值与比基准值小的最后一位交换，实现比基准值小的都在基准值前面
    return index-1
    #返回基准值下标

def quickfile(a,left,right):
    if left < right:
        mid= partition(a,left,right)
        quickfile(a,left,mid-1)
        #基准值排好了，不动，先对左边进行递归
        quickfile(a,mid+1,right)


a = [3,5,8,9,2,6,7]
quickfile(a,0,6)
print(a)