算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n)$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(n log n)$	$O(n log n)$	$O(n^2)$	$O(log n)$	不稳定
归并排序	$O(n log n)$	$O(n log n)$	$O(n log n)$	$O(n)$	稳定
堆排序	$O(n log n)$	$O(n log n)$	$O(n log n)$	$O(1)$	不稳定
基数排序	$O(d*(n+k))$	$O(d*(n+k))$	$O(d*(n+k))$	$O(n+k)$	稳定

冒泡排序

/**
 * @brief 冒泡排序
 * @param arr 待排序数组
 * @param len 数组长度
 * @note 每次将最大的元素放到数组末尾
 */
void bubbleSort(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len -i- 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

选择排序

/**
 * @brief 选择排序
 * @param arr 待排序数组
 * @param len 数组长度
 * @note 每次将最小的元素放到数组开头
 */
void selectSort(int arr[], int len) {
    for (int i = 0; i < len; ++i) {
        int min_index = i;
        for (int j = i; j < len; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = tmp;
    }
}

插入排序

/**
 * @brief 插入排序
 * @param arr 待排序数组
 * @param len 数组长度
 * @note 将未排序的元素插入已排序的数组中
 */
void insertionSort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        int temp = arr[i], j = i;
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            --j;
        }
        arr[j] = temp;
    }
}

希尔排序

/**
 * @brief 希尔排序
 * @param arr 待排序数组
 * @param len 数组长度
 * @note 通过分组，将数组分为若干子数组，对子数组进行插入排序
 */
void shellSort(int arr[], int len) {
    for (int gap = len / 2; gap > 0; gap /= 2) {  // 控制分组步长
        for (int i = 0; i < len; i++) {           // 遍历数组中所有元素
            for (int j = i; j < len; j += gap) {  // 遍历分组
                int temp = arr[j], k = j;
                while (k - gap >= 0 && arr[k - gap] > temp) {  // 插入排序
                    arr[k] = arr[k - gap];
                    k -= gap;
                }
                arr[k] = temp;
            }
        }
    }
}

快速排序

/**
 * @brief 快速排序
 * @param arr 待排序数组
 * @param start 起始位置
 * @param end 结束位置
 * @note 基准点为第一个元素
 */
void quickSort(int arr[], int start, int end) {
    int left = start, right = end - 1;
    if (left >= right) {
        return;
    }
    int pivot = arr[left];

    while (left < right) {
        while (arr[right] >= pivot && left < right) {
            --right;
        }
        arr[left] = arr[right];
        while (arr[left] <= pivot && left < right) {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr, start, left);
    quickSort(arr, left + 1, end);
}

堆排序

采用了大小根堆的思想,和大小根堆实现一样

归并排序

/**
 * @brief 归并排序
 * @param arr 待排序数组
 * @param tmp 临时数组
 * @param start 起始位置
 * @param end 结束位置
 */
void mergeSort(int arr[], int tmp[], int start, int end) {
    if (start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(arr, tmp, start, mid);
    mergeSort(arr, tmp, mid + 1, end);

    int i = start, j = mid + 1;
    for (int k = start; k <= end; ++k) {
        if (i > mid) {
            tmp[k] = arr[j++];
        } else if (j > end) {
            tmp[k] = arr[i++];
        } else if (arr[i] <= arr[j]) {
            tmp[k] = arr[i++];
        } else {
            tmp[k] = arr[j++];
        }
    }

    for (int k = start; k <= end; ++k) {  // 将tmp中分组排序后的结果写回原数组
        arr[k] = tmp[k];
    }
}

基数排序

void radixSort(vector<int>& vec) {
    int max = *max_element(vec.begin(), vec.end());
    int mod = 10, dev = 1;
    vector<vector<int>> bucket(10);

    for (int i = 0; i < to_string(max).length(); ++i, mod *= 10, dev *= 10) {
        bucket.resize(10);
        // 将 vec 分桶
        for (int j = 0; j < vec.size(); ++j) {
            int index = vec[j] % mod / dev;
            bucket[index].emplace_back(vec[j]);
        }
        int index = 0;
        // 将桶中的元素重新放入 vec
        for (const auto& item : bucket) {
            for (const auto& it : item) {
                vec.at(index++) = it;
            }
        }
        bucket.clear();
    }
}

int main() {
    srand(time(NULL));
    vector<int> data;
    cout << "before: ";
    for (int i = 0; i < 10; ++i) {
        data.push_back(rand() % 100);
        cout << data.back() << " ";
    }
    cout << endl;
    radixSort(data);
    cout << "after: ";
    for (const auto& item : data) {
        cout << item << " ";
    }
    cout << endl;
    return 0;
}

贡献者

pinkdopeybug

版权所有

版权归属：PinkDopeyBug

许可证：署名 4.0 国际 (CC-BY-4.0)