这篇文章主要讲解了“怎么用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++实现十大排序算法这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4444206/blog/5044461