排序合集（一）

一、直接插入排序 (Insertion Sort)

基本思想

直接插入排序是一种简单直观的排序算法，就像我们打扑克牌时的操作：每次摸到一张牌，都会把它插入到手中已排好序的牌的正确位置。通过这种方式，逐步构建一个有序序列。

步骤

1. 从第一个元素开始，该元素可以认为已经被排序。

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。

4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。

5. 将新元素插入到该位置后。

6. 重复步骤2~5，直到所有元素都被排序。

C语言代码示例

void InsertSort(int* a, int n) {for (int i = 1; i < n; i++) { // 从第二个元素开始int temp = a[i]; // 当前要插入的元素int j = i - 1;    // 从已排序部分的最后一个元素开始比较while (j >= 0 && a[j] > temp) {a[j + 1] = a[j]; // 如果当前元素大于新元素，向后移动j--;}a[j + 1] = temp; // 找到插入位置后，插入新元素}
}

算法分析

• 时间复杂度：

  • 最好情况（已排好序）：O(n)，每个元素只需比较一次。

  • 平均情况和最坏情况（逆序）：O(n²)。

• 空间复杂度：O(1)，只需要一个临时变量。

• 稳定性：稳定。相等元素的相对位置不会改变。

• 适用场景：适用于小型数据集或基本有序的数据集，效率较高。

---

二、冒泡排序 (Bubble Sort)

基本思想

冒泡排序是一种简单但效率较低的排序算法。它的名字来源于其工作方式：通过重复遍历待排序的数列，比较相邻的两个元素，如果顺序错误就交换它们。每次遍历后，最大的元素会像气泡一样“浮”到数列的末尾。

步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们。

2. 对每一对相邻元素做同样的操作，从第一个元素到最后一个元素。经过这一轮后，最大的元素会移动到数列的末尾。

3. 重复上述步骤，但每次减少比较的范围，因为最后的元素已经排好序。

4. 继续重复，直到整个数列有序。

C语言代码示例

void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 遍历 n-1 次for (int j = 0; j < n - i - 1; j++) { // 每次减少比较范围if (arr[j] > arr[j + 1]) { // 如果顺序错误，交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

算法分析

• 时间复杂度：

  • 最好情况（已排好序）：O(n)，因为只需要遍历一次。

  • 平均情况和最坏情况（逆序）：O(n²)。

• 空间复杂度：O(1)，只需要一个临时变量。

• 稳定性：稳定。相等元素的相对位置不会改变。

• 适用场景：由于效率较低，通常只用于教学示例，不适合实际应用。

---

三、希尔排序 (Shell Sort)

基本思想

希尔排序是插入排序的一种改进版本，通过引入“增量”来分组排序，减少数据的移动次数。它将待排序的元素分成若干组，每组内的元素间距为某个增量，然后对每组进行插入排序。随着增量逐渐减小，最终增量为1时，整个序列基本有序，此时再进行一次直接插入排序即可完成。

步骤

1. 选择一个增量序列，例如 [n/2, n/4, ..., 1]。

2. 按增量序列的个数进行多趟排序。

3. 每趟排序中，根据当前增量将序列分成若干子序列，对每个子序列进行插入排序。

4. 增量逐步减小，直到增量为1，完成排序。

C语言代码示例

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) { // 增量逐步减小for (int i = gap; i < n; i++) { // 对每个子序列进行插入排序int temp = arr[i];int j = i;while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}

算法分析

• 时间复杂度：

  • 最好情况：O(n log n)。

  • 平均情况：取决于增量序列，通常在 O(n log² n) 到 O(n^(3/2)) 之间。

  • 最坏情况：O(n²)。

• 空间复杂度：O(1)。

• 稳定性：不稳定。由于分组排序，可能会破坏元素的相对顺序。

• 适用场景：适用于中等规模的数据集，性能优于简单排序算法。

---

四、选择排序 (Selection Sort)

基本思想

选择排序是一种简单直观的排序算法。它的核心思想是：每次从未排序的部分中找到最小（或最大）的元素，放到已排序部分的末尾。通过逐步缩小未排序部分的范围，最终完成排序。

步骤

1. 在未排序的序列中找到最小元素。

2. 将最小元素与未排序部分的第一个元素交换。

3. 将已排序部分的边界向后移动一位。

4. 重复上述步骤，直到所有元素都被排序。

C语言代码示例

void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 遍历 n-1 次int min_idx = i; // 假设当前元素为最小值for (int j = i + 1; j < n; j++) { // 找到未排序部分的最小值if (arr[j] < arr[min_idx]) {min_idx = j;}}// 交换最小值与当前元素int temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}
}

算法分析

• 时间复杂度：

  • 最好、平均和最坏情况：O(n²)。

• 空间复杂度：O(1)。

• 稳定性：不稳定。交换操作可能会破坏相等元素的相对顺序。

• 适用场景：实现简单，适合小型数据集或教学示例。

---

五、堆排序 (Heap Sort)

基本思想

堆排序是一种基于堆数据结构的排序算法。堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。堆排序利用堆的性质，快速找到最大或最小元素，并逐步构建有序序列。

步骤

1. 将待排序的序列构建成一个大顶堆（升序排序）或小顶堆（降序排序）。

2. 将堆顶元素（最大值或最小值）与末尾元素交换。

3. 将剩余的元素重新调整为堆。

4. 重复上述步骤，直到所有元素都被排序。

C语言代码示例

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) {// 交换当前节点与最大值节点int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 递归调整子树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--) {// 交换堆顶元素与末尾元素int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整剩余元素为堆heapify(arr, i, 0);}
}

算法分析

• 时间复杂度：

  • 最好、平均和最坏情况：O(n log n)。

• 空间复杂度：O(1)。

• 稳定性：不稳定。交换操作可能会破坏相等元素的相对顺序。

• 适用场景：适合大数据量的排序，性能稳定。