C/C++教程

排序算法整理C++(初赛)

本文主要是介绍排序算法整理C++(初赛),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序算法整理

常见考点

  1. 将一个乱掉的字符串排回有序(以交换为基本操作)的最少操作,就是冒泡排序。
  2. 排序算法的稳定性
  3. 排序算法的时间复杂度

排序算法的稳定性

稳定性是指排序前两个元素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]

初始.png

找到了

第一轮.png

交换,注意i ++, j -- 不然会死循环

第一轮交换.png

i 不再动了,因为a[i] = mid

第二轮.png

这里没写 i ++, j --

第二轮交换.png

这篇关于排序算法整理C++(初赛)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!