1.选择排序
**基本思想：**每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。
函数实现：
void selectSort(int a[], int n) {
//未开始排序时 已排序部分为0 因此从0开始遍历
for (int i = 0; i < n - 1; i++) { //n-1是因为最后一个未排序数字已经是最大且避免越界
int minIndex = i; //每次假定未排序部分的第一个元素作为最小值
for (int j = i + 1; j < n; j++){ //遍历剩余未排序部分
if (a[j] < a[minIndex]) { //如果找到更小的元素
minIndex = j;
}
}
swap(a[i], a[minIndex]); //将找到的最小元素与未排序部分的第一个元素交换位置
}
}
时间复杂度
空间复杂度
2.冒泡排序
**基本思想：**通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。
(名字由来：元素就像"气泡"一样逐渐"浮"到列表的顶端，大元素上浮快而小元素上浮慢。)
函数实现：
for (int i = 0; i < n - 1; i++) { //i每自增一次，冒泡完成一次
for (int j = 0; j < n-1-i; j++) { //从0遍历到最后一位，n-i为未排序区间长度，n-1-i是为了防止第一次冒泡j+1越界访问数组
if (a[j] > a[j+1]) { //冒泡
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
时间复杂度
最坏情况：O(n²)，当列表是逆序时。
最好情况：O(n)，当列表已经有序时。
平均情况：O(n²)。
空间复杂度
3.归并排序
基本思想：
采用分治与递归思想将数组分段排序后合并。
将数组不断二分成更小的数组，当数组长度为 1 时，该数组就已经是有序的，不用再分解；此时就可以将两个为1的数组进行合并。
函数实现：
//c++
void merge(int a[], int b[], int c[], int alen, int blen) { //需要保证a,b数组均为有序数组，c为合并后的数组
int i = 0, j = 0, k = 0;
while (i < alen && j < blen) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}
// 如果此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
for (; i < alen; ++i, ++k) c[k] = a[i];
for (; j < blen; ++j, ++k) c[k] = b[j];
}
void mergesort(int arr[], int len) {
if (len <= 1) return;
int mid = len / 2;
int* left = new int[mid]; //存放左半部分数组
int* right = new int[len - mid]; ////存放右半部分数组
// 拷贝左半部分
for (int i = 0; i < mid; ++i) {
left[i] = arr[i];
}
// 拷贝右半部分
for (int i = 0; i < len - mid; ++i) {
right[i] = arr[mid + i];
}
// 递归排序左右两部分
mergesort(left, mid);
mergesort(right, len - mid);
// 合并
merge(left, right, arr, mid, len - mid);
delete[] left;
delete[] right;
}
时间复杂度
空间复杂度