首页 / C++ / C++实现五种排序方式
C++实现五种排序方式
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++实现五种排序方式，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4823字，纯文字阅读大概需要7分钟。
内容图文
插入排序
#include <iostream>
using std::cout;
using std::endl;
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void insert_sort(int arr[], int n)
{
printArr(arr, n);
for (int i = 1; i < n; i++)
{
// 如果当前元素小于前面的已经排序好的递增序列的最后一个元素
if (arr[i] < arr[i - 1])
{
cout << "arr[" << i << "] < "
<< "arr[" << i - 1 << "] " << endl;
int tmp = arr[i];
// 我们需要将这个元素不断移动到对应的位置
int j = i;
for (j = i; j >= 1; j--)
{
cout << "j: " << j << " arr[j-1]: " << arr[j - 1] << " "
<< "tmp: " << tmp << endl;
if (arr[j - 1] > tmp)
{
arr[j] = arr[j - 1];
cout << "移动"
<< "arr[" << j + 1 << "]" << endl;
}
else
{
break;
}
}
if (j != i)
{
arr[j] = tmp;
printArr(arr, n);
}
}
}
}
int main()
{
const int num = 5;
int arr[num] = {1, 4, 3, 6, 2};
insert_sort(arr, num);
return 0;
}
冒泡排序
#include <iostream >
using std::cout;
using std::endl;
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void bubble_sort(int arr[], int n)
{
bool flag = false;
for (int i = 0; i < n; i++)
{
flag = false;
// 外层循环i次之后，相当于排序好了i个位置
for (int j = 0; j < n - i - 1; j++)
{
// 不断的将较大的值传递到后面去
// 所以最后的数据是最大的
if (arr[j + 1] < arr[j])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
// 如果一趟过程中没有执行冒泡操作
// 那么说明已经排序好了，可以结束
if (!flag)
{
return;
}
}
}
int main()
{
const int num = 5;
int arr[num] = {1, 4, 3, 6, 2};
cout << "排序之前: ";
printArr(arr, num);
bubble_sort(arr, num);
cout << "排序之后: ";
printArr(arr, num);
}
选择排序
#include <iostream>
using std::cout;
using std::endl;
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
// 每一次选择一个最小的值放到前面
void select_sort(int arr[], int n)
{
printArr(arr, n);
for (int i = 0; i < n; i++)
{
int min = arr[i];
int index = i;
// 遍历之后的元素，获取到最小的元素
for (int j = i+1; j < n; j++)
{
if (arr[j] < min)
{
min = arr[j];
index = j;
}
}
// 交换最小值和第i个元素
if (index != i)
{
int tmp = arr[i];
arr[i] = arr[index];
arr[index] = tmp;
}
}
printArr(arr, n);
}
int main()
{
const int num = 5;
int arr[num] = {1, 4, 3, 6, 2};
select_sort(arr, num);
return 0;
}
归并排序
#include <iostream>
using std::cout;
using std::endl;
// 输出指定索引的
void printArr(const int *arr, int left, int right)
{
for (int i = left; i <= right; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
// 输出数组信息
void printArr(const int *arr, int n)
{
printArr(arr, 0, n-1);
}
void merge(int *arr, const int left, const int mid, const int right)
{
// cout << "enter merge function "<<endl;
// 申请一个临时空间
int *tmp = new int[right - left + 1];
// 进行合并
int i = left;
int j = mid + 1;
int k = 0;
// 将[left, mid], [mid+1, right]两个有序数组进行合并
while (i <= mid && j <= right)
{
if (arr[i] < arr[j])
{
tmp[k] = arr[i];
k++;
i++;
}
else
{
tmp[k] = arr[j];
k++;
j++;
}
}
// cout << "merge first step done"<<endl;
while (i <= mid)
{
tmp[k] = arr[i];
k++;
i++;
}
while (j <= right)
{
tmp[k] = arr[j];
k++;
j++;
}
// cout << "merge second stemp done"<<endl;
// cout << "original: ";
// printArr(arr, left, right);
// cout << "tmp: ";
// printArr(tmp, right-left+1);
// 将数据赋值给arr对应的位置
k = 0;
for (int i = left; i <= right; i++)
{
arr[i] = tmp[k];
k++;
}
// cout << "after: ";
// printArr(arr, left, right);
// 释放空间
delete[] tmp;
}
void sort(int *arr, const int left, const int right)
{
// cout << "sort: "<<left << " to " << right<<endl;
if (left >= right)
{
return;
}
int mid = (right - left) / 2 + left;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void merge_sort(int *arr, const int n)
{
sort(arr, 0, n - 1);
}
int main()
{
const int num = 6;
int arr[num] = {3, 4, 1, 6, 2, 5};
cout << "排序之前: ";
printArr(arr, num);
merge_sort(arr, num);
cout << "排序之后: ";
printArr(arr, num);
return 0;
}
快速排序
#include <iostream>
using std::cout;
using std::endl;
void printArr(const int *arr, int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void sort(int *arr, int left, int right)
{
// 停止条件
if (left >= right)
{
return;
}
// 选择轴心然后移动元素
int pivot = arr[left];
// cout << "pivot: " << pivot << endl;
int i = left, j = right;
while (left < right)
{
// cout << "left<right: " << left << " < " << right << endl;
while (left < right && arr[right] > pivot)
{
right--;
}
// cout << "right " << right << "----" << endl;
if (left < right)
{
// cout << "swap: " << left << right << endl;
arr[left] = arr[right];
left++;
}
while (left < right && arr[left] < pivot)
{
left++;
}
// cout << "left: " << left << endl;
if (left < right)
{
// cout << "swap: " << left << right << endl;
arr[right] = arr[left];
right--;
}
}
arr[left] = pivot;
sort(arr, i, left);
sort(arr, left + 1, j);
}
void quick_sort(int *arr, int n)
{
printArr(arr, n);
sort(arr, 0, n - 1);
printArr(arr, n);
}
int main()
{
const int num = 6;
int arr[num] = {3, 4, 1, 6, 2, 5};
quick_sort(arr, num);
return 0;
}
内容总结
以上是互联网集市为您收集整理的C++实现五种排序方式全部内容，希望文章能够帮你解决C++实现五种排序方式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】