排序

AisDaeun 28 2023-10-29

排序算法主要有三种分类:算法复杂度为O(n^2)的、算法复杂度为O(n \log n)的、其他算法复杂度。

已经证明,基于比较的排序算法的最优复杂度为O(n \log n)

O(n^2)的排序算法

主要有:冒泡排序、插入排序。

O(n \log n)的排序算法

主要有:快速排序、归并排序、希尔排序

归并排序:

void merge_sort(int l, int mid, int r) {
	if (l >= r) return;
	merge_sort(l, (l + mid) >> 1, mid);
	merge_sort(mid + 1, (mid + 1 + r) >> 1, r);
	int i = l, j = mid + 1;
	for (int k = l; k <= r; ++k) 
		if (j > r || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
		else b[k] = a[j++];
	for (int k = l; k <= r; ++k) a[k] = b[k];
} 

不基于比较的排序算法

主要有:桶排序、基数排序