算法导论基础-几种排序算法总结

---

算法	最坏情况运行时间	平均情况/期望运行时间
插入排序	Θ(n²)	Θ(n²)
归并排序	Θ(nlgn)	Θ(nlgn)
堆排序	Θ(nlgn)	——
快速排序	Θ(n²)	Θ(nlgn)
计数排序	Θ(n+k)	Θ(n+k)
基数排序	Θ(d(n+k))	Θ(d(n+k))
桶排序	Θ(n²)	Θ(n)

1 插入排序算法

插入排序示意图：

演示C代码：

void insertionSort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = value;
  }
}

2 归并排序算法（分治法）

归并排序图示：

演示C代码：

void mergeSort(int a[], int n) {
  if (n <= 1) {
    return;
  }

  int mid = n / 2;
  int left[mid];
  int right[n - mid];

  for (int i = 0; i < mid; ++i) {
    left[i] = a[i];
  }

  for (int i = mid; i < n; ++i) {
    right[i - mid] = a[i];
  }

  mergeSort(left, mid);
  mergeSort(right, n - mid);
  merge(a, left, mid, right, n - mid);
}

void merge(int a[], int left[], int leftCount, int right[], int rightCount) {
  int i = 0, j = 0, k = 0;

  while (i < leftCount && j < rightCount) {
    if (left[i] <= right[j]) {
      a[k++] = left[i++];
    } else {
      a[k++] = right[j++];
    }
  }

  while (i < leftCount) {
    a[k++] = left[i++];
  }

  while (j < rightCount) {
    a[k++] = right[j++];
  }
}

3 堆排序（二叉树）

建堆图示：

堆排序图示：


演示C代码：

void heapSort(int a[], int n) {
  // 建立大顶堆
  buildMaxHeap(a, n);

  for (int i = n - 1; i > 0; --i) {
    // 将堆顶元素与末尾元素交换
    swap(a[0], a[i]);
    // 调整堆结构，排除末尾元素
    adjustHeap(a, 0, i - 1);
  }
}

void buildMaxHeap(int a[], int n) {
  for (int i = n / 2 - 1; i >= 0; --i) {
    adjustHeap(a, i, n - 1);
  }
}

void adjustHeap(int a[], int i, int end) {
  int child = i * 2 + 1;
  while (child <= end) {
    // 左右子节点中选取最大值
    if (child + 1 <= end && a[child] < a[child + 1]) {
      child++;
    }

    if (child <= end && a[i] < a[child]) {
      // 将子节点的值与父节点的值交换
      swap(a[i], a[child]);
      i = child;
      child = i * 2 + 1;
    } else {
      return;
    }
  }
}

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

4 计数排序

计数排序图示：

演示C代码：

void countingSort(int a[], int n) {
  int min = a[0], max = a[0];
  for (int i = 1; i < n; ++i) {
    if (a[i] < min) {
      min = a[i];
    } else if (a[i] > max) {
      max = a[i];
    }
  }

  int count[max - min + 1];
  for (int i = 0; i <= max - min; ++i) {
    count[i] = 0;
  }

  for (int i = 0; i < n; ++i) {
    count[a[i] - min]++;
  }

  int i = 0;
  for (int j = min; j <= max; ++j) {
    while (count[j - min] > 0) {
      a[i++] = j;
      count[j - min]--;
    }
  }
}

5 基于计数排序的基数排序

基数排序图示：

演示C代码：

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

  for (int exp = 1; exp <= max; exp *= 10) {
    int count[10];
    for (int i = 0; i < 10; ++i) {
      count[i] = 0;
    }

    for (int i = 0; i < n; ++i) {
      count[(a[i] / exp) % 10]++;
    }

    int i = 0;
    for (int j = 0; j < 10; ++j) {
      while (count[j] > 0) {
        a[i++] = j * exp;
        count[j]--;
      }
    }
  }
}

6 桶排序

桶排序图示：

演示C代码：

void bucketSort(int arr[], int n) {
  // 设置桶的数量
  int bucketCount = 10; // 假设元素范围为 0 到 99

  // 创建桶
  int buckets[bucketCount][]; // 存储桶

  // 初始化空桶
  for (int i = 0; i < bucketCount; ++i) {
    buckets[i] = (int *)malloc(n * sizeof(int)); // 为每个桶分配内存
    for (int j = 0; j < n; ++j) {
      buckets[i][j] = 0; // 初始化桶元素为 0
    }
  }

  // 将元素分配到桶中
  for (int i = 0; i < n; ++i) {
    int bucketIndex = arr[i] / bucketCount; // 计算桶索引
    buckets[bucketIndex][i % bucketCount] = arr[i]; // 将元素放入相应桶
  }

  // 对每个桶中的元素排序
  for (int i = 0; i < bucketCount; ++i) {
    int bucketSize = 0; // 非零元素计数器
    for (int j = 0; j < n; ++j) {
      if (buckets[i][j] != 0) { // 非零元素
        buckets[i][bucketSize++] = buckets[i][j]; // 移动非零元素到桶前面
      }
    }
  }

  // 合并桶中排序后的元素
  int index = 0;
  for (int i = 0; i < bucketCount; ++i) {
    for (int j = 0; j < n; ++j) {
      if (buckets[i][j] != 0) {
        arr[index++] = buckets[i][j]; // 将非零元素复制到排序数组
      }
    }
  }

  // 释放分配的内存
  for (int i = 0; i < bucketCount; ++i) {
    free(buckets[i]); // 释放每个桶的内存
  }
}

int main() {
  int arr[] = {5, 2, 4, 6, 1, 3};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("未排序数组：");
  for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
  }

  bucketSort(arr, n);

  printf("\n排序后的数组：");
  for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
  }

  return 0;
}

7 快速排序

快速排序图示：

演示C代码：

void swap(int *a, int *b) {
  int temp = *a;  // 临时变量用于存储要交换的值
  *a = *b;  // 将 a 的值赋给 b
  *b = temp;  // 将 temp 的值赋给 b
}

int partition(int arr[], int low, int high) {
  int pivot = arr[high];  // 选择最后一个元素作为枢纽元素
  int i = (low - 1);  // 初始化 i 变量为 low - 1

  for (int j = low; j < high; j++) {  // 从 low 循环到 high - 1
    if (arr[j] <= pivot) {  // 如果当前元素小于或等于枢纽元素
      i++;  // i 递增
      swap(&arr[i], &arr[j]);  // 交换当前元素和 arr[i] 的值
    }
  }

  swap(&arr[i + 1], &arr[high]);  // 将枢纽元素移到正确的位置
  return (i + 1);  // 返回枢纽元素的位置
}

void quickSort(int arr[], int low, int high) {
  if (low < high) {  // 如果 low 小于 high，则继续排序
    int pi = partition(arr, low, high);  // 对数组进行分区，并返回枢纽元素的位置

    quickSort(arr, low, pi - 1);  // 递归排序左子数组
    quickSort(arr, pi + 1, high);  // 递归排序右子数组
  }
}

int main() {
  int arr[] = {5, 2, 4, 1, 3};  // 待排序数组
  int n = sizeof(arr) / sizeof(arr[0]);  // 数组长度

  printf("未排序数组：");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);  // 输出未排序数组
  }

  quickSort(arr, 0, n - 1);  // 对数组进行快速排序

  printf("\n排序后数组：");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);  // 输出排序后数组
  }

  return 0;
}