直接插入排序

直接插入排序是一种简单直观的排序算法。它将待排序序列划分为有序区和无序区。在每一趟排序中，取无序区中的第一个元素，在有序区中从后向前查找其插入位置，并将有序区中需要移动的元素向后移动，最后将该元素插入到找到的位置。

void StraightInsertSort(int arr[], int n) {
    int i, j;
    for (i = 1; i < n; ++i) {
        // arr[i] 是待插入元素
        if (arr[i] < arr[i - 1]) {
            int temp = arr[i];
            // 从有序区的最后一个元素开始向前查找插入位置
            for (j = i - 1; j >= 0 && temp < arr[j]; --j) {
                arr[j + 1] = arr[j]; // 后移元素
            }
            arr[j + 1] = temp; // 插入元素
        }
    }
}
    

折半插入排序

折半插入排序是对直接插入排序的优化。它将查找插入位置和移动元素这两个操作分开。在每一趟排序中，使用折半查找（二分查找）在有序区中快速找到待插入元素的位置，然后再统一将该位置之后的所有元素后移，最后将待插入元素放入空出的位置。

void BinaryInsertSort(int arr[], int n) {
    int i, j, low, high, mid;
    for (i = 1; i < n; ++i) {
        int temp = arr[i];
        low = 0;
        high = i - 1;
        // 使用折半查找确定插入位置
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (temp < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // high+1 是插入位置
        // 将插入位置之后的元素后移
        for (j = i - 1; j >= high + 1; --j) {
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = temp; // 插入元素
    }
}
    

希尔排序

希尔排序（Shell Sort），也称为缩小增量排序，是对直接插入排序的改进。它首先将待排序序列分割成若干个长度较小的子序列，对这些子序列分别进行直接插入排序。随着增量的逐渐减小，子序列的长度也逐渐增大，最终当增量为1时，整个序列将基本有序，此时再进行一次直接插入排序，效率会大大提高。常见的增量序列是先取n/2，然后每次减半，直到增量为1。

void ShellSort(int arr[], int n) {
    int dk; // 增量
    for (dk = n / 2; dk >= 1; dk = dk / 2) {
        // 对每个增量进行分组插入排序
        for (int i = dk; i < n; ++i) {
            if (arr[i] < arr[i - dk]) {
                int temp = arr[i];
                int j;
                // 在分组内进行插入排序
                for (j = i - dk; j >= 0 && temp < arr[j]; j -= dk) {
                    arr[j + dk] = arr[j]; // 后移元素
                }
                arr[j + dk] = temp; // 插入元素
            }
        }
    }
}
    

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历待排序列表，比较每对相邻的元素，如果它们的顺序错误（前一个比后一个大），就交换它们。这个过程会一直重复，直到在一次完整的遍历中没有再发生交换，这意味着列表已经排序完成。每一趟排序都会将当前未排序部分的最大（或最小）元素"冒泡"到其最终位置。

void BubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        // 从后往前比较相邻元素
        for (int j = n - 1; j > i; --j) {
            if (arr[j - 1] > arr[j]) {
                // 交换元素
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                swapped = true;
            }
        }
        // 如果在一趟中没有发生交换，则列表已排序
        if (!swapped) {
            break;
        }
    }
}
    

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治策略。它选择一个"基准"（pivot）元素，然后将列表重新排列，使得所有小于基准的元素都放在基准前面，所有大于基准的元素都放在基准后面。这个过程称为分区（partition）。然后，它递归地对基准前后的子列表进行快速排序，直到整个列表排序完成。基准的选择对性能有很大影响。

int Partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 选择第一个元素作为基准
    while (low < high) {
        // 从右向左找到第一个小于基准的元素
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high]; // 将该元素放到基准位置（左边）
        // 从左向右找到第一个大于等于基准的元素
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low]; // 将该元素放到右边空位
    }
    arr[low] = pivot; // 基准放到最终位置
    return low; // 返回基准的最终索引
}

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = Partition(arr, low, high);
        QuickSort(arr, low, pivotIndex - 1); // 递归排序左侧子数组
        QuickSort(arr, pivotIndex + 1, high); // 递归排序右侧子数组
    }
}
    

