Python实现排序算法_python排序

“排序”是计算机科学中的重要问题之一，他的主要目的是将一组无序的数据按照一定的顺序进行排列，以便于后续的查找、统计、分析等操作。

在本文中，我们将介绍几种常见的排序算法，并给出它们的Python实现。

（1）冒泡排序：

冒泡排序是一种简单的排序算法，即是依次比较两个相邻的数据元素，如果两数顺序与顺序次序不一致，则交换两个元素;重复对未排序的数据进行这样的操作，直到所有相邻的数据元素都不需要交换为止，则排序完成。在这个过程中，一些元素经过交换慢慢移到数列的前端，就像水中的“气泡”一样“冒”到上面，故称为“冒泡排序”。

下面是Python实现冒泡排序的代码：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。 

（2）选择排序：

选择排序是一种简单的排序算法，它的基本思想是每次选择未排序部分中的最小元素，将其放到已排序部分的末尾。

选择排序的原理可以用以下几个步骤来解释：

1. 首先，我们将整个待排序的数据分成两个部分，已排序部分和未排序部分。
2. 然后，我们从未排序部分中选取一个最小的元素，将其放到已排序部分的末尾。
3. 重复上述步骤，直到未排序部分中的所有元素都已经放到了已排序部分中。

下面是Python实现选择排序的代码：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

（3）插入排序

插入排序是一种简单的排序算法，它的基本思想是将未排序部分的元素依次插入到已排序部分的正确位置。

插入排序的原理可以用以下几个步骤来解释：

1. 首先，我们将整个待排序的数据分成两个部分，已排序部分和未排序部分。
2. 然后，我们从未排序部分中取出一个元素，在已排序部分中找到其正确的位置，并将其插入到该位置。
3. 重复上述步骤，直到未排序部分中的所有元素都已经插入到了已排序部分中。

下面是Python实现插入排序的代码：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

评价：虽然上述三种排序方式的时间复杂度较高，但是它的实现简单、稳定性好，对于小规模数据的排序效果还是比较不错的。同时，上述三种排序还具有稳定性，即相等的元素在排序前后的相对位置不会发生改变。

（4）快速排序

快速排序是一种高效的排序算法，它的基本思想是通过选取一个基准元素，将数组分成两部分，并对这两部分分别进行排序。

快速排序的原理可以用以下几个步骤来解释：

1. 首先，我们选取一个基准元素，将数组分成两部分，一部分包含所有小于基准元素的元素，另一部分包含所有大于等于基准元素的元素。
2. 然后，我们对这两部分分别进行排序，即对小于基准元素的部分和大于等于基准元素的部分分别进行递归排序。
3. 最后，将排好序的两部分合并起来，即可得到一个有序的序列。

下面是Python实现快速排序的代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

（5）归并排序

归并排序是一种高效的排序算法，它的基本思想是将数组分成两部分，并对这两部分分别进行排序，然后将它们合并起来。

归并排序的原理可以用以下几个步骤来解释：

1. 首先，我们将待排序的数组分成两个部分，分别对这两部分进行排序，这个过程可以使用递归来实现。
2. 然后，将排序好的两部分合并起来，得到一个有序的数组。
3. 重复上述步骤，直到数组的所有元素都已经排好序。

在归并排序的过程中，我们将数组分成两部分进行排序，并将排好序的两部分合并起来，这个过程可以看作是一棵树形结构的递归过程。每次递归都将数组分成两半，直到每个子数组的长度都为1，然后将相邻的两个子数组合并起来，得到一个有序的数组。这个过程可以看作是一棵树形结构，树的高度为logn，每个节点需要进行一次合并操作，因此归并排序的时间复杂度为O(nlogn)。

下面是Python实现归并排序的代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

评价：上述两种排序是稳定的排序算法，由于在排序过程中，相等的元素的相对位置不会发生改变。上述两种排序也是一种原地排序算法，即不需要额外的存储空间来存储中间结果，因此，它们在空间上的开销很小。

另外介绍两种“有趣”的排序

def cocktail_sort(arr):
 
    n = len(arr)
 
    left = 0
 
    right = n - 1
 
    while left < right:
 
        for i in range(left, right):
 
            if arr[i] > arr[i+1]:
 
                arr[i], arr[i+1] = arr[i+1], arr[i]
 
        right -= 1
 
        for i in range(right, left, -1):
 
            if arr[i-1] > arr[i]:
 
                arr[i], arr[i-1] = arr[i-1], arr[i]
 
        left += 1
 
    return arr

def gnome_sort(arr):
 
    n = len(arr)
 
    i = 0
 
    while i < n:
 
        if i == 0 or arr[i] >= arr[i-1]:
 
            i += 1
 
        else:
 
            arr[i], arr[i-1] = arr[i-1], arr[i]
 
            i -= 1
 
    return arr