数据结构之七大排序

我不是女神ヾ 2022-03-21 03:46 169阅读 0赞

假设含有n个记录的序列为![\\left \\\{ r\_\{1\} ,r\_\{2\},......,r\_\{n\}\\right \\\}][left _ r_1_ _r_2_......_r_n_right]，其相应的关键字分别为![\\left \\\{ k\_\{1\},k\_\{2\},......,k\_\{n\} \\right \\\}][left _ k_1_k_2_......_k_n_ _right]，需确定1,2,......,n的一种排列![p\_\{1\},p\_\{2\},......,p\_\{n\}][p_1_p_2_......_p_n]，使其相应的关键字满足![k\_\{p\_\{1\}\}\\leq k\_\{p\_\{2\}\}\\leq ......\\leq k\_\{p\_\{n\}\}][k_p_1_leq k_p_2_leq ......_leq k_p_n]（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列![\\left \\\{ r\_\{p\_\{1\}\}, r\_\{p\_\{2\}\}, ......, r\_\{p\_\{n\}\} \\right \\\}][left _ r_p_1_ r_p_2_ ......_ r_p_n_ _right]，这样的操作就称为排序。

假设![k\_\{i\}= k\_\{j\}\\left ( 1\\leq i\\leq n,1\\leq j\\leq n,i\\neq j \\right )][k_i_ k_j_left _ 1_leq i_leq n_1_leq j_leq n_i_neq j _right]，且在排序前的序列中![r\_\{i\}][r_i]领先于![r\_j][r_j](即i<j)。如果排序后![r\_\{i\}][r_i]仍然领先于![r\_j][r_j]，则称所用的排序方法是稳定的；反之，若排序后的![r\_j][r_j]领先于![r\_\{i\}][r_i]，则称所用的排序方法是不稳定的。

如果在排序过程中，待排序的所有记录全部被放置在内存中，即称这种排序为内排序。常见的内排序有插入排序、交换排序、选择排序和归并排序。外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内存和外存之间多次交换数据才能进行。

排序算法有很多种，这里仅选择几种常用的或常见的排序方式来说明。为了方便使用，我们使用顺序表来存储待排序记录，当然，也可以用数组来存储。无论是用顺序表还是数组存储，其排序思想不会发生改变，所以依个人喜好决定。又因为排序算法中经常用到的操作是交换，所以我们单独写个交换函数，在排序算法中需要的地方直接调用就行。还有，我们再写一个打印函数Show()来显示排序结果。由于排序算法的不同，有些不是从下标为0的地方开始排序的，所以我们需要给Show()函数传两个参数来满足不同的输出需要。具体代码如下：

#include<stdio.h>
    #define MAXSIZE 20		//假设顺序表最大容量为20
    typedef int ElemType;		//数据类型假设为int
    typedef struct
    {
        ElemType data[MAXSIZE];	//存储待排序记录的数组data
        int length;			//待排序记录的个数
    }SqList;
    //交换函数
    void Swap(SqList* s, int i, int j)
    {
        ElemType temp = s->data[i];
        s->data[i] = s->data[j];
        s->data[j] = temp;
    }
    //如果Show()只传入一个参数，则默认begin=0，否则，以begin为准
    void Show(const SqList* s,int begin=0)
    {
        for (int i = begin; i < s->length+begin; i++)
        {
    	printf("%d ", s->data[i]);
        }
        printf("\n");
    }

一、冒泡排序

关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字。当数据元素中只有一个数据项时，其关键字即为该数据元素的值。数据元素即记录。

首先将第一个记录的关键字和第二个记录的关键字进行比较，若第二个关键字比第一个关键字小，则将两记录交换，然后比较第二个记录和第三个记录的关键字，依次类推，直到n-1个记录和第n个记录的关键字比较完为止。。此为第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使关键字第二大的记录被安置到第n-1个记录的位置上。依次类推，最后将关键字最小的记录被安置到第1个记录的位置上。

