#include
#include
#include
#include
using namespace std;
class Student
{
private:
int age=0;
string username;
public:
void set_age(int age) //设置年龄
{
this->age = age;
}
void set_name(string username) //设置用户名
{
this->username = username;
}
int get_age() //获取年龄
{
return this->age;
}
string get_username() //获取用户名
{
return this->username;
}
int Compare(Student c2) //比较规则
{
return this->age - c2.age; //c1>c2返回>0;c1=c2返回0；c1
};
void Printf_student(Student stu)
{
cout << "用户名 = " << stu.get_username() << ",年龄=" << stu.get_age() << endl;
}
class CompareTo //排序类
{
public:
//冒泡排序 具有稳定性
template
void BubbleSort (T c[],long long int length) //冒泡比较规则
{
for (int i = length-1; i >0; i--)
{
for (int j = 0; j < i; j++) //从小到大排序
{
if (c[j] > c[j + 1])
{
T temp = c[j];
c[j] = c[j + 1];
c[j + 1] = temp;
}
}
}
}
//选择排序 不具有稳定性
template
void SelectSort(T c[], long long int length) //选择排序
{
for (int i = 0; i < length; i++)
{
int min_index = i; //默认最小为本次遍历的首个元素
for (int j = i + 1; j < length; j++) //从小到大
{
if (c[j] < c[min_index])
{
min_index = j;
}
}
if (min_index != i)
{
T temp = c[i];
c[i] = c[min_index];
c[min_index] = temp;
}
}
}
//插入排序 具有稳定性
template
void InsertSort(T c[], long long int length)
{
for (int i = 1; i < length; i++)
{
for (int j = i; j > 0; j--) //当前c[j]与前面的元素相比较
{
if (c[j] < c[j-1]) //找到一个大于等于当前c[j]的值，则交换元素位置
{
T temp = c[j];
c[j] = c[j-1];
c[j-1] = temp;
}
else
{
break;
}
}
}
}
//希尔排序 不具有稳定性
template
void ShellSort(T c[], long long int length) // 希尔排序规则 减小规则为h/2指导h=0结束
{
int h = 1;
//增长量确定
while (h<(length/2))
{
h = 2 * h + 1;
}
//希尔排序
while (h>=1)
{
for (int i = h; i < length; i++) //排序总次数
{
for (int j = i; j >= h; j -= h) //增量冒泡，分组方式
{
if (c[j] < c[j - h])
{
T temp = c[j];
c[j] = c[j - h];
c[j - h] = temp;
}
else
{
break;
}
}
}
h = h / 2; //增量倍减
}
}
//归并排序 具有稳定性
template
void MergeSort(T c[], int low ,int hight) // 归并排序规则，时间复杂度O(nlog2(n))
{
//用分治法对R[low..high]进行二路归并排序
int mid;
if (low < hight)
{ //区间长度大于1
mid = (low + hight) / 2; //分解
MergeSort(c, low, mid); //递归地对R[low..mid]排序
MergeSort(c, mid + 1, hight); //递归地对R[mid+1..high]排序
//组合，将两个有序区归并为一个有序区
T* arrist = new T[hight + 1]; //定义辅助数组
if (!arrist) //申请空间
{
return;
}
//定义三个指针
int i = low;
int p1 = low;
int p2 = mid + 1;
//遍历，移动p1，p2指针，比较索引值，找出小的放到辅助数组中
while (p1 <= mid && p2 <= hight)
{
if (c[p1] < c[p2])
{
arrist[i++] = c[p1++];
}
else
{
arrist[i++] = c[p2++];
}
}
while (p1 <= mid)
{
arrist[i++] = c[p1++];
}
while (p2 <= hight)
{
arrist[i++] = c[p2++];
}
for (int index = low; index <= hight; index++)
{
c[index] = arrist[index];
}
}
else
{
return;
}
}
//快速排序 不具有稳定性
template
void QuickSort(T c[], int low,int hight) // 快速排序规则
{
if (low < hight)
{
//1.分组代码
//1.1确认分界值
T key = c[low];
//1.2定义两个位置指针
int left = low;
int right = hight + 1;
//1.3分组实现
while (true)
{
while (key < c[--right]) //从右向左扫描，直到找到第一个小于分界值的索引
{
if (right == low) //若到了最小索引还找不到也退出小while循环
{
break;
}
}
while (key > c[++left]) //从左向右扫描，直到找到第一个大于分界值的索引
{
if (left == hight) //若到了最大索引还找不到也退出小while循环
{
break;
}
}
if (left >= right) //若left大于right退出大while循环
{
break;
}
else //反之交换找到的元素值
{
T temp = c[left];
c[left] = c[right];
c[right] = temp;
}
}
//1.4完成切分后、交换分界值
T dive = c[low];
c[low] = c[right];
c[right] = dive;
//2.左右子组排序，递归调用
QuickSort(c,low,right-1); //左
QuickSort(c, right + 1, hight); //右
}
else
{
return;
}
}
};
void test01()
{
Student c1, c2;
c1.set_age(18);
c1.set_name("张三");
c2.set_age(20);
c2.set_name("李四");
Student max;
if (c1.Compare(c2) >= 0)
{
max = c1;
}
else
{
max = c2;
}
Printf_student(max);
}
constexpr auto LENGTH = 1000;
void test02()
{
long long int n = LENGTH;
long long int *arr = new long long int[n];
for (long long int i = 0; i < n; i++)
{
arr[i]=n-i;
}
int arr1 [10] = {2,1,3,9,7,5,4,6,8,0};
CompareTo sort;
//sort.BubbleSort(arr, n);
//sort.SelectSort(arr,n);
//sort.InsertSort(arr, n);
//sort.ShellSort(arr, n);
//sort.MergeSort(arr, 0, n-1);
sort.QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
cout << arr[i]<<" ";
}
cout << endl;
}
int factorial(int n);//递归求阶乘
double Time_test();//测试代码执行时间
int main(int agrc,char*agrv[])
{
//int a=atoi("12323");
//cout << a << endl;
//test01();
//test02();
Time_test();
//cout << factorial(3) << endl;;
return 0;
}
//递归求阶乘
int factorial(int n) //递归求阶乘
{
if (n == 1) return 1;
else
{
return n * factorial(n - 1);
}
}
//测试代码执行时间
double Time_test()
{
clock_t start, ending;
start = clock();
test02();
ending = clock();
cout << ((double)(ending) - (double)(start)) / CLOCKS_PER_SEC << endl;
return 0;
}