简单选择排序

简单选择排序（Selection Sort）是一种简单直观的排序算法。它将列表分为已排序部分和未排序部分。在每一趟排序中，从未排序部分找到最小（或最大）的元素，然后将其与未排序部分的第一个元素交换。这个过程重复进行，直到整个列表排序完成。每一趟排序都会确定一个元素在其最终位置。

void SelectionSort(int arr[], int n) {
    int i, j, minIndex;
    for (i = 0; i < n - 1; ++i) {
        minIndex = i; // 假设当前元素是最小的
        // 在未排序部分查找最小元素
        for (j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小元素的索引
            }
        }
        // 如果最小元素不是当前元素，则交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
    

堆排序

堆排序（Heap Sort）是一种基于比较的排序算法。它利用了"堆"（Heap）这种数据结构。堆是一个近似完全二叉树的结构，并且满足堆的性质：对于大顶堆，父节点的值总大于或等于其子节点的值；对于小顶堆，父节点的值总小于或等于其子节点的值。堆排序首先将待排序序列构建成一个大顶堆，此时根节点（第一个元素）是整个序列的最大值。然后，将根节点与最后一个元素交换，并将堆的大小减一，再对剩余的元素重新调整以满足大顶堆的性质。重复这个过程，直到堆的大小减为1，则排序完成。

// 调整大顶堆，确保以k为根的子树满足大顶堆性质
void MaxHeapify(int arr[], int n, int k) {
    int largest = k;       // 初始化 largest 为根节点
    int left = 2 * k + 1;  // 左子节点索引
    int right = 2 * k + 2; // 右子节点索引

    // 如果左子节点存在且比根节点大
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点存在且比当前最大值大
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点
    if (largest != k) {
        // 交换根节点和最大值节点
        int temp = arr[k];
        arr[k] = arr[largest];
        arr[largest] = temp;

        // 递归地对受影响的子树进行堆调整
        MaxHeapify(arr, n, largest);
    }
}

// 构建大顶堆
void BuildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始向前调整
    // 最后一个非叶子节点的索引是 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        MaxHeapify(arr, n, i);
    }
}

void HeapSort(int arr[], int n) {
    // 1. 构建初始大顶堆
    BuildMaxHeap(arr, n);

    // 2. 从最后一个元素开始，逐个将最大元素放到其最终位置
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素（最大值）与当前末尾元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 减小堆的大小，并对新的堆顶元素进行堆调整
        MaxHeapify(arr, i, 0);
    }
}
    

归并排序

归并排序（Merge Sort）是一种高效的、基于分治策略的排序算法。它的基本思想是将待排序序列递归地分成两半，直到每个子序列只包含一个元素（此时它被认为是已排序的）。然后，它将这些已排序的子序列两两合并，生成新的、更大的已排序子序列，直到所有子序列合并成一个完整的、已排序的序列。合并操作是归并排序的核心，它将两个已排序的子数组合并成一个已排序的数组。

// 将两个已排序的子数组 arr[low...mid] 和 arr[mid+1...high] 合并
void Merge(int arr[], int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;

    // 创建临时数组来存储两个子数组
    int* leftArr = new int[n1];
    int* rightArr = new int[n2];

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[low + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    // 合并临时数组回 arr[low...high]
    int i = 0; // leftArr 的初始索引
    int j = 0; // rightArr 的初始索引
    int k = low; // 合并后 arr 的初始索引

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 复制 leftArr 中剩余的元素
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // 复制 rightArr 中剩余的元素
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    delete[] leftArr;
    delete[] rightArr;
}

// 归并排序的主函数
void MergeSort(int arr[], int low, int high) {
    if (low < high) {
        // 找到中间点
        int mid = low + (high - low) / 2;

        // 分别对两半进行排序
        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);

        // 合并已排序的两半
        Merge(arr, low, mid, high);
    }
}