前端排序算法 -- 基数排序、堆排序和桶排序

基数排序算法

1. 介绍

基数排序是一种非比较型的排序算法，它根据元素的位数进行排序。与其他排序算法不同，基数排序将元素按照个位、十位、百位等位置进行排序，从而实现整体有序。

2. 实现过程

• 首先，确定排序的最大值，并计算出最大值的位数。
• 创建一个桶数组，用于存放待排序元素。
• 从最低位开始，依次按照当前位数的值将元素分配到对应的桶中。
• 按照顺序收集每个桶中的元素。
• 重复上述步骤，直到处理完所有位数。
• 最后，收集所有桶中的元素即可得到排序结果。

3. 伪代码

function radixSort(arr):
    maxNum = 找到数组中的最大值
    digit = 计算最大值的位数
    buckets = 创建桶数组，每个桶包含一个空数组
    
    for i from 个位开始到最高位:
        for j from 0 to 数组长度:
            将arr[j]根据当前位数放入对应的桶中
            
        将所有桶中的元素按顺序收集到arr中
    
    返回排序后的arr

4. ts实现

function radixSort(arr: number[]): number[] {
  const maxNum = Math.max(...arr);
  const digit = Math.floor(Math.log10(maxNum) + 1);
  const buckets: number[][] = Array.from({ length: 10 }, () => []);

  for (let i = 0; i < digit; i++) {
    for (let j = 0; j < arr.length; j++) {
      const num = arr[j];
      const digitValue = Math.floor(num / Math.pow(10, i)) % 10;
      buckets[digitValue].push(num);
    }

    arr = buckets.flat();
    buckets.forEach(bucket => (bucket.length = 0));
  }

  return arr;
}

5. c实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void radixSort(int arr[], int n) {
  int maxNum = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > maxNum) {
      maxNum = arr[i];
    }
  }

  int digit = 0;
  while (maxNum > 0) {
    maxNum /= 10;
    digit++;
  }

  int buckets[10][n];
  int bucketCounts[10] = {0};

  for (int i = 0; i < digit; i++) {
    for (int j = 0; j < n; j++) {
      int num = arr[j];
      int digitValue = (num / (int)pow(10, i)) % 10;
      buckets[digitValue][bucketCounts[digitValue]] = num;
      bucketCounts[digitValue]++;
    }

    int index = 0;
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < bucketCounts[j]; k++) {
        arr[index] = buckets[j][k];
        index++;
      }
      bucketCounts[j] = 0;
    }
  }
}

int main() {
  int arr[] = {53, 89, 150, 36, 633, 233, 928, 999};
  int n = sizeof(arr) / sizeof(arr[0]);

  radixSort(arr, n);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

6. 复杂度分析

• 比较复杂度：基数排序的比较复杂度为O(1)，因为它不需要进行元素之间的比较操作。
• 交换复杂度：基数排序的交换复杂度也为O(1)，因为它不需要进行元素之间的交换操作。
• 空间复杂度：基数排序的空间复杂度取决于桶数组的大小，即O(n+k)，其中n是待排序元素的数量，k是桶的数量。在最坏情况下，当k接近n时，空间复杂度可能会较高。
• 时间复杂度：基数排序的时间复杂度为O(d * (n + k))，其中d是元素的位数，n是待排序元素的数量，k是桶的数量。在最坏情况下，当d接近n时，时间复杂度可能会较高

堆排序算法

1. 介绍

堆排序是一种基于二叉堆的排序算法。它利用堆数据结构的特性进行排序，具有稳定的时间复杂度和较好的性能表现。

2. 实现过程

• 首先，将待排序的数组构建为一个最大堆（或最小堆）。
• 然后，将堆顶元素与堆的最后一个元素交换，并从堆中移除该元素。
• 重复上述步骤，直到堆为空或只剩下一个元素。
• 最后，按照从大到小（或从小到大）的顺序收集所有交换出来的元素，即得到排序结果。

3. 伪代码

function heapSort(arr):
    buildMaxHeap(arr)  // 构建最大堆

    for i from 数组长度-1 到 1:
        交换arr[0]和arr[i]  // 将堆顶元素与堆的最后一个元素交换
        调整堆(arr, 0, i)  // 重新调整堆，保持最大堆的性质

    返回排序后的arr

4. ts实现

function heapSort(arr: number[]): number[] {
  const n = arr.length;

  // 构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 逐步将堆顶元素与堆的最后一个元素交换，并调整堆
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }

  return arr;
}

function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

5. c实现

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    swap(&arr[i], &arr[largest]);
    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n) {
  // 构建最大堆
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 逐步将堆顶元素与堆的最后一个元素交换，并调整堆
  for (int i = n - 1; i > 0; i--) {
    swap(&arr[0], &arr[i]);
    heapify(arr, i, 0);
  }
}