void Bubble_Sort(SqList* s)
    {
        for (int i = 0; i < s->length - 1; i++)
        {
    	for (int j = 0; j < s->length - i - 1; j++)
    	{
    	    if (s->data[j]>s->data[j + 1])
    	    {
    	        Swap(s, j, j + 1);
    	    }
    	}
            Show(s);
        }
    }

此算法是将较大的值往后放置，其每一趟比较结果为：

![20190130160431726.png][]

还有一种正宗的冒泡排序，即让j从后往前循环，逐个比较，将较小值交换到最前面，直到最后找到最小值放在第1个记录的位置上。此方法中，较小的数字如同气泡般慢慢浮到最上面，所以称其是正宗的冒泡算法，这也是“冒泡”的由来。

void Bubble_Sort(SqList* s)
    {
        //i从前往后循环
        for (int i = 0; i < s->length - 1; i++)
        {
    	//j从后往前循环
    	for (int j = s->length - 1; j > i; j--)
    	{
    	    if (s->data[j - 1] > s->data[j])
    	    {
    		Swap(s, j - 1, j);
    	    }
    	}
    	Show(s);
        }
    }

此算法是将较小的值往前放置，其每趟比较结果为：

![2019013016065117.png][]

还有一种优化了的冒泡算法。观察第二种冒泡算法，发现有多余的不必要的比较，即完全可以在第6趟冒泡比较之后得到最终排序结果，可是仍然比较了9趟，这就有点浪费时间。于是，改进的算法很好的避免了这种不必要的比较。方法是在原有的算法之中增加一个变量来标记。

void Bubble_Sort(SqList* s)
    {
        int flag = 1;
        //i从前往后循环,flag=1时进入循环
        for (int i = 0; flag == 1 && i < s->length - 1; i++)
        {
    	flag = 0;
    	//j从后往前循环
    	for (int j = s->length - 1; j > i; j--)
    	{
    	    if (s->data[j - 1] > s->data[j])
    	    {
    		Swap(s, j - 1, j);
    		flag = 1;
    	    }
    	}
    	Show(s);
        }
    }

其比较过程为：

![20190130161802282.png][]

以上即为冒泡排序的解释，可以看出，对于n个关键字，在第i趟的比较中，需要对前n-i-1个关键字进行n-i次比较，没有数据的交换，时间复杂度为O(n)，最坏情况下，即待排序表逆序，此时需要比较n(n-1)/2次。最好的情况是待排序序列已经有序，此时只需要进行一次冒泡过程。因此，总的时间复杂度为O(n^2)。

二、简单选择排序

简单选择排序是基于选择排序的一种排序算法。选择排序的基本思路是：从n个关键字序列中找到一个最小值，并把它放到序列首端，再从剩下的n-1个关键字中选择最小值，仍然放到这n-1个关键字的序列首端，以此类推。而一趟简单选择排序的操作为：通过n-1次关键字之间的比较，从n-i-1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换。

void Simple_Selection_Sort(SqList* s)
    {
        for (int i = 0; i < s->length - 1; i++)
        {
    	int min = i;	//将当前下标min定义为最小值下标
    	for (int j = i + 1; j < s->length; j++)
    	{
    	    //如果有比当前关键字小的，将此关键字的下标赋值给min
    	    if (s->data[j] < s->data[min])
    	    {
    		min = j;
    	    }
    	}
    	//如果当前最小值的下标与i不相等，说明有比当前下标的关键字还小的关键字，所以交换
    	if (i != min)
    	{
    	    Swap(s, i, min);
    	}
    	Show(s);
        }
    }

其每趟排序结果为：

![20190130171542721.png][]

简单选择排序最大的特点就是交换移动数据次数相当少，也就节约了时间。另外，无论是最好还是最坏情况，其比较次数都是一样多的，第i趟排序需要进行n-i次关键字的比较，需要比较n(n-1)/2次。而对于交换次数而言，当最好的时候，即待排序序列已经有序，交换次数为0，最差的时候，即待排序序列逆序时，交换次数为n-1次。最终的排序时间是比较与交换次数的总和，所以，总的时间复杂度为O(n^2)。虽然与冒泡算法的时间复杂度相等，但其性能还是略优于冒泡排序。

