十大经典排序算法
冒泡排序 111111 1111111111111 111111111111 11111111111111
选择排序

1 冒泡排序（Bubble Sort）

算法步骤

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

代码实现

1
2
3
4
5
6
def bubbleSort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2 选择排序（Selection Sort）

算法步骤

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

代码实现

1
2
3
4
5
6
7
8
9
def selectionSort(arr):
    for i in range(len(arr) - 1):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

3 插入排序（Insertion Sort）

算法步骤

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

代码实现

1
2
3
4
5
6
7
8
9
def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and current < arr[preIndex]:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr

4 希尔排序（Shellsort）

算法步骤

  • 选择一个增量序列 $t_1, t_2, \dots, t_k$，其中$t_i>t_{i+1}$，$t_k = 1$。

  • 按增量序列个数$k$，对序列进行$k$趟排序。

  • 每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$m$的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现

序列选择

间隔的选择是希尔排序的重要部分，不同的间隔会带来不同的性质。间隔太少会减慢传递速度，而间隔太多会产生开销。

通项公式 具体项数