MH's Blog
0%

排序

发表于 更新于 分类于

基本概念

将个元素按关键字的递增或递减排列

评价指标

  1. 时间复杂度
  2. 空间复杂度
  3. 稳定性: 假设$K_i=K_j\quad (i \lt j)$排序完成后$K_i$的位子仍在$K_j$之前称该排序算法是稳定的，否则不稳定

排序两大类

  1. 内部排序：数据全在RAM里
  2. 外部排序：数据太多不能一次性导入RAM，需要对外存进行访问

内部排序方法

插入排序

直接插入排序

将一个key插入到已经排序好的有序表中 。
适用于顺序表，也适用于链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(int array[], int len)
{
    //得到递增序列
    for(int i = 2; i <= len; ++i)
    {
        array[0] = array[i];
        int j = i -1;
        for(; array[0] < array[j]; --j)
        {
            array[j+1] = array[j];
        }
        array[j+1] = array[0];
    }
}

时间复杂度分析:
最好：序列是有序且为递增序列，则第二层for循环一次都不执行，$O(n)=n$
最坏:序列是有序且为递减序列，$O(n)=n^2$
平均:因为序列的各种排列出现的概率相同,平均复杂度大约为最好和最坏之和除2,$O(n)=n^2$
空间复杂度：$O(1)$
稳定性分析：稳定的 。关键在于array[0] < array[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
26
27
int InsertBinSort(int array[], int len)
{
    //得到递增序列
    for (int i = 2; i <= len; ++i)
    {
        array[0] = array[i];
        int high = i - 1, low = 1;
        while (low <= high)
        {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > array[0])
            {
                //high最后永远指向小于等于array[0]的最后一个元素
                high = mid - 1; //保证递增序列的稳定性，相等的元素后判断的要插入后半区
            }
            else
            {
                low = mid + 1;
            }
        }
        for (int j = i - 1; j > high; --j)
        {
            array[j + 1] = array[j];
        }
        array[high + 1] = array[0];
    }
}

只是优化了找位置，移动元素仍有$O(n^2)的量级$

希尔排序

是对直接插入排序的一种优化
主要思想是先先使得序列部分有序后慢慢直接有序
比如1537比5317用直接排序会快很多
设置一个增量d，将序列分割成一个个子表$[i，i+d，i+2d，\cdots,]$，对各各子表采用直接插入，逐步缩小d，直至d为1。
如42618735，先设置d为len/2=4，那么就有4个子表[4,8],[2,7],[6,3],[1,5],先把这几个子表分别进行直接插入[4,8],[2,7],[3,6],[1,5],序列变为42318765,减小d,d=d/2,等到2个子表，继续进行，继续减小d为1,最后一次直接插入。

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
void ShellSort(int array[], int len, int dlta[], int dLen)
{
    //dlta 0～dLen-1  array 1~len
    for (int k = 0; k < dLen; ++k)
    {
        ShellInsert(array, len, dlta[k]);
    }
}

void ShellInsert(int array[], int len, int d)
{
    //不对子表单独处理，而是一起处理
    for (int i = d + 1; i <= len; ++i)
    {
        if (array[i] < array[i - d])
        {
            array[0] = array[i - d];
            int j = i - d;
            for (; j > 0 && array[j] < array[0]; j -= d) //这个大于0很重要，因为[0]已经不是哨兵了
            {
                array[j + d] = array[j];
            }
            array[j + d] = array[0];
        }
    }
}

时间复杂度:无法用数学手段明确给出，与增量序列d的选取有关，d选取应该时增量序列的值中没有除了1之外的公因子，且最后一个增量必须等于1
图片 2021-03-31 21-40-26

基于交换的排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void BubbleSort(int array[], int len)
{
    for (int i = 1; i < len; ++i)
    {
        for (int j = 1; j < len - i + 1; ++j)
        {
            if (array[j] > array[j + 1])
            {
                Swap(&array[j], &array[j + 1]);
            }
        }
    }
}

时间复杂度：$O(n)=n^2$
稳定性：稳定

快速排序

分治思想

对待排序序列，选出一个枢轴pivot，把所有比pivot小的元素放在它的左边，所有比他大的放在右边(等于的会被<或>自动归类的)。分出左右两个区间，在对左右区间作相同的操作，直至区间不可分。(递归实现)

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
void QuickSort(int *array, int low, int high)
{
    int Partiton(int *array, int low, int high);
    if (low < high)
    {
        int mid = Partiton(array, low, high);
        QuickSort(array, low, mid - 1);
        QuickSort(array, mid + 1, high);
    }
}

int Partiton(int *array, int low, int high)
{
    int privot = array[low];
    while (low < high)
    {
        while (low < high && array[high] > privot)
        {
            --high;
        }
        //Swap(&array[high],&array[low]);
        array[low] = array[high]; //不用交换是因为第一次交换时low就是privot的位置这个位子本来就能被代替，没代替一次就产生一个废位子
        while (low < high && array[low] < privot)
        {
            ++low;
        }
        //Swap(&array[high],&array[low]);
        array[high] = array[low];
    }
    array[low] = privot; //没有使用交换记得最后把privot移回去
    return low;
}

时间复杂度分析：
每一次处理Partiton最多要处理n次，那么就要分析递归次数就好了
O(n)=O(n*递归层数)
快速排列把一个序列分层2个区间，并依次划分出去，就像一颗二叉树，一个有n个结点的二叉数，树高$log_2(n+1)\le h\le n$
所以最快为$O(nlog_2n)$
最慢为$O(n^2 )$

选择排序

简单选择排序

每次选取最小的元素放到前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelcetSort(int array[], int len)
{
    for (int i = 1; i < len; ++i)
    {
        int min = i;
        for (int j = i + 1; j <= len; ++j)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
        if (min != i)
        {
            Swap(array + i, array + min);
        }
    }
}

堆排序

大根堆定义： $ai \ge a{2i}\quad and\quad ai \ge a{2i+1}$
小根堆

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
void HeapSort(int array[], int len)
{
    void HeadAdjust(int array[], int len, int k);
    for (int i = len / 2; i > 0; --i)
    {
        HeadAdjust(array, len, i);
    }
    for (int i = 1; i < len; ++i)
    {
        Swap(array, array + len - i + 1);
        HeadAdjust(array, len - i, 1);
    }
}

void HeadAdjust(int array[], int len, int k)
{
    int son = 2 * k;
    while (son <= len)
    {
        if (son + 1 <= len && array[son] < array[son + 1])
            ++son;
        if (array[son] < array[k])
            return;
        Swap(array + son, array + k);
        k = son;
        son = 2 * k;
    }
}

归并排序