三、直接插入排序

直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加1的有序表。假设待排序序列有五个关键字，则默认第一个关键字天然有序，从第二个关键字开始，与天然有序的第一个关键字进行比较，并选择合适位置插入。也就是相当于把待排序序列分成两部分。最开始的时候，最左部分只有一个关键字，我们认为其天然有序，然后将剩下的关键字组成第二部分，从第二部分的第一个关键字开始，与第一部分的关键字进行比较，然后插入第一部分中，并仍然保持第一部分有序。

void Straight_Insertion_Sort(SqList* s)
    {
        //第一个关键字天然有序，所以从第二个关键字开始遍历
        for (int i = 1; i < s->length; i++)
        {
    	//如果第i个关键字比前一个关键字还小
    	if (s->data[i] < s->data[i - 1])
    	{
    	    //先将第i个关键字的值存起来
    	    ElemType temp = s->data[i];
    	    //j从0开始
    	    int j = i - 1;
    	    //如果第j个关键字比temp还大
    	    for (; j >= 0 && s->data[j]>temp; j--)
    	    {
    		//将data[j]赋值给data[j+1]，即让已有序序列后移
    		s->data[j + 1] = s->data[j];
    	    }
    	    //j=-1时，直接将temp赋值给data[0]
    	    s->data[j + 1] = temp;
    	}
    	Show(s);
        }
    }

其排序过程为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70][]

此算法从空间上来看，需要一个记录的辅助空间。最好的情况下，即序列本身有序，因此不需要移动数据，时间复杂度为O(n)。最坏的情况下，即待排序序列逆序，此时需要比较(n+2)(n-1)/2次，移动 次数也达到了最大值(n+4)(n-1)/2次。平均情况下，比较和移动的次数约为(n^2)/4次。因此，直接插入排序算法的时间复杂度为O(n^2)。虽然时间复杂度也是O(n^2)，但性能比冒泡排序和简单选择排序都要好。

四、希尔排序

希尔排序算法是突破O(n^2)时间复杂度的排序算法之一。其基本思想是：将原有的记录进行分组。分割成若干个子序列，此时每个子序列中待排序的记录个数相比之前就少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时再对全体记录进行一次直接插入排序。所谓的基本有序就是小的关键字基本在前面，大的关键字基本在后面，不大不小的基本在中间。但是我们要怎样做才能使得分割后的子序列基本有序呢？此时我们采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。于是希尔排序的关键就是“增量”的选取。迄今为止还没有人找到一种好的增量序列，但是，不论增量序列如何取值，最后一个增量值必须为1。

对于我们所使用的待排序记录来说，就是让下标为0、4、8的记录相比较，下标为1、5、9的记录相比较，下标为2、6的记录相比较，下标为3、7的记录相比较，至此，第一次step结束；第二次step=2，那么就让下标为0、2、4、6、8的记录相比较，下标为1、3、5、7、9的记录相比较；之后第三次step=1，让每一条记录都分别比较。至此，step已经等于1，排序结束。

void InsertSortByShell(SqList* s, int step)
    {
        for (int i = step; i < s->length; i++)
        {
    	if (s->data[i] < s->data[i - step])
    	{
    	    int t = s->data[i];
    	    int j = i - step;
    	    for (; j >= 0 && s->data[j] > t; j = j - step)
    	    {
    		s->data[j + step] = s->data[j];
    	    }
    	    s->data[j + step] = t;
    	}
        }
        Show(s);
    }
    void Shell_Sort(SqList* s)
    {
        int step = s->length;
        while (1)
        {
    	//增量序列
    	step = step / 3 + 1;
    	InsertSortByShell(s, step);
    	if (step == 1)
    	{
    	    break;
    	}
        }
    }

