排序算法

排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列，排序就是把集合中的元素按照一定的次序排序在一起。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

时间复杂度对比

排序算法	平均时间复杂度	最坏时间复杂度	最优时间复杂度	空间复杂度	排序方式	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	In-Place	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	In-Place	不稳定
插入排序	O(n²)	O(n²)	O(n)	O(1)	In-Place	稳定
希尔排序	O(n¹˙³)	O(n²)	O(n)	O(1)	In-Place	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	Out-Place	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	In-Place	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	In-Place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-Place	稳定
桶排序	O(n+k)	O(n²)	O(n)	O(n+k)	Out-Place	稳定
基数排序	O(n×k)	O(n×k)	O(n×k)	O(n+k)	Out-Place	稳定

注意：

n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

冒泡排序（Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对 n 个项目需要 O(n²) 的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

算法步骤

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

动图展示

代码实现

Java

public int[] bubbleSort(int[] array) {
    int temp;
    for (int i = 0; i < array.length - 1; i++) {
        boolean Flag = false; // 是否发生交换。没有交换，提前跳出外层循环
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                Flag = true;
            }
        }
        if (!Flag)
        {
            break;
        }
    }
    return array;
}

Python

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

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 (n-1) 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法步骤

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

动图展示

代码实现

Java

public int[] selectionSort(int[] arr) throws Exception {
    // 总共要经过 n-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }
        // 将找到的最小值和 i 位置所在的值进行交换
        if (i != min) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    return arr;
}

Python

def selection_sort(arr):
    for i in range(len(arr)-1):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        if i == minIndex:
            pass
        else:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 In-Place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法步骤

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

动图展示

代码实现

Java

public int[] insertionSort(int[] arr) throws Exception {
    // 从下标为 1 的元素开始选择合适的位置插入，因为下标为 0 的元素，默认是有序的
    for (int i = 1; i < arr.length; i++) {
        // 记录要插入的数据
        int tmp = arr[i];
        // 从已经排序的序列最右边的开始比较，找到比其小的数
        int j = i;
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        // 存在比其小的数，插入
        if (j != i) {
            arr[j] = tmp;
        }
    }
    return arr;
}

Python

def insertion_sort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr

希尔排序

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

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

算法步骤

选择一个增量序列 t₁, t₂, ..., tₖ，其中 tᵢ > tⱼ, tₖ = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 tᵢ，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图展示

代码实现

Java

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    // 动态定义间隔序列
    for (int step = length / 2; step >= 1; step /= 2) {
        // 插入排序
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

Python

def shell_sort(arr):
    n = len(arr)
    # 初始步長
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步長進行插入排序
            temp = arr[i]
            j = i
            # 插入排序
            while j >= 0 and j-gap >= 0 and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        # 得到新的步長
        gap = gap // 2
    return arr

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；自下而上的迭代；

算法步骤

递归法（Top-down）

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针到达序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

迭代法（Bottom-up）

原理如下（假设序列共有 n 个元素）：

将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素；
若此时序列数不是 1 个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素；
重复步骤 2，直到所有元素排序完毕，即序列数为 1。

动图展示

代码实现

Java

// 递归版：
public static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1); //左边归并排序，使得左子序列有序
    merge_sort_recursive(arr, result, start2, end2); //右边归并排序，使得右子序列有序
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

// 迭代版：
public static void merge_sort(int[] arr) {
    int[] orderedArr = new int[arr.length];
    for (int i = 2; i < arr.length * 2; i *= 2) {
        for (int j = 0; j < (arr.length + i - 1) / i; j++) {
            int left = i * j;
            int mid = left + i / 2 >= arr.length ? (arr.length - 1) : (left + i / 2);
            int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1);
            int start = left, l = left, m = mid;
            while (l < mid && m <= right) {
                if (arr[l] < arr[m]) {
                    orderedArr[start++] = arr[l++];
                } else {
                    orderedArr[start++] = arr[m++];
                }
            }
            while (l < mid)
                orderedArr[start++] = arr[l++];
            while (m <= right)
                orderedArr[start++] = arr[m++];
            System.arraycopy(orderedArr, left, arr, left, right - left + 1);
        }
    }
}

