选择排序和冒泡排序
选择排序
第i次排序中，找到第i个元素和最后一个元素最小的值，将它置于首位
点击查看代码
void Efferve()
{
int m[5] = { 12, 8, 6, 9, 10 };
int max = m[0];
for (int i = 0; i < 4; i++)
{
for (int j = i; j < 4; j++)
{
if (m[j] < m[j + 1])
{
max = m[j + 1];
m[j + 1] = m[j];
m[j] = max;
}
}
}
}
时间空间复杂度
T（n）=T（1）
O（n）=O（N2）
冒泡排序
每次两两比较记录，如果顺序相反则交换他，每次最高位或者最低位就无需比较
void BubbleSort(int *a, int size)
{
for (int i = 0; i < size; i++)//外循环，循环每个元素
{
for (int j = 1; j < size - i; j++)//内循环进行元素的两两比较
{
if (a[j] < a[j - 1])//判断相邻元素并进行交换
{
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}
归并排序和快速排序
归并排序
点击查看代码
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)//代表已经划分为最小组1，不需要递归
return;
int len = end - start, mid = (len >> 1) + start;//len是一个模块的长度 mid是划分区块的中间值
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;//区块1和区块2
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];//这是合并主要函数 从左块第一个和右块第一个开始比较 直到有一个区块插满
while (start1 <= end1)
//这两部是如果排序好后剩下一部分（可能是左半边也可能是右半边），那么他一定是有序的，此时直接插入主数组即可
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);//reg是辅助数组
}
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为:T(n)=O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。