其每次比较过程为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1][]

希尔排序算法的时间复杂度为O(n^(3/2))，相比之前的O(n^2)的排序算法来说，希尔排序使我们突破了慢速排序的时代，具有划时代的意义。

五、堆排序

堆排序其实是对简单选择排序算法的一种改进。

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，此为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，此为小顶堆。

堆排序就是利用堆进行排序的方法，它的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个值再重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列。于是，堆排序的重点就变成了如何由一个无序序列构建一个堆和如何在输出堆顶元素之后调整剩下的元素成为一个新的堆。

//堆排序（非递归）
    void HeapAdjust(SqList* s, int root, int length)
    {
        //取出根结点数据
        int temp = s->data[root];
        //左孩子结点
        int i = 2 * root + 1;
        while (i < length)
        {
    	//不是最后一个结点表示还有右孩子，而且要保证右孩子大于左孩子
    	if (i != length - 1 && s->data[i] < s->data[i + 1])
    	{
    	    i++;
    	}
    	if (temp < s->data[i])
    	{
    	    s->data[root] = s->data[i];
    	    root = i;
    	    i = 2 * root + 1;
    	}
    	else
    	{
    	    break;
    	}
            s->data[root] = temp;
        }
        Show(s);
    }
    void Heap_Sort(SqList* s)
    {
        for (int i = s->length / 2; i >= 0; i--)
        {
    	HeapAdjust(s, i, s->length);
        }
        for (int j = s->length - 1; j >= 0; j--)
        {
    	Swap(s, 0, j);
    	HeapAdjust(s, 0, j);
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2][]

堆排序的运行时间主要是消耗在初始构建堆和重建堆时的反复筛选上。在构建堆的过程中，因为我们是从完全二叉树的最下层最右边的非终端结点开始构建，将它与其孩子进行比较和互换，因此整个堆的构建时间复杂度为O(n)。在正式排序时，第i次取堆顶记录重建堆需要用O(logi)(完全二叉树的某个结点到根节点的距离为![\\left \\lfloor \\log\_\{2\}i \\right \\rfloor + 1][left _lfloor _log_2_i _right _rfloor _ 1])的时间，并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

六、归并排序

归并排序就是利用归并的思想（所谓归并，在数据结构中定义为将两个或两个以上的有序表组合成一个新的有序表）实现排序。它的原理是假设初始序列中含有n个记录，则可以看成是n个有序子序列，每个子序列的长度为1，然后两两归并，得到![\\left \\lceil n / 2 \\right \\rceil][left _lceil n _ 2 _right _rceil]个长度为2或1的有序子序列；然后再两两合并，重复此过程，直至得到一个长度为n的有序序列。

//归并排序（递归）
    void Merge(SqList* s, int first, int mid, int last)
    {
        ElemType temp[MAXSIZE];
        int i = first;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= last)
        {
    	if (s->data[i] < s->data[j])
    	{
    	    temp[k++] = s->data[i++];
    	}
    	else
    	{
    	    temp[k++] = s->data[j++];
    	}
        }
        while (i <= mid)
        {	
            temp[k++] = s->data[i++];
        }
        while (j <= last)
        {
    	temp[k++] = s->data[j++];
        }
        for (int i = 0; i < k; i++)
        {
    	s->data[first + i] = temp[i];
        }
        Show(s);
    }
    void MSort(SqList* s, int first, int mid, int last)
    {
        if (first < last)
        {
    	MSort(s, first, (first + mid) / 2, mid);
    	MSort(s, mid + 1, (mid + 1 + last) / 2, last);
    	Merge(s, first, mid, last);
        }
    }
    void Merge_Sort(SqList* s)
    {
        int first, mid, last;
        first = 0;
        last = s->length - 1;
        mid = (first + last) / 2;
        MSort(s, first, mid, last);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 3][]

