经典的排序算法

一、排序算法简介

1.1 排序概念

​ 排序：将一堆数据按照某一种特定的方式进行特定方式排列(比如从大到小排列)的算法。

​ 记录：我们待排序集合里的数据元素

​ 关键字：我们通过比较记录里面的关键字来进行排序

​ 排序的输入是一个记录集合，排序后的输出也是一个记录集合。

​ 多个关键字的排序可以转换为单个关键字的组合。

1.2 排序的稳定性

​ 由于待排序的记录序列中可能存在两个或者两个以上数据相等的记录，所以排序的结果可能不唯一，若在排序之前A1在A2的前面，排完序后A1仍然在A2的前面，那么该排序算法是稳定的，否则是不稳定的(A1、A2为记录集合中的两个相等元素)

​

1.3 内排序和外排序

1.3 .1 内排序

​ 内排序：待排序的所有记录都被存放在内存中

​ 排序算法的性能影响：

• 时间性能：排序主要进行比较和移动。所以高效率的排序要尽量减少比较和移动
• 辅助空间：也就是除了存放我们需要待排序的数据之外其它的辅助存储空间
• 算法的复杂性：算法本身过于复杂会影响到排序的性能

内排序分为：插入排序、交换排序、选择排序、归并排序

1.3.2 外排序

​ 外排序：在排序的过程中存在内外存之间的多次数据交换，也就是说有数据保存在外存中

​ Tips：外存也就是我们常说滴硬盘,包括机械硬盘和固态硬盘SSD

​

1.4 排序用到的结构和函数

排序的顺序表定义：

//排序的个数的最大值
#define MAXSIZE 10 
typedef struct
{
    //存储要排序的数组，data[0]可用作临时变量或者哨兵
    int data[MAXSIZE+1];
    //记录顺序表的长度 
    int length;
}SqList;
1
2
3
4
5
6
7
8
9

交换元素的函数定义：

void swap(SqList *L, int i, int j)
{
    int temp = L->data[i];
    L->data[i] = L->data[j];
    L->data[j] = temp;
}
1
2
3
4
5
6

二、冒泡排序

2.1 基本思路

​ 冒泡排序(Bubble sort)是一种交换排序，其基本思路是：两两比较相邻的记录的关键字，如果出现反序则交换，直到没有反序为止。

2.2 代码实现

/**
 * @brief 冒泡排序算法
 * @param L 待排序的记录集合 
 * 时间复杂度：O(n^2)
 * 空间复杂度:O(n)
 */
void bubbleSort(SqList *L)
{
    int i,j;
    //标记是否发生交换数据，若查看一次发现没有需要比较的数据则结束排序，防止排序好的数继续比较
    BOOL flag = TRUE;
    //i代表的是总共需要比较的趟数:一趟内我们只需要比较未排序的即可,即L->length-2趟
    for(i = 1; i < L->length && flag; i++)
    {
        flag = FALSE;
        //j代表冒泡排序一趟比较的的次数：比如有N个数，那么我们只需要比较L->length-i-1次即可
        for(j = L->length - 1; j >= i; j--)
        {
            if(L->data[j] < L->data[j-1])
            {
                swap(L , j, j-1);
                flag = TRUE;
            }
        }
    }
}
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
26

三、简单选择排序

3.1 基本思路

​ 冒泡排序需要不断地进行交换，导致时间复杂度增加了，我们可以找到合适的时机进行关键字的交换，并且只移动一次就完成相应关键字的定位。拿买股票来举例：冒泡排序就像狂热的交易者，不断地进行交易来达到自己的目的。而选择排序就像头脑冷静的智者在关键时刻进行交易，轻松达到自己的目的。

​ 简单选择排序就是通过n-i次关键字间的比较从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。

3.2 代码实现

/**
 * @brief 简单选择排序
 * 
 * @param argc 
 * @param argv 
 * @return int 
 * 分析：交换移动数据的次数减少了，但是其比较的次数确没有减少，即第i趟排序
 * 需要进行n-i次关键字比较，所以总共需要进行n(n-1)/2次比较.但是其性能要优于冒泡排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 */
void simpleSelectSort(SqList *L)
{
    //min为最小值的下标
    int i,j,min;
    for(i = 0; i < L->length - 1; i++)
    {
        min = i;
        for(j = i + 1; j < L->length; j++)
        {
            if(L->data[min] > L->data[j])
            {
                min = j;
            }
        }
        //若i和min不相等则说明找到了最小值，将最小值下标的元素与以i为下标的元素交换
        if(i != min)
        {
            swap(L, i, min);
        }
    }
}
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
26
27
28
29
30
31
32

四、直接插入排序

4.1 基本思路

​ 扑克牌的插入就是直接插入排序算法的最好体现，也就是我们拿到一张牌会将其插入到已经排好序的集合中去。

​ 其基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表

4.2 代码实现

/**
 * @brief 直接插入排序
 * 
 * @param L 
 * 时间复杂度分析：O(n^2)
 * 空间复杂度分析：O(n+1)
 * 空间上就是多了一个辅助空间用来保存临时变量，其算法性能要比冒泡排序和简单选择排序要好
 */
void directInsertionSort(SqList *L)
{
    int temp;
    int i,j;
    for(i = 1; i < L->length; i++)
    {
        temp = L->data[i];
        for(j = i - 1; j >= 0 && temp < L->data[j]; j--)
        {
            L->data[j+1] = L->data[j];
        }
        L->data[j+1] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22