int main() {
  int arr[] = {53, 89, 150, 36, 633, 233, 928, 999};
  int n = sizeof(arr) / sizeof(arr[0]);

  heapSort(arr, n);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

6. 复杂度分析

• 比较复杂度：堆排序的比较次数在最坏情况下为O(nlogn)，其中n是待排序元素的数量。每个节点需要与其子节点进行一次比较。
• 交换复杂度：堆排序的交换次数也在最坏情况下为O(nlogn)。每个节点需要与其子节点进行一次交换，但每次交换可能会引起整个堆的重新调整。
• 空间复杂度：堆排序的空间复杂度为O(1)，因为它只需要使用常数级别的额外空间进行操作，无需额外的辅助空间。
• 时间复杂度：堆排序的时间复杂度为O(nlogn)，因为构建最大堆的过程需要O(n)的时间，然后每次调整堆的过程需要O(logn)的时间，总共进行n-1次调整。

桶排序算法

1. 介绍

桶排序是一种线性时间复杂度的排序算法，适用于已知待排序数据分布范围的情况。它将待排序数据划分为多个桶，然后对每个桶进行排序，最后按照桶的顺序依次收集元素，即可得到有序结果。

2. 实现过程

• 首先，确定桶的数量和范围。根据待排序数据的最大值和最小值，计算出需要的桶数量。
• 然后，将待排序数据分配到各个桶中。可以使用简单的映射函数将数据映射到桶的索引位置。
• 接下来，对每个桶中的数据进行排序。可以使用其他排序算法，如插入排序或快速排序。
• 最后，按照桶的顺序将各个桶中的数据合并起来，即可得到有序结果。

3. 伪代码

function bucketSort(arr):
    n = 数组长度
    maxVal = 数组最大值
    minVal = 数组最小值
    bucketSize = (maxVal - minVal) / n  // 计算桶的大小

    创建空桶数组bucket[n]

    for i from 0 到 n-1:
        创建空数组bucket[i]  // 创建各个桶

    for i from 0 到 n-1:
        将arr[i]插入到对应的桶中  // 根据映射函数将数据分配到桶中

    for i from 0 到 n-1:
        对每个桶进行排序  // 可以使用其他排序算法，如插入排序

    合并各个桶中的数据得到有序结果

    返回排序后的数组

4. ts实现

function bucketSort(arr: number[]): number[] {
  const n = arr.length;
  const maxVal = Math.max(...arr);
  const minVal = Math.min(...arr);
  const bucketSize = Math.floor((maxVal - minVal) / n) + 1;

  const buckets: number[][] = [];
  for (let i = 0; i < n; i++) {
    buckets.push([]);
  }

  for (let i = 0; i < n; i++) {
    const bucketIndex = Math.floor((arr[i] - minVal) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }

  for (let i = 0; i < n; i++) {
    buckets[i].sort((a, b) => a - b);
  }

  let sortedArr: number[] = [];
  for (let i = 0; i < n; i++) {
    sortedArr = sortedArr.concat(buckets[i]);
  }

  return sortedArr;
}

5. c实现

#include <stdio.h>
#include <stdlib.h>

void bucketSort(int arr[], int n) {
  int maxVal = arr[0];
  int minVal = arr[0];

  for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal) {
      maxVal = arr[i];
    }
    if (arr[i] < minVal) {
      minVal = arr[i];
    }
  }

  int bucketSize = (maxVal - minVal) / n + 1;

  // 创建桶数组
  int** buckets = (int**)malloc(n * sizeof(int*));
  for (int i = 0; i < n; i++) {
    buckets[i] = (int*)malloc(n * sizeof(int));
  }

  // 初始化桶数组为空
  for (int i = 0; i < n; i++) {
    buckets[i][0] = 0;
  }

  // 将元素分配到对应的桶中
  for (int i = 0; i < n; i++) {
    int bucketIndex = (arr[i] - minVal) / bucketSize;
    int index = ++buckets[bucketIndex][0];
    buckets[bucketIndex][index] = arr[i];
  }

  // 对每个桶中的元素进行排序（使用插入排序）
  for (int i = 0; i < n; i++) {
    int size = buckets[i][0];
    for (int j = 1; j <= size; j++) {
      int k = j;
      while (k > 1 && buckets[i][k] < buckets[i][k - 1]) {
        int temp = buckets[i][k];
        buckets[i][k] = buckets[i][k - 1];
        buckets[i][k - 1] = temp;
        k--;
      }
    }
  }

  // 合并各个桶中的元素得到有序结果
  int sortedIndex = 0;
  for (int i = 0; i < n; i++) {
    int size = buckets[i][0];
    for (int j = 1; j <= size; j++) {
      arr[sortedIndex++] = buckets[i][j];
    }
  }

  // 释放内存
  for (int i = 0; i < n; i++) {
    free(buckets[i]);
  }
  free(buckets);
}

int main() {
  int arr[] = {53, 89, 150, 36, 633, 233, 928, 999};
  int n = sizeof(arr) / sizeof(arr[0]);

  bucketSort(arr, n);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

6. 复杂度分析

• 比较复杂度：桶排序的比较次数取决于对每个桶中元素进行排序所使用的算法。在最坏情况下，如果每个桶只有一个元素，那么比较次数将是O(n^2)，但通常情况下，每个桶中的元素数量会比较均衡，所以比较次数较少。
• 交换复杂度：桶排序的交换次数与比较次数相关，取决于对每个桶中元素进行排序所使用的算法。
• 空间复杂度：桶排序的空间复杂度为O(n+k)，其中n是待排序元素的数量，k是桶的数量。需要额外的空间来存储桶数组和每个桶中的元素。
• 时间复杂度：桶排序的平均时间复杂度为O(n+k)，其中n是待排序元素的数量，k是桶的数量。由于桶的数量趋近于n，所以桶排序的时间复杂度可以近似为O(n)。