千家信息网

如何用C++实现十大排序算法

发表于:2024-11-20 作者:千家信息网编辑
千家信息网最后更新 2024年11月20日,这篇文章主要讲解了"如何用C++实现十大排序算法",文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习"如何用C++实现十大排序算法"吧!冒泡排序// 冒泡排序
千家信息网最后更新 2024年11月20日如何用C++实现十大排序算法

这篇文章主要讲解了"如何用C++实现十大排序算法",文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习"如何用C++实现十大排序算法"吧!

冒泡排序

// 冒泡排序// 从小到大// 时间复杂度 平均 n^2 最好 n 最坏n^2// 空间复杂度 1// 内排序,稳定排序void bubbleSort(int arr[] , int length) {    for (int i = 0; i < length - 1; ++i) {        for (int j = i; j < length; ++j) {            if (arr[i] > arr[j]){                swap(arr[i],arr[j]);            }        }    }}

选择排序

//选择排序// 时间复杂度 平均 n^2 最好 n^2 最坏n^2// 空间复杂度 1// 内排序 不稳定void selectSort(int arr[], int length) {    for (int i = 0; i < length; ++i) {        int minIndex = i;        for (int j = i; j < length; ++j) {            if (arr[minIndex] > arr[j]) {                minIndex = j;            }        }        swap(arr[i], arr[minIndex]);    }}

插入排序

// 插入排序// 时间复杂度 平均 n^2 最好 n 最坏n^2// 空间复杂度 1// 内排序,稳定排序void insertSort(int arr[], int length) {    for (int i = 1; i < length; ++i) {        int preIndex = i - 1;        int current = arr[i];        while (preIndex >= 0 && current <= arr[preIndex]) {            arr[preIndex + 1] = arr[preIndex];            preIndex--;        }        arr[preIndex + 1] = current;    }}

希尔排序

// 希尔排序// 时间复杂度 平均 n^1.3 最好 n 最坏n^2// 空间复杂度 1// 内排序,不稳定排序void shellSort(int arr[], int length) {    for (int step = length / 2; step >= 1; step /= 2) {        for (int i = step; i < length; ++i) {            int preIndex = i - step;            int current = arr[i];            while (preIndex >= 0 && current <= arr[preIndex]) {                arr[preIndex + step] = arr[preIndex];                preIndex -= step;            }            arr[preIndex + step] = current;        }    }}

归并排序

// 归并排序// 时间复杂度 平均 nlogn 最好 nlogn 最坏 nlogn// 空间复杂度 n// 稳定 外排序void mergeSort(int arr[], int left, int right) {    if (left >= right) {        return;    }    int mid = (left + right) >> 1;    mergeSort(arr, left, mid);    mergeSort(arr, mid + 1, right);    merge(arr, left, mid, right);}void merge(int *arr, int left, int mid, int right) {    int res[right - left + 1];    int left_index = left;    int right_index = mid + 1;    int index = 0;    while (left_index <= mid && right_index <= right) {        if (arr[left_index] < arr[right_index]) {            res[index] = arr[left_index];            index++;            left_index++;        } else {            res[index] = arr[right_index];            index++;            right_index++;        }    }    while (left_index <= mid) {        res[index] = arr[left_index];        index++;        left_index++;    }    while (right_index <= right) {        res[index] = arr[right_index];        index++;        right_index++;    }    for (int i = 0; i < right - left + 1; ++i) {        arr[left + i] = res[i];    }}

快速排序

// 快速排序// 时间复杂度 平均nlogn 最好nlogn 最坏 n^2// 空间复杂度 logn// 内排序 不稳定void quickSort(int arr[], int left, int right) {    if (left >= right) {        return;    }    int p = arr[left];    int low = left, high = right;    while (low < high) {        while (low < high && arr[high] >= p) high--;        arr[low] = arr[high];        while (low < high && arr[low] <= p) low++;        arr[high] = arr[low];    }    arr[low] = p;    quickSort(arr, left, low - 1);    quickSort(arr, low + 1, right);}

堆排序

// 堆排序// 时间复杂度 平均nlogn 最好nlogn 最坏 nlogn// 空间复杂度 1// 内排序 不稳定void heapify(int arr[], int i, int length) {    int left = 2 * i + 1;    int right = 2 * i + 2;    int max_index = i;    if (left < length && arr[max_index] < arr[left]) {        max_index = left;    }    if (right < length && arr[max_index] < arr[right]) {        max_index = right;    }    if (max_index != i) {        swap(arr[i], arr[max_index]);        heapify(arr, max_index, length);    }}void heap_sort(int arr[], int length) {    for (int i = length / 2 - 1; i >= 0; --i) {        heapify(arr, i, length);    }// 构建小顶堆    for (int i = length - 1; i > 0; --i) {        swap(arr[0], arr[i]);        heapify(arr, 0, i);    }}

感谢各位的阅读,以上就是"如何用C++实现十大排序算法"的内容了,经过本文的学习后,相信大家对如何用C++实现十大排序算法这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是,小编将为大家推送更多相关知识点的文章,欢迎关注!

0