排序算法整理C++

排序算法整理C++

常见考点

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

排序算法的稳定性

稳定性是指排序前两个元素a1 = a2，a1在前。排序过后，倘若a1始终在前，则算法是稳定的，否则是不稳定的。

稳定的

冒泡排序、插入排序、归并排序、基数排序（简写）

不稳定的

堆排序（简写）、快速排序、希尔排序、选择排序

各个算法细锁

冒泡排序

基本思路：双重循环遍历数组，交换两个相邻的逆序的数字。时间复杂度一般 - ，最坏 - ，最好。

代码

1
2
3
4
5
6
7
8
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)，但显然这个程序怎么看都是，实际上是优化过的。考试的时候记住就行。

选择排序

基本思路：遍历一遍数组 i in (1, n + 1)，从 i 数开始遍历到后面，寻找最小的比它小的数，与它交换。

关于为什么选择排序是不稳定的？

举个例子：5 3 5 2 7
第一个5会与2交换

无论如何都是。

代码

1
2
3
4
5
6
7
8
9
10
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，但我不知道原理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    }
    
}

插入排序

基本思路：从第二个元素开始，和前面的元素比较，倘若前面的元素更大就往前移，直到遇到一个小于等于自己的元素。

最优： 平均： 最差：

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i = 2; i <= n; i ++)
{
    int key = a[i];
    int j = i - 1;
    while(j >= 1 && a[j] > key)
    {
        a[j + 1] = a[j];
        j --;
    }
    a[j + 1] = key;
}

希尔排序

一种插入排序的优化版。

思路：先把所有数分组（很常见的排序算法思路），怎么分？比如数组一共8个数那就隔4隔为一组。a[0]a[4]一组，a[1]a[5]一组。之后组内排序。然后减少分组间隔为2。一次类推，直至间隔为1。

没听懂可以看看视频

六分钟彻底弄懂希尔排序，简单易懂_bilibili

为什么说希尔排序是优化版的插入排序，就是因为一次的组内排序都是插入排序实现的。

平均，最坏，最好。

代码就不放了，我也没敲过

堆排序

想法就是维护一个大根堆，每一次取出根节点。

时间复杂度都是。

基数排序

时间复杂度

快速排序

基本思路：找一个基准数，先由i从左边出发，找到一个小于，j再从右边出发，找一个小于基准数的数。分开区间，重复此操作。时间复杂度平均，最优也是，最差。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int random_real(int l_b, int r_b){
    srand(time(0));
    return rand()%(r_b - l_b + 1) + l_b;
}

void quick_sort(int l, int r)
{
    if(l >= r)
        return;
    int mid = random_real(l, r);
    swap(a[mid], a[l]);
    int i = l, j = r;
    while(i < j){
        while(i < j && a[j] >= a[l])
            j --;
        while(i < j && a[i] <= a[l])
            i ++;
        if(i != j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    quick_sort(l, i - 1);
    quick_sort(i + 1, r);

}

其他

2024年07月04日，又敲了一遍快排，发现一直报SIGFPE(除0)的错，查了半天发现是函数结束条件if(l > r)写成了 if(l == r)导致可能l > r还不return函数。引以为戒。

还有一个☝🏻问题，就是指针i初始化时必须让i = l，我写的时候将i = l + 1。问题在哪里呢？当仅仅排序两个数字时，模拟一下就会发现是会排反的。