排序算法整理
常见考点
- 将一个乱掉的字符串排回有序(以交换为基本操作)的最少操作,就是冒泡排序。
- 排序算法的稳定性
- 排序算法的时间复杂度
排序算法的稳定性
稳定性是指排序前两个元素a1 = a2,a1在前。排序过后,倘若a1始终在前,则算法是稳定的,否则是不稳定的。
稳定的
不稳定的
各个算法细锁
冒泡排序
基本思路:双重循环遍历数组,交换两个相邻的逆序的数字。时间复杂度一般 - \(O(n^2)\),最坏 - \(O(n^2)\),最好\(O(n)\)。
代码
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n - i; j ++)
{
if(a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}
}
都说最优复杂度是O(N),但显然这个程序怎么看都是\(O(n^2)\),实际上\(O(n)\)是优化过的。考试的时候记住就行。
选择排序
基本思路:遍历一遍数组 i in (1, n + 1),从 i 数开始遍历到后面,寻找最小的比它小的数,与它交换。
无论如何都是\(O(n^2)\)。
代码
for(int i = 1; i < n; i ++)
{
int min = i;
for(j = i + 1; j <= n; j ++)
{
if(a[min] > a[j])
min = j;
swap(a[i], a[min]);
}
}
归并排序
分治思想,将数组中所有的数递归分为两个一组
网上讲的挺好的归并排序MergeSort(通俗易懂_kevinmeanscool的博客-CSDN
这个算法还能用来求逆序对,所以在复赛中也挺重要 虽然现在一般复赛不会考,只要在else后面(代码)加一句ans += mid - i +1
,但我不知道原理。
代码
void merge_sort(int a[], int l, int r){
if(l >= r)
return;
int mid = l + r >> 1;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
int k = 0;
int i = l;
int j = mid + 1;
while(i <= mid && j <= r){
if(a[i] <= a[j])
f[k ++] = a[i ++];
else
f[k ++] = a[j ++];
}
while(i <= mid) f[k ++] = a[i ++];
while(j <= r) f[k ++] = a[j ++];
for(i = l, j = 0; i <= r; i ++, j ++){
a[i] = f[j];
}
}
快速排序
基本思路:找一个基准数,先由i从左边出发,找到一个小于,j再从右边出发,找一个小于基准数的数。分开区间,重复此操作。时间复杂度平均\(O(nlon_n)\),最优也是\(O(nlon_n)\),最差\(O(n^2)\)。
代码
void qsort(int l, int r)
{
int mid = a[l + r >> 1];
int i = l, j = r;
do{
while(a[i] < mid) i ++;
while(a[j] > mid) j --;
if(i <= j)
{
swap(a[i], a[j]);
i ++;
j --;
}
}while(i <= j);
if(l < j) qsort(l, j);
if(i < r) qsort(i, r);
}
int main()
{
qsort(1, n);
}
根据代码图解
(如果加载不出来请刷新,因为图放在Github):
数组:[3, 2, 9, 5, 1, 8, 2]
找到了
交换,注意i ++, j -- 不然会死循环
i 不再动了,因为a[i] = mid
这里没写 i ++, j --