Python

def mergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

快速排序

快速排序（Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(nlogn) 次比较。在最坏状况下则需要 O(n²)次比较，但这种状况并不常见。事实上，快速排序(nlogn)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

算法步骤

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）；
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

动图展示

代码实现

Java

public int[] quickSort(int[] arr, int left, int right) {
    int left = 0;
    int right = arr.length - 1
    // 当传递的目标数组含有两个以上的元素时，进行递归调用。（即：当传递的目标数组只含有一个元素时，此趟排序结束）
    if (left < right) {
        int partitionIndex = partition(arr, left, right); //获取关键值的下标（快排的核心）
        quickSort(arr, left, partitionIndex - 1); //递归调用，快排划分出来的左区间
        quickSort(arr, partitionIndex + 1, right); //递归调用，快排划分出来的右区间
    }
    return arr;
}

public int partition(int[] arr, int left, int right) {
    // 设定基准值（pivot）
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Python

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex - 1)
        quickSort(arr, partitionIndex + 1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index - 1)
    return index - 1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

算法步骤

创建一个堆 H[0 ... n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

动图展示

代码实现

Java

/**
  * 堆排序的主要入口方法，共两步。
  */
public void heapSort(int[] arr) {
    /*
      *  第一步：将数组堆化
      *  beginIndex = 第一个非叶子节点。
      *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
      *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
      */
    int len = arr.length - 1;
    int beginIndex = (arr.length >> 1)- 1;
    for (int i = beginIndex; i >= 0; i--)
        maxHeapify(i, len);
    /*
      * 第二步：对堆化数据排序
      * 每次都是移出最顶层的根节点 A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
      * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
      * 直至未排序的堆长度为 0。
      */
    for (int i = len; i > 0; i--) {
        swap(0, i);
        maxHeapify(0, i - 1);
    }
}

public void swap(int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/**
  * 调整索引为 index 处的数据，使其符合堆的特性。
  *
  * @param index 需要堆化处理的数据的索引
  * @param len 未排序的堆（数组）的长度
  */
public void maxHeapify(int index, int len) {
    int li = (index << 1) + 1; // 左子节点索引
    int ri = li + 1;           // 右子节点索引
    int cMax = li;             // 子节点值最大索引，默认左子节点。
    if (li > len) return;      // 左子节点索引超出计算范围，直接返回。
    if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
        cMax = ri;
    if (arr[cMax] > arr[index]) {
        swap(cMax, index);      // 如果父节点被子节点调换，
        maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
    }
}

Python

def heap_sort(arr):
    def sift_down(start, end):
        """最大堆调整"""
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    # 创建最大堆
    for start in xrange((len(arr) - 2) // 2, -1, -1):
        sift_down(start, len(arr) - 1)

    # 堆排序
    for end in xrange(len(arr) - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end - 1)
    return arr

计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。

算法步骤

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1。

找出待排序的数组中最大和最小的元素
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1

动图展示

代码实现

Java

public int[] countingSort(int[] arr) {
    int maxValue = getMaxValue(arr)
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];
    for (int value : arr) {
        bucket[value]++;
    }

    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    return arr;
}

public int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}

Python

def countingSort(arr):
    maxValue = arr[0]
    for value in arr:
        if maxValue < value:
            maxValue = value

    bucketLen = maxValue + 1
    bucket = [0] * bucketLen
    sortedIndex = 0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]] = 0
        bucket[arr[i]] += 1
    for j in range(bucketLen):
        while bucket[j] > 0:
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
    return arr

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

算法步骤

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

动图展示

代码实现

Java

public int indexFor(int a, int min, int step) {
    return (a - min) / step;
}

