一、冒泡排序

冒泡排序的本质在于交换，即每次通过交换的方式把当前剩余元素的最大值移动到一端，而当前剩余元素减少为0时，排序结束。

对于一个拥有 n 个元素的数组进行冒泡排序，整个过程执行 n-1 趟，每一趟从左到右依次比较相邻的两个数，如果大的数在左边，则交换这两个数，当该趟结束时，该趟最大数被移动到当前剩余数的最右边。

具体代码实现如下：

#include<stdio.h>

void BubbleSort(int a[], int n) {
    for(int i = 1; i <= n-1; i++) {    //排序过程进行n-1趟
        for(int j = 0; j < n-i; j++) {    //第i趟从a[0]到a[n-i-1]都与下一个数进行比较，每趟结束后最大的数在a[n-i]
    	    if(a[j] > a[j+1]) {    //如果左边的数更大，则交换a[j]和a[j+1]
    		    int temp = a[j];
    		    a[j] = a[j+1];
    		    a[j+1] = temp;
		    }
	    }
    }
}

int main() {
    int a[50], n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {    //依次输入未排序的数组元素
        scanf("%d", &a[i]);
    }
    Bubble(a, n);
    for(int i = 0; i < n; i++) {
	    printf("%d ", a[i]);
    }
    return 0;
}

二、选择排序

1、简单选择排序

简单选择排序是众多选择排序中最常用的一种。简单排序的基本思想是：首先，选出最小的数，放在第一个位置；然后，选出第二小的数，放在第二个位置；以此类推，直到所有的数从小到大排序。

简单排序的具体实现为：对于数组 a[n]，令 i 从 0 枚举到 n-1，进行 n 趟操作，每趟从待排序部分 [i，n-1] 中选择最小的元素，令其与待排序部分的第一个元素 a[i] 进行交换，这样元素 a[i] 就会与当前有序区间 [0，i-1] 形成新的有序区间 [1，i]，在进行 n 趟操作后便可完成排序。

具体代码实现如下：

#include<stdio.h>

void SimpleSelectSort(int a[], int n) {
    int mix, temp;
    int i, j;
    for(i = 0; i <= n-1; i++){    //每次循环数组，找出最小的元素，放在前面
        mix = i;
        for(j = i+1; j <= n-1; j++) {    //找出未排序部分最小元素的下标
            if(a[j] < a[mix]) {
                mix = j;
            }
        }
        if(i != mix) {
            temp = a[i];
            a[i] = a[mix];
            a[mix] = temp;
        }
    }
}

int main() {
    int a[50], n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {    //依次输入未排序的数组元素
        scanf("%d", &a[i]);
    }
    SimpleSelectSort(a, n);
    for(int i = 0; i < n; i++) {
	    printf("%d ", a[i]);
    }
    return 0;
}

三、插入排序

1、直接插入排序

直接插入排序是众多插入排序方法中最直观的一种，直接插入排序是指，对于数组 a[n]，令 i 从 1 到 n-1 枚举，进行 n-1 趟操作，如果数组 a 的前 i-1 个元素 [0，i-1] 已经有序，而范围 [i，n-1] 还未有序，那么该趟从范围 [0，i-1] 中寻找某个位置 j，使得将 a[i] 插入位置 j 后范围 [0，i] 有序。

具体代码实现如下：

#include<stdio.h>

void StraightInsertSort(int a[], int n) {
    for(int i = 1; i < n; i++) {    //从第二个元素开始枚举，与前面有序部分进行比较
        int j = i-1;
        int temp = a[i];
        while(j >= 0 && temp < a[j]) {    //当temp比其左边的数的值小时，从后向前枚举有序部分来确定插入位置
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

int main() {
    int a[50], n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {    //依次输入未排序的数组元素
        scanf("%d", &a[i]);
    }
    StraightInsertSort(a, n);
    for(int i = 0; i < n; i++) {
	    printf("%d ", a[i]);
    }
    return 0;
}

四、sort 排序

顾名思义，sort 函数就是用来排序的函数，它根据具体情况使用不同的排序方法，而且 sort 函数在实现的过程中规避了经典快速排序中可能会出现的会导致实际复杂度退化到 O($n^2$) 的极端情况，所以其效率比较高。

1、如何使用 sort 排序

sort 函数的使用必须加上头文件 “#include\” 和 “using namespace std;”，其使用方式如下：

1	sort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数cmp（非必填）);

对一个 int 型数组 a[4] = {3, 4, 9, 5} 进行排序：

1	sort(a, a + 4); //int型数组（double型也一样）默认从小到大进行排序，输出结果为3,4,5,9

对一个 char 型数组 a[5] = {‘T’, ‘W’, ‘A’, ‘K’, ‘B’} 进行排序：

1	sort(a, a + 5); //char型数组默认按字典序从小到大进行排序，输出结果为A，B，K，T，W

2、如何实现比较函数 cmp

（1）基本数据类型数组的排序

对一个 int 型数组 a[4] = {3, 4, 9, 5} 进行排序：

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a, int b) {
    return a > b;      //从大到小排序，double型和char型同理
    //return a < b;    //从小到大排序，double型和char型同理
}
int main() {
    int a[] = {3, 4, 9, 5};
    sort(a, a + 4, cmp);
    for(int i = 0; i < 4; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

（2）结构体数组的排序

现定义了如下的结构体：

struct node {
    int x;
    char y[10];
}ssd[10];

如果想先按 x 从大到小排序，但当 x 相等的情况下，按照 y 的大小从小到大来排序，则 cmp 函数的写法为：

bool cmp(node a, node b) {
    if(a.x != a.y) return a.x > b.x;            //x不等时按x从大到小排序
    else return strcmp(a.y, b.y) < 0;           //x相等时按y从小到大排序
}