【C++算法】几种排序算法 - ToB企服应用市场:ToB评测及商务社交产业平台

# include <bits/stdc++.h>
# include "time.h"
using namespace std;
//插入排序
void InsertSort1(int *a, int n)
{
int i, j;
for (i = 1; i < n; i++)//默认第一个元素以排序，从第二个开始（即使第一个不是最小的，后面也会让这个元素往后移的）
if (a[i] < a[i - 1])
{
int temp = a[i]; //保存要比较的值
for (j = i - 1; j >= 0 && a[j] > temp; j--) //以选择元素为起始点，从后向前查找待插入位置
a[j + 1] = a[j];
a[j + 1] = temp;
}
for (int i = 0;i < 20;i++)
cout << a[i] << " ";
cout << endl;
}
//选择排序
void SelectSort(int *a, int n)
{
int i, j, min, t;
for (i = 0;i < n - 1;i++) //这个for循环是排序次数，n个数只需要排序n-1次，最后只剩一个数不需要排序
{
min = i;
for (j = i + 1;j < n;j++) //这个for循环是寻找下标为i的元素后面有没有比它更小的数
{
if (a[j] < a[min])
min = j;
}
if (min != i)
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
for (int i = 0;i < 20;i++)
cout << a[i] << " ";
cout << endl;
}
void Merge(int A[], int Temp[], int L, int R, int RightEnd)
{
int LeftEnd = R - 1;
int p = L, i;
int num = RightEnd - L + 1;
//先合并最短序列的长度的个数个元素
while (L <= LeftEnd && R <= RightEnd)
{ //这个循环执行完左数组和右数组一定有一个已经被搬空到temp中去了
if (A[L] <= A[R])
Temp[p++] = A[L++];
else
Temp[p++] = A[R++];
}
while (L <= LeftEnd)
Temp[p++] = A[L++];
//判断如果是右侧数组还有剩余
while (R <= RightEnd)
Temp[p++] = A[R++];
// 将辅助空间中的值拷贝到原列表中，完成排序
for (i = 0;i < num;i++, RightEnd--) //要从RightEnd开始赋值，因为不是每次排序的数组都是从0下标开始的，而L又被改过了，所以只能从RightEnd开始赋值
A[RightEnd] = Temp[RightEnd];
}
//递归拆分m_sort，递归归并Merge
void m_sort(int arr[], int* temp, int L, int right_end)
{
int center;
if (L < right_end)
{
center = (L + right_end) / 2;
m_sort(arr, temp, L, center);
m_sort(arr, temp, center + 1, right_end);
Merge(arr, temp, L, center + 1, right_end);
}
}
//归并排序
void merge_Sort(int arr[], int length)
{
int* temp = (int*)malloc(length * sizeof(int));
if (temp == NULL) {
return;
}
m_sort(arr, temp, 0, length - 1); //发送待排序数组，辅助数组，最左边元素下标，最右边元素下标
for (int i = 0;i < 20;i++)
cout << arr[i] << " ";
cout << endl;
free(temp);
temp = NULL;
}
int main(void)
{
int arr1[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
int arr2[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
int arr3[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
clock_t beg, end;
beg = clock();
merge_Sort(arr3, 20);
end = clock();
double time = (double)(end - beg) / CLOCKS_PER_SEC;
cout << "归并排序运行时间为";
printf("%lf\n", time);
beg = clock();
SelectSort(arr2, 20);
end = clock();
time = (double)(end - beg) / CLOCKS_PER_SEC;
cout << "选择排序运行时间为";
printf("%lf\n", time);
beg = clock();
InsertSort1(arr1, 20);
end = clock();
time = (double)(end - beg) / CLOCKS_PER_SEC;
cout << "插入排序运行时间为";
printf("%lf\n", time);
return 0;
}

复制代码