排序可以说是相当常用的一类数据处理方式，而进行排序的方法也是多种多样的，此文主要记录经典的排序算法，并阐明基本原理

开始之前

  • 所有的排序算法以函数形式展现，采用C语言编写
  • 函数风格统一，命名规则同ASort，A为排序方法名称，首字母大写，传参均仅传入数组及其大小，函数类型为void，即直接将原数组进行排序
  • 所有排序的终点，也就时排序后的结果，为从大到小排序

为了让排序更好的进行，首先编写交换函数，即Swap()函数

代码：

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#define ELEMENT_TYPE int


void Swap(ELEMENT_TYPE *x, ELEMENT_TYPE *y) {
    ELEMENT_TYPE temp = *x;
    *x = *y;
    *y = temp;
}

冒泡排序

冒泡排序可谓是相当经典的一个排序算法，记得自己大一面试学校社团之时，学长让第一个去了解的排序算法就是冒泡算法

实现思路

  • 冒泡，顾名思义，就是将需排序的元素，看作大小不同的泡泡进行处理
  • 首先将数组进行一趟从头至尾的扫描，遇到后者比前者大的元素，就将二者交换，一趟扫描之后，最大的元素实现沉底
  • 那么只需要扫描n趟，就可让数组排列整齐

结合上述思路，我们可以写出以下代码：

代码1

1
2
3
4
5
6
void BubbleSort (ELEMENT_TYPE a[], int n) { // 冒泡
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (a[j] > a[j+1])
                Swap(&a[j], &a[j+1]);
}
  • 上述代码相当简单，但是还可进行优化
  • 因为冒泡排序过程中，有可能只进行小于n趟就已经排序完成，之后的扫描都属于无用功，所以加一标记，使其在扫描一趟的过程中，若无元素交换，则直接结束循环

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort (ELEMENT_TYPE a[], int n) { // 冒泡
    for (int i = 0; i < n; ++i) {
        int flag = 0;
        for (int j = 0; j < n; ++j) {
            if (a[j] > a[j+1]) {
                Swap(&a[j], &a[j+1]);
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}

如此一来，其最好情况为O(N)，而最坏情况为O(N^2)

插入排序

插入排序也是简单排序的一种，也是比较常见的一种算法

实现思路

  • 为了更好地理解插入算法，我们引入打牌时的实例
  • 打牌时，为方便出牌，我们一般将牌有顺序地拿着，当摸一张牌时，我们会与手中已排序完成的牌进行比较，以插入到合适的位置
  • 插入排序也是模拟了这一过程，首先假设数组中的首个元素已经 “拿在手中” ，之后将数组中的元素依次取出，进行插入

代码

1
2
3
4
5
6
7
8
9
void InsertionSort(ELEMENT_TYPE a[], int n) {   // 插入
    int i, j;
    for (i = 1; i < n; ++i) {
        ELEMENT_TYPE temp = a[i];
        for (j = i; j > 0 && a[j-1] > temp; j--)
            a[j] = a[j-1];
        a[j] = temp;
    }
}
  • 代码在插入的时候是从后往前比较的，也就是从i到0
  • 插入排序无需进行数字的交换，某种程度来说代码量是少于冒泡的
  • 其最好情况为O(N)，而最坏情况为O(N^2)

选择排序

提到简单排序，就不得不说选择排序

实现思路

  • 选择排序很好理解，就是首先遍历一遍数组，找到，该数组中最小的元素，与数组首位元素进行交换
  • 这种交换需要进行n次，所以遍历也会进行n次

代码

1
2
3
4
5
6
7
8
9
10
void SelectionSort (ELEMENT_TYPE a[], int n) {  // 选择
    for (int i = 0; i < n; ++i) {
        int min = i;
        for (int j = i; j < n; ++j) {
            if (a[j] < a[min])
                min = j;
        }
        Swap(&a[min], &a[i]);
    }
}
  • 选择排序的时间复杂度是恒定的，无所谓最好最坏，均为 O(N^2)