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]);	//将找到的最小元素与未排序部分的第一个元素交换位置
	}
}

时间复杂度

最坏情况：O(n²)，无论输入数据是否有序，都需要进行 n*(n-1)/2 次比较。
最好情况：O(n²)，即使列表已经有序，仍需进行相同数量的比较。
平均情况：O(n²)。

空间复杂度

O(1)，原地排序算法，不需要额外的存储空间。

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²)。

空间复杂度

O(1)，原地排序算法，不需要额外的存储空间。

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;
}

时间复杂度

所有情况：O(n logn)。

空间复杂度

O(n)，需要与原来数组相等的额外空间。