复杂度分析：一趟归并需要将待排序序列中相邻的长度为n的有序序列进行两两合并，将结果放到额外申请的空间temp中，这需要将待排序序列中所有的记录扫描一遍，耗时O(n)，而整个归并排序需要进行![\\left \\lceil \\log\_\{2\}n \\right \\rceil][left _lceil _log_2_n _right _rceil]次，因此，总的时间复杂度为O(nlogn)。而归并排序需要申请额外空间，所以空间复杂度为O(n+logn)。

七、快速排序

快速排序的基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

void QSort1(SqList* s, int first, int last)
    {
        if (first < last)
        {
    	int key = s->data[first];
    	int i = first;
    	int j = last;
    	while (i < j)
    	{
    	    while (i < j && s->data[j] >= key)
    	    {
    	        j--;
    	    }
    	    Swap(s, i, j);
    	    while (i < j && s->data[i] <= key)
    	    {
    	        i++;
    	    }
    	    Swap(s, i, j);
    	    Show(s);
    	}
    	QSort1(s, first, i - 1);
    	QSort1(s, j + 1, last);
        }
    }
    void Quick_Sort(SqList* s)
    {
        QSort1(s, 0, s->length - 1);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 4][]

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，此时需要n-1次递归调用，且第i次划分需要经过第n-i次关键字的比较才能找到第i个记录，因此比较次数为n(n-1)/2，其时间复杂度就为O(n^2)。

**总结：**

冒泡排序：对于包含n个元素的待排序数组，重复遍历数组，首先比较第一个和第二个元素，若为逆序，则交换位置；然后比较第二个和第三个元素，重复上述过程。每次遍历会把当前n-i个元素中的最大元素移到n-i的位置。遍历n次，完成排序。

简单选择排序：每次循环选择当前无序数组中最小的哪个元素，然后将其与无序数组的第一个元素交换位置，从而使有序数组元素加1，无序数组元素减1，初始时无序数组为空。

直接插入排序：对于一个待排序数组来说，其初始有序数组元素个数为1，然后从第二个元素开始，依次插入到有序数组中。对于每一次插入操作，从后往前遍历当前有序数组，如果当前元素大于要插入的元素，则后移一位；如果当前元素小于或等于要插入的元素，则将要插入的元素插入到当前元素的下一位中。

希尔排序：先将整个待排序记录分割成若干个子序列，然后分别进行插入排序，待整个序列中的记录基本有序时i，再对全体记录进行一次直接插入排序。其子序列的构成不是简单的逐段分割，而是将每隔某个增量的记录组成一个子序列。希尔排序时间复杂度与增量序列的选取有关，其最后一次值必须为1。

堆排序：堆排序是一种选择排序，利用堆这种数据结构来完成选择。其算法思想是将待排序数据构造一个最大堆或最小堆，然后将堆顶元素与待排序数组的最后一个元素交换位置，此时末尾元素就是最大/最小值，然后将剩余的n-1个元素重新构造成最大堆/最小堆。

