常用排序算法 - 帖子

先介绍时间复杂度和稳定性，实现的代码后续补充 ~~(鸽)~~

冒泡排序

时间复杂度：平均和最坏情况，最好情况
稳定性：稳定
简介：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

流程

初始状态：未排序的数组。
第一轮：从第一个元素开始，比较相邻的元素，如果第一个比第二个大，就交换它们的位置。这样，每一对相邻的元素都会进行比较，直到最后一对，这时最大的元素会被放到最后的位置。
后续轮次：重复上述过程，每次比较时都忽略已经排序好的最大元素。
完成状态：当没有元素需要交换时，排序完成。

实现代码

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)    
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

选择排序

时间复杂度：平均和最坏情况，最好情况
稳定性：不稳定
简介：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

流程

初始状态：未排序的数组。
第一轮：搜索整个数组以找到最小（或最大）的元素，然后将其与数组的第一个元素交换位置。
后续轮次：从剩下的未排序元素中继续寻找最小（或最大）元素，然后与数组的第二个元素交换位置。如此重复。
完成状态：直到整个数组排序完成。

实现代码

void selectionSort(int arr[], int n) {
    int min_idx;
    for (int i = 0; i < n-1; i++) {
        min_idx = i;
        for (int j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
        swap(arr[min_idx], arr[i]);
    }
}

插入排序

时间复杂度：平均和最坏情况，最好情况
稳定性：稳定
简介：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

流程

初始状态：未排序的数组。
第一轮：假设第一个元素已经被排序，从第二个元素开始，将这个元素与之前的元素比较，如果它更小，就继续向前比较，直到找到它的正确位置，并将其插入。
后续轮次：重复上述过程，每次都将未排序的第一个元素插入到已排序的序列中的正确位置。
完成状态：当所有元素都被插入到正确的位置时，排序完成。

实现代码

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

快速排序

时间复杂度：平均，最坏情况，最好情况
稳定性：不稳定
简介：通过选取一个元素作为基准，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。

流程

初始状态：未排序的数组。
分区：选择一个元素作为"基准"（pivot），重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归排序：递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。
完成状态：递归完成，数组排序完成。

实现代码

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  
    int i = (low - 1);  
    for (int j = low; j <= high- 1; j++) {
        if (arr[j] < pivot) {
            i++;    
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

归并排序

时间复杂度：平均和最坏情况，最好情况
稳定性：稳定
简介：建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

流程

初始状态：未排序的数组。
分解：将数组分成两半，然后再递归地将这两半分成更小的部分，直到每个部分只有一个元素（认为单个元素是已排序的）。
合并：将两个已排序的部分合并成一个有序的数组。对每一对这样的部分，比较它们的元素并按顺序放入一个新的数组中，重复这个过程直到整个数组被合并且排序。
完成状态：当所有分割的部分被合并回一个数组，且这个数组是有序的，排序完成。

实现代码

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

希尔排序

时间复杂度：取决于间隔序列，最好情况，平均情况取决于间隔序列，最坏情况
稳定性：不稳定
简介：是插入排序的一种更高效的改进版本，也称缩小增量排序。

流程

初始状态：未排序的数组。
间隔选择：选择一个间隔序列，比如数组长度的一半作为间隔，然后进行插入排序。
间隔减少：完成一轮插入排序后，选择一个更小的间隔（通常是上一个间隔的一半），再次进行插入排序。
完成状态：当间隔减少到1，整个数组将进行一次标准的插入排序，此时数组已经基本上是排序的状态，插入排序将完成最终的排序工作。

实现代码

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            int temp = arr[i];
            int j;            
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

堆排序

时间复杂度：平均和最坏情况，最好情况
稳定性：不稳定
简介：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质。

流程

初始状态：未排序的数组。
建堆：将整个数组重新排列成一个最大堆，确保所有的父节点都比它的子节点大。
排序：由于堆的最大元素总是位于根节点，可以通过将其与数组的最后一个元素交换并减少堆的大小来固定它的位置。然后重新调整剩余元素，使其再次成为最大堆。
完成状态：重复上述过程，直到堆的大小为1，此时数组已经完全排序。

实现代码

// 函数用于调整索引为 i 的节点，使其满足最大堆的性质
void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大值为根节点
    int l = 2 * i + 1; // 左子节点
    int r = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // 如果右子节点大于目前的最大值
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // 如果最大值不是根节点，交换它们
    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 函数处理减少的堆
        heapify(arr, i, 0);
    }
}