排序

将无序的序列，按照某个规则进行排序，如果一个数据含有多个数据域，则针对其中一个数据域进行排序

排序方法分类

按照存储介质
- 内部排序：数据量不大，在内存中可以完成的排序
- 外部排序：数据量比较大，需要在硬盘上进行操作
按照比较器个数
- 串行排序：同一时刻比较一对元素
- 并行排序：同一时刻比较多对元素
按照主要操作
- 比较排序：用来比较的方法
- 基数排序：不需要比较大小
按照辅助空间
- 原地排序：辅助空间为O(1)，只在原始数据基础上进行操作，不需要额外空间
- 非原地排序：辅助空间超过O(1)
按照稳定性
- 稳定排序：如果有元素相等的元素，排序后相对位置不变，称为稳定排序
- 非稳定排序：如果有元素相等的元素，排序后相对位置改变了，称为不稳定排序
  
  排序的稳定性只针对结构类型的数据是有意义的，不用来衡量排序算法的优劣
按照自然性
- 自然排序：输入的数据越有序，排序速度越快
- 非自然排序：不是自然排序的排序

插入排序

基本思想：每一次将一个待排序的对象，按照值的大小，插入到前边已经排好序的合适的位置上，直到所有对象插入为止

是在有序序列中插入，保持序列有序，插入过程中，序列的长度一直是有序的

插入方法

首先将前i个元素看作是一个有序的序列，假设是按照升序（从小到大）排序
取第a[i+1]的值，为其从0到i找一个合适的位置，合适位置找到后，按照以下策略插入
- 如果该元素比任何元素都大，直接放到已经排好序的序列之后，即下标为i的位置
- 如果比任何元素都小，则整体后移，将其放在第一个位置，即下标为0的位置
- 如果该元素是在中间，则将比它大的后移，为其腾出一个位置
i自增1
重复第二三步，直到所有元素都被插入

种类

按照找插入位置的方法不同，可以将其分为

直接插入排序

顺序法找插入位置
二分插入排序

二分法找插入位置
希尔排序

缩小增量，多遍插入排序

直接插入排序

使用顺序查找法

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-04 08:51:42
 */
