常见排序算法

冒泡排序

工作原理

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

复杂度

• 最坏时间复杂度 O(N^2)
• 最优时间复杂度 O(N)
• 平均时间复杂度 O(N^2)
• 额外空间复杂度 O(1)
• 稳定性 稳定

实现

# 冒泡排序
def bubble_sort(alist):
    n = len(alist)
    exchange = False
	# 首先得到每个循环需要比较的次数，第一次从0位置开始需要比较 len(alist) - 1 次
    for i in range(n-1, 0, -1):
		# 相邻两个位置不断比较，如果左边的数大于右边就交换位置
        for j in range(0, i):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
                exchange = True
        # 如果发现整个排序过程中没有交换，提前结束
        if not exchange:
            break
    return alist

选择排序

工作原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。步骤如下：

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

复杂度

• 最坏时间复杂度 O(N^2)
• 最优时间复杂度 O(N^2)
• 平均时间复杂度 O(N^2)
• 额外空间复杂度 O(1)
• 稳定性 稳定

实现

# 选择排序
def selection_sort(alist):
    n = len(alist)
    for i in range(n-1):
        # 寻找[i,n]区间里的最小值
        min_index = i
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist

插入排序

工作原理

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

复杂度

• 最坏时间复杂度 O(N^2)
• 最优时间复杂度 O(N)
• 平均时间复杂度 O(N^2)
• 额外空间复杂度 O(1)
• 稳定性 稳定

实现

# 插入排序
def insertion_sort(alist):
    # 从索引为 1 的值开始从后向前扫描
    for i in range(1, len(alist)):
        current_value = alist[i]
        position = i
        # 如果前一个数大于当前值则将前一个数向右移动一位，直到找到前一个数小于当前值得位置，将该位置的值设为当前值
        while position > 0 and alist[position - 1] > current_value:
            alist[position] = alist[position - 1]
            position -= 1

        alist[position] = current_value
    return alist

快速排序

工作原理

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。步骤如下：

1. 从数列中挑出一个元素，称为“基准”（pivot）；
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作；
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

复杂度

• 最坏时间复杂度 O(N^2)
• 最优时间复杂度 O(NlogN)
• 平均时间复杂度 O(NlogN)
• 额外空间复杂度 O(logN)
• 稳定性 不稳定

实现

# 快速排序
def __quickSort(alist, l, r):
    #当数列的大小比较小的时候，数列近乎有序的概率较大
    # if (r - l <= 15):
    #     insertionSortHelp(alist, l, r)
    #     return

    if l >= r:
        return
    p = partition(alist, l, r)
    __quickSort(alist, l, p-1)
    __quickSort(alist, p+1, r)

# 在alist[l...r]中寻找j,使得alist[l...j] <= alist[l], alist[j+1...r] >alist[l]
def partition(alist, l, r):
    pos = randint(l, r)
    alist[pos], alist[l] = alist[l], alist[pos]
    v = alist[l]
    # v = alist[l]
    j = l
    i = l + 1
    while i <= r:
        if alist[i] <= v:
            alist[j+1],alist[i] = alist[i],alist[j+1]
            j += 1
        i += 1
    alist[l], alist[j] = alist[j], alist[l]
    return j