public void bucketSort(int[] arr) {
    int max = arr[0], min = arr[0];
    for (int a : arr) {
        if (max < a)
            max = a;
        if (min > a)
            min = a;
    }
    // 该值也可根据实际情况选择
    int bucketNum = max / 10 - min / 10 + 1;
    List buckList = new ArrayList<List<Integer>>();
    // 创建桶
    for (int i = 1; i <= bucketNum; i++) {
        buckList.add(new ArrayList<Integer>());
    }
    // 将数据分配到各个桶中
    for (int i = 0; i < arr.length; i++) {
        int index = indexFor(arr[i], min, 10);
        ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
    }
    ArrayList<Integer> bucket = null;
    int index = 0;
    for (int i = 0; i < bucketNum; i++) {
        bucket = (ArrayList<Integer>) buckList.get(i);
        // 对每个桶进行排序，这里使用了插入排序
        insertSort(bucket);
        for (int k : bucket) {
            arr[index++] = k;
        }
    }
}

// 把桶內元素使用插入排序
public void insertSort(List<Integer> bucket) {
    for (int i = 1; i < bucket.size(); i++) {
        int temp = bucket.get(i);
        int j = i - 1;
        for (; j >= 0 && bucket.get(j) > temp; j--) {
            bucket.set(j + 1, bucket.get(j));
        }
        bucket.set(j + 1, temp);
    }
}

Python

def bucket_sort(arr):
    max_num = max(arr)
    # 不能使用[[]]*(max+1)，这样新建的空间中各个[]是共享内存的
    buf = {i: [] for i in range(int(max_num) + 1)}
    arr_len = len(arr)
    for i in range(arr_len):
        num = arr[i]
        # 将相应范围内的数据加入到[]中
        buf[int(num)].append(num)
    arr = []
    for i in range(len(buf)):
        if buf[i]:
            # 这里还需要对一个范围内的数据进行排序，然后再进行输出
            arr.extend(sorted(buf[i]))
    return arr

基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序有两种方法：基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

算法步骤

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零；
从最低位开始，依次进行一次排序；
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

动图展示

代码实现

Java

public void radixSort(int[] array) {
    int max = getMax(array);
    int bit = 1;
    while(max / bit > 0) {
        radix(array, bit);
        bit *= 10;
    }
}

public void radix(int[] array, int bit) {
    int[] temp = new int[array.length];
    int[] bucket = new int[10];
    for(int i = 0; i < array.length; i++) {
        bucket[(array[i] / bit) % 10]++;
    }
    for(int i = 1; i < bucket.length; i++) {
        bucket[i] += bucket[i-1];
    }
    for(int i = array.length - 1; i >= 0; i--) {
        temp[bucket[(array[i] / bit) % 10] - 1] = array[i];
        bucket[(array[i] / bit) % 10]--;
    }
    for(int i = 0; i < temp.length; i++) {
        array[i] = temp[i];
    }
}

public int getMax(int[] array) {
    int max = array[0];
    for(int i = 1; i < array.length; i++){
        if(array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

Python

def radix_sort(arr):
    n = len(str(max(arr)))  # 记录最大值的位数
    for k in range(n):  # n 轮排序
        # 每一轮生成 10 个列表
        bucket_list = [[] for i in range(10)]  # 因为每一位数字都是 0~9，故建立 10 个桶
        for i in arr:
            # 按第 k 位放入到桶中
            bucket_list[i // (10 ** k) % 10].append(i)
        # 按当前桶的顺序重排列表
        arr = [j for i in bucket_list for j in i]
    return arr

排序算法

相关概念

时间复杂度对比

冒泡排序

算法步骤

动图展示

代码实现

Java

Python

选择排序

算法步骤

动图展示

代码实现

Java

Python

插入排序

算法步骤

动图展示

代码实现

Java

Python

希尔排序

算法步骤

动图展示

代码实现

Java

Python

归并排序

算法步骤

动图展示

代码实现

Java

Python

快速排序

算法步骤

动图展示

代码实现

Java

Python

堆排序

算法步骤

动图展示

代码实现

Java

Python

计数排序

算法步骤

动图展示

代码实现

Java

Python

桶排序

算法步骤

动图展示

代码实现

Java

Python

基数排序

算法步骤

动图展示

代码实现

Java

Python