#include <stdio.h>
#include <stdlib.h>
#define maxLength 11
void sort(int *a)
{
    for (int i = 1; i < 15; i++)
    {
        int temp = a[i]; //临时变量存储值
        int pos = -1;    //存储比它大的第一个数的下标，此时这个位置就是存储着需要插入的值
        for (int j = 0; j <= i; j++)
        {
            if (a[j] >= temp) //找第一个比它大的值，还有一种情况，没有数比它大，所以取等号
            {
                pos = j;
                break;
            }
        }
        for (int j = i; j > pos; j--)
        {
            a[j] = a[j - 1]; //后移
        }
        a[pos] = temp; //赋值
    }
}
int main()
{
    int a[15] = {0, 11, 2, 3, 4, -445, -6444, 6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(a);
    for (int i = 0; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

更巧妙的方法

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-04 09:09:11
 */
#include <stdio.h>
#include <stdlib.h>
#define maxLength 11
void sort(int *a)
{
    for (int i = 1; i < 15; i++)
    {
        int temp = a[i]; //临时变量存储值
        int j = i - 1; //从已经排好的位置进行查找
        for (; j >= 0 && a[j] > temp; j--)
        {
            a[j + 1] = a[j]; //后移，将j+1的位置空出来
        }
        a[j + 1] = temp; //因为可能出现这个元素比第一个小的情况，所以要放在循环体外，此时的j = -1，还有就是第j + 1的位置被空了出来
    }
}
int main()
{
    int a[15] = {0, 11, 2, 3, 4 , 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(a);
    for (int i = 0; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

时间复杂度O(n*n)

折半插入排序（二分插入排序）

基于二分查找

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-06 16:44:47
 */
#include <stdio.h>
#include <stdlib.h>
#define maxLength 11
void sort(int *a)
{
    for (int i = 1; i < 15; i++)
    {
        int low = 0, height = i - 1;
        int mid;
        int temp = a[i];
        while (low <= height)//二分查找
        {
            mid = (low + height) / 2;
            if (a[i] > a[mid])
                low = mid + 1;
            else
                height = mid - 1;
        }
        // 最后的值将存放在height+1的位置，将height+1后的元素后移
        for (int j = i; j > height + 1; j--)
        {
            a[j] = a[j - 1];
        }
        a[height + 1] = temp;
    }
}
int main()
{
    int a[15] = {0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(a);
    for (int i = 0; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

速度比顺序查找快
最好情况要比顺序差
没有减少移动次数

希尔排序

直接插入排序在序列有序的时候，插入效率最高，待排序数量个数少时效率也最高

#####思想

将待排序的序列分成若干个子序列，分别进行直接插入排序，等到整个序列基本有序之后，再进行整体的直接插入排序

思路

选择一个增量序列，用来控制间隔
根据增量序列的间隔，进行一次间隔插入排序

特点

缩小了增量，多遍的插入排序，因为直接插入排序在元素数量少时，效率最高

移动的位置比较大
最后一次仅需要少量移动
序列必须是递减的，最后一个元素必须是1
增量序列应该都互为质数

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 22:06:26
 */
#include <stdio.h>
#include <stdlib.h>
#define maxLength 15
void shellSort(int *a, int num)
{
    for (int i = num; i < maxLength; i++) //普通的插入排序，间隔为num
    {
        int key = a[i];
        int j = i - num;
        for (; j >= 0 && a[j] > key; j -= num)
            a[j + num] = a[j];
        a[j + num] = key;
    }
}
void sort(int *a, int *list, int listNum)
{
    for (int i = 0; i < listNum; i++) //按照增量进行希尔排序
    {
        shellSort(a, list[i]); //增量序列时list[i]
    }
}

int main()
{
    int a[15] = {0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    int list[3] = {5, 3, 1}; //初始化一个增量序列
    sort(a, list, 3);
    for (int i = 0; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

希尔排序是一种不稳定算法

空间复杂度为O(1)

交换排序

思想：两两比较，如果第一个比第二个大(小)，将两者进行交换，直到所有的所有的都排好序

冒泡排序

不断地进行比较，按照规则进行交换

/*
 * @Created by : SongXiaoxu
 * @Copyright ? 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 21:59:12
 */
#include <stdio.h>
#include <stdlib.h>

#define maxLength 15


void sort(int *a, int *list, int listNum)
{
    for (int i = 0; i < maxLength - 1; i++) 
    {
        for (int j = 1; j < maxLength - i; j++)
        {
            if (a[j] < a[j - 1])
            {
                int t = a[j];
                a[j] = a[j - 1];
                a[j - 1] = t;
            }
        }
    }
}

int main()
{
    int a[15] = {0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    int list[3] = {5, 3, 1}; //初始化一个增量序列
    sort(a, list, 3);
    for (int i = 0; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

需要重复数组的最大长度-1次
时间复杂度为O(N*N)

每次排好一个元素，排好的元素会放在末尾

0 2 3 4 11 -6444 -6545117 86 9 10 11 12 13 14 445
0 2 3 4 -6444 -6545117 11 9 10 11 12 13 14 86 445
0 2 3 -6444 -6545117 4 9 10 11 11 12 13 14 86 445
0 2 -6444 -6545117 3 4 9 10 11 11 12 13 14 86 445
0 -6444 -6545117 2 3 4 9 10 11 11 12 13 14 86 445
-6444 -6545117 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445
-6545117 -6444 0 2 3 4 9 10 11 11 12 13 14 86 445

设数组长度为n，外层循环需要n-1次，内层循环每次递减，即n，n-1，n-2....直到剩下1次
也可以提高效率，当不再出现交换时，跳出整个循环，即此时排好序了
是一种稳定的算法

快速排序

是一种改进的交换排序

基本思想（升序）

任取一个元素为中心
依次查看其他的元素，如果比它小，放在它的前边，如果比它大，放在它的后边，最后空出的位置为它的位置，空出的位置也是拍好序的位置
- 此时形成两个子表，再对两个子表使用此规则进行划分
- 直到每个子表只剩下一个元素

####过程
|空余位置（哨兵）0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|:-----:| :----: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| | 49 | 38 | 65 | 97 | 76 | 13 | 27 |49|

先把中心元素移动到空余位置，这里选择第一个元素
设立low指针（指向第一个位置）和height指针（指向最后一个位置）
- 如果此时的low指向的空位置，那么在height指针进行操作
  - 如果height指针处的值比中心元素小，那么将其移动到空余位置，此时height指向空位置
  - 如果比中心元素小，height的值-1，即指针前移
- 如果此时height指向空位置，那么在low指针进行操作
  - 如果low指针处的值比中心元素大或者等于中心元素，那么将其移动到空余位置，此时low指向空位置
  - 如果比中心元素小，low的值+1，即指针后移

此时1的位置空了

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49		38	65	97	76	13	27	49
	low							height

49不比中心元素小，无需移动，将height指针前移

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49		38	65	97	76	13	27	49
	low						height

27比不中心元素小，无需移动，将27指针移动到low(空白位置)，此时height变为了空白位置

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49	27	38	65	97	76	13		49
	low						height

此时要操作low指针，很显然38不比中心元素大，low后移，65比中心元素大，将其移动到空白位置，此时的low指向了空白位置

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49	27	38		97	76	13	65	49
			low				height

此时要操作height指针，将13移动到空白位置，此时的height指向了空白位置

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49	27	38	13	97	76		65	49
			low			height

继续操作，可见，此时的height和low指针指向了同一个位置

空余位置（哨兵）0	1	2	3	4	5	6	7	8
49	27	38	13		76	97	65	49
				low height

接下来将哨兵位置的元素放在两者的重合位置，此时第一次划分结束

空余位置（哨兵）0	1	2	3	4	5	6	7	8
	27	38	13	49	76	97	65	49
				low height

此时中心点的位置是在low和height的重合处

空余位置（哨兵）0	1	2	3	4	5	6	7	8
	27	38	13	49	76	97	65	49
	第一个子表开始		第一个子表结束	low height	第二个子表开始			第二个子表结束

继续划分个子表，直到每个子表只有一个元素

空余位置（哨兵）0	1	2	3	4	5	6	7	8
	13	27	38	49	49	65	76	97

代码

/*
 * @Created by : SongXiaoxu
 * @Copyright ? 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 21:59:12
 */
#include <stdio.h>
#include <stdlib.h>

#define maxLength 16

int getPosition(int low, int height, int *a)//返回中间的元素位置
{
    int isEmpty = 0; //0代表左边有空余位置，1代表右边有空余位置
    a[0] = a[low];
    while (low != height)
    {
        if (isEmpty == 0) //左边有空余位置
        {
            while (a[height] >= a[0] && low != height) //因为右边的元素要比中间的大，所以此时height指针要不断前移
                height--;
            if (low != height) //代表此时没有移动到相同的位置了
            {
                a[low] = a[height]; //将找到的的放到空余位置
                isEmpty = 1; //此时代表右边右空余位置
            } else
                break;
        } else //右边有空余位置
        {
            while (a[low] < a[0] && low != height) //因为左边的元素要比中间的小，所以此时height指针要不断前移
                low++;
            if (low != height)
            {
                a[height] = a[low];
                isEmpty = 0; //此时代表左边右空余位置
            } else
                break;
        }
    }
    a[low] = a[0];
    return low;
}

void sort(int low, int height, int *a)
{
    if (low > height)
        return;
    int mid = getPosition(low, height, a);
    sort(low, mid - 1, a); //递归对左右两个子表进行排序
    sort(mid + 1, height, a);
}

int main()
{
    int a[16] = {0, 0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(1, 15, a);
    for (int i = 1; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

精简代码后的

/*
 * @Created by : SongXiaoxu
 * @Copyright ? 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 21:59:12
 */
#include <stdio.h>
#include <stdlib.h>

#define maxLength 16

int getPosition(int low, int height, int *a)//返回中间的元素位置
{
    a[0] = a[low];
    while (low != height)
    {
        while (a[height] >= a[0] && low != height) //因为右边的元素要比中间的大，所以此时height指针要不断前移
            height--;
        a[low] = a[height]; //将找到的放到空余位置
        while (a[low] < a[0] && low != height) //因为左边的元素要比中间的小，所以此时height指针要不断前移
            low++;
        a[height] = a[low];
        //极端情况，此时的low == height，假设开始low处是空的，low为空，height处的放到low中，此时的height为空，又将low处的值放在了height处
        //如果height处是空的，那么完美结束
        //如果一直不断的前移，在第一个while处使得low等于了height，a[low] = a[height]仍会执行，但是这次的执行是没有意义的，循环体外会将a[0]处的值再次放到a[0]处
    }
    a[low] = a[0];
    return low;
}

void sort(int low, int height, int *a)
{
    if (low > height)
        return;
    int mid = getPosition(low, height, a);
    sort(low, mid - 1, a);
    sort(mid + 1, height, a);
}

int main()
{
    int a[16] = {0, 0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(1, 15, a);
    for (int i = 1; i < 15; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

时间复杂度

递归算法的时间复杂度为O(N)
查找中心元素位置的时间复杂度为$$O(log_2N)$$
总体时间复杂度为$$O(Nlog_2N)$$
最坏时间复杂度为*$$O(N^2)$$*
如果序列为有序序列，快速排序就退化成了冒泡排序，因此不适用于有序序列或基本有序序列

空间复杂度

平均的空间复杂度为O(logN)
最坏为O(N)

因为使用了递归，函数调用堆栈也是需要占用空间的，取决于递归的深度，是一种不稳定的排序方法

选择排序

分为简单选择排序、堆排序

简单选择排序

思想：在待排序的数据中选出最大（小）的元素放到最终位置

假设按照从小到大进行排序

首先选定第一个元素，从第一个元素开始，与其后每个元素对比
- 如果比该元素小，记录下标，继续使用该处的值进行对比
- 如果比该元素大，继续往后遍历
继续进行，从第二个元素开始，重复对比步骤，总共需要n-1次对比

/*
 * @Created by : SongXiaoxu
 * @Copyright ? 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 21:59:12
 */
#include <stdio.h>
#include <stdlib.h>

#define maxLength 16


void sort(int *a)
{
    for (int i = 0; i < maxLength; i++)
    {
        int minPos = i;
        for (int j = i + 1; j < maxLength; j++)
        {
            if (a[minPos] > a[j])
                minPos = j;
        }
        //以下步骤始终执行，无论该处的值是否是最小值都会执行，如果该处的值是最小值，那么相当于自身与自身交换
        int t = a[i];
        a[i] = a[minPos];
        a[minPos] = t;
    }

}

int main()
{
    int a[16] = {0, 0, 11, 2, 3, 4, 445, -6444, -6545117, 86, 9, 10, 11, 12, 13, 14};
    sort(a);
    for (int i = 0; i < 16; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

时间复杂度：$$O(N^2)$$

不是稳定的算法，但也可以进行稳定

堆排序

堆的定义

小根堆：
- ai <= a2i
- ai <= a2i+1
大根堆：
- ai >= a2i
- ai >= a2i+1

堆的实质是完全二叉树，因此小根堆的根节点要比左右(所有)孩子小，大根堆的根节点要大于左右(所有)孩子

排序过程

堆顶要么是最大值，要么是最小值，每次取堆顶的元素
将剩下的元素重新建立一个堆，再去堆顶元素，重复该过程

堆的调整

去掉堆顶元素后，用堆中的最后一个元素代替堆顶元素，最好是交换两者
将堆顶元素与其左右子树进行对比，用小（大）的元素替代堆顶元素
递归的对替换后的元素重复这个过程，直到叶子结点，如果没有替换成功，无需进行相关操作

堆的建立

单个结点是堆
叶子结点不需要调整，只需要调整双亲结点
首先从最后一个双亲结点调整，即数组的元素个数/2

/*
 * @Created by : SongXiaoxu
 * @Copyright ? 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-07 21:59:12
 */
#include <stdio.h>
#include <stdlib.h>

#define maxLength 16

void heap(int pos, int *a, int cnt) //如果根节点比左右结点大，那么用左右结点的最小值替换根节点，同时递归的对替换后的根节点再次进行操作
{
    int minPos;
    if (2 * pos < cnt) //如果左孩子的下标没有要比最后一个元素的下标小就代表有左右孩子
    {
        minPos = a[2 * pos] < a[2 * pos + 1] ? 2 * pos : 2 * pos + 1;
    } else if (2 * pos == cnt) //如果左孩子的值和最后一个元素的值相等，代表此时只有左孩子
        minPos = 2 * pos;
    else //代表没有孩子结点
        return;
    if (a[pos] > a[minPos]) //这个条件在这里必须要加，只有在交换值之后才可以进行递归操作
    {
        int t = a[pos];
        a[pos] = a[minPos];
        a[minPos] = t;
        heap(minPos, a, cnt);
    }

}

int main()
{
    int a[maxLength + 1] = {0, 32, 43, 233, 444, -555, -666, 5432, 14, 23, 4, 14, 1, 34, 3341, 24, 1};
    for (int i = (maxLength + 1) / 2; i >= 1; i--)
    {
        heap(i, a, maxLength);
    }
    int cnt = maxLength;
    for (int i = 0; i < 16; i++)
    {
        printf("%d ", a[1]); //每次取堆顶元素
        int t = a[1];
        a[1] = a[cnt--]; //用最后一个元素替换堆顶元素
        a[cnt + 1] = t;
        heap(1, a, cnt); //递归的进行堆的调整
    }
    puts("\n");
    for (int i = 1; i <= maxLength; i++)
        printf("%d ", a[i]);
    return 0;
}

时间复杂度为：O(NlogN)，无论初始数据的顺序，复杂度都不变
空间复杂度为：O(1)
是一种不稳定的算法

归并排序

将两个或者两个以上的序列归并为一个

48	34	60	80
34 48	60 80	12 75	26 48
34 48 60 80	12 26 48 75
12 26 34 48 48 60 75

对以上序列进行升序的排序过程

时间复杂度为：$$O(Nlog_2N)$$
空间复杂度为：O(N)
是一个稳定的排序算法

基数排序

基本思想：分配+收集

又被称为桶排序或者箱排序

一般准备10个箱子（因为数字是从0-9），也可以根据序列数字的特征准备

从个位开始，把他们扔到箱子里，再从0-9收集，再分别从十位、百位进行分配，直到最后收集完毕，每次收集就代表序列按照这个位数有序，例如按照个位进行收集，则此时收集起来就是个位有序的了

这是此时的数据

614	738	921	485	637	101	215	530	790	306

分配个位

0	1	2	3	4	5	6	7	8	9
530 790	921 101			614	485 215	306	637	738

收集

530	790	921	101	614	485	215	306	637	738

按照十位分配

0	1	2	3	4	5	6	7	8	9
101 306	614 215	921	530 637 738					485	790

收集

101	306	614	215	921	530	637	738	485	790

按照百位分配

0	1	2	3	4	5	6	7	8	9
	101	215	306	485	530	614 637	738 790		921

收集

101	215	306	485	530	614	637	738	790	921

此时数据是有序的了

时间复杂度为：O(K*N+M)，其中K为关键字的个数，即一堆数字的最大位数，M为关键字的取值（0-9）
是一个稳定的算法

总结

Q.E.D.

Moyok的博客

排序

排序