归并排序：归并算法采用分治法。对于包含n个元素的待排序序列，将其看成n个长度为1的子序列。然后两两合并，得到n/2个长度为2或者为1的有序子序列；然后再两两合并，直到得到1个长度为n的有序序列。

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的数据都小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th style="width:177px;">排序算法</th> 
   <th style="width:173px;">空间复杂度</th> 
   <th>平均情况</th> 
   <th>最好情况</th> 
   <th>最差情况</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <th style="width:177px;">冒泡排序</th> 
   <td style="width:173px;">O(1)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">简单选择排序</th> 
   <td style="width:173px;">O(1)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">直接插入排序</th> 
   <td style="width:173px;">O(1)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">希尔排序</th> 
   <td style="width:173px;">O(1)</td> 
   <td>O(nlogn）~ O(n^2)</td> 
   <td>O(n^1.3)</td> 
   <td>O(n^2)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">堆排序</th> 
   <td style="width:173px;">O(1)</td> 
   <td>O(nlogn）</td> 
   <td>O(nlogn）</td> 
   <td>O(nlogn）</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">归并排序</th> 
   <td style="width:173px;">O(n)</td> 
   <td>O(nlogn）</td> 
   <td>O(nlogn）</td> 
   <td>O(nlogn）</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <th style="width:177px;">快速排序</th> 
   <td style="width:173px;">O(logn) ~ O(n)</td> 
   <td>O(nlogn）</td> 
   <td>O(nlogn）</td> 
   <td>O(n^2)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

排序规模不大时，适合直接插入排序、简单选择排序、冒泡排序，虽然时间复杂度稍逊于快速排序，但是实现简单。

快速排序的综合表现最佳。空间复杂度稍逊于堆排序等，序列有序时时间复杂度稍逊于堆排序，但其实现难度比堆排序简单。

当排序规模很大，而且对稳定性有相应要求时，可采用归并排序。

[left _ r_1_ _r_2_......_r_n_right]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7B%20r_%7B1%7D%20%2Cr_%7B2%7D%2C......%2Cr_%7Bn%7D%5Cright%20%5C%7D
[left _ k_1_k_2_......_k_n_ _right]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7B%20k_%7B1%7D%2Ck_%7B2%7D%2C......%2Ck_%7Bn%7D%20%5Cright%20%5C%7D
[p_1_p_2_......_p_n]: https://private.codecogs.com/gif.latex?p_%7B1%7D%2Cp_%7B2%7D%2C......%2Cp_%7Bn%7D
[k_p_1_leq k_p_2_leq ......_leq k_p_n]: https://private.codecogs.com/gif.latex?k_%7Bp_%7B1%7D%7D%5Cleq%20k_%7Bp_%7B2%7D%7D%5Cleq%20......%5Cleq%20k_%7Bp_%7Bn%7D%7D
[left _ r_p_1_ r_p_2_ ......_ r_p_n_ _right]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7B%20r_%7Bp_%7B1%7D%7D%2C%20r_%7Bp_%7B2%7D%7D%2C%20......%2C%20r_%7Bp_%7Bn%7D%7D%20%5Cright%20%5C%7D
[k_i_ k_j_left _ 1_leq i_leq n_1_leq j_leq n_i_neq j _right]: https://private.codecogs.com/gif.latex?k_%7Bi%7D%3D%20k_%7Bj%7D%5Cleft%20%28%201%5Cleq%20i%5Cleq%20n%2C1%5Cleq%20j%5Cleq%20n%2Ci%5Cneq%20j%20%5Cright%20%29
[r_i]: https://private.codecogs.com/gif.latex?r_%7Bi%7D
[r_j]: https://private.codecogs.com/gif.latex?r_j
[20190130160431726.png]: /images/20220321/214dc0a64f574f7b8dea24bf57158e8a.png
[2019013016065117.png]: /images/20220321/fe58d399892d4fe3b3eda2f693b2cea5.png
[20190130161802282.png]: /images/20220321/b8a684dc51e341debf35251050b16f98.png
[20190130171542721.png]: /images/20220321/7e19ed2a929f48afa10a40af91e94bc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70]: /images/20220321/604e975a64ec460db87e9e78416e8016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1]: /images/20220321/70c0f4d646b9477e883c30d348d9ab34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2]: /images/20220321/58807a7bb19a4ef99056f4b2cb071940.png
[left _lfloor _log_2_i _right _rfloor _ 1]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20%5Clog_%7B2%7Di%20%5Cright%20%5Crfloor%20&plus;%201
[left _lceil n _ 2 _right _rceil]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clceil%20n%20/%202%20%5Cright%20%5Crceil
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 3]: /images/20220321/7085612ddbbe446a968c5b6b7d946e61.png
[left _lceil _log_2_n _right _rceil]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clceil%20%5Clog_%7B2%7Dn%20%5Cright%20%5Crceil
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 4]: /images/20220321/3aa5d0bff3b94d64902081dd5c3e5446.png