数据结构回顾——排序

- 日理万妓 2023-03-01 10:52 50阅读 0赞

**要求：掌握算法思想，性能分析，代码实现**

**注：本文默认递增排序**

一，排序的基本概念

1，什么是排序：将一个没有顺序的数列进行重新排列是它成为一个递增（递减）序列

2，稳定性：如果数列中有两个元素的值是相等的，排序后他们的相对位置没有发生改变，就认为该排序算法稳定。

3，内部排序：指排序期间元素全部存放在内存中的排序

外部排序：排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断在内，外存之间进行移动

## 二，直接插入排序 ##

插入排序：每次将一个待排序的序列插入到一个前面已经排好的子序列中

### 1，直接插入排序： ###

设已知数列\[ a1 a2,,,ai,,,,an\]，已知a1,,,ai已经是递增序列了，如何将ai+1号元素插入到a1,,,ai中使得，它们任然是有序序列

**思想：**

*  找到位置k，有k前面的元素小于ai+1号元素，有k后面的元素大于ai+1号元素。
 *  将ai+1元素暂存在中间变量中（空间复杂度O(1)）
 *  将ak,,,,ai的所有元素后移一个位置，空出ak来存放ai+1元素，后移过程中ai元素刚好替换ai+1的位置

**代码实现：**

void InsertSort(int A[],int n){
    	int i,j;
    	
    	for(i=2;i<=n;i++){
    		A[0]=A[i];//A[0]是哨兵暂存A[i]
    		for(j=i-1;A[0]<A[j];j--)//从后向前监测合适的位置k
    			A[j+1]=A[j];//检查的过程中顺便将元素后移
    		A[j+1]=A[0];//插入
    	}
    
    }

性能分析：

*  最好时间复杂度：O(n)   一开始就是递增的有序序列
 *  平均时间复杂度：O(n2)
 *  最坏时间复杂度：O(n2)   一开始就是递减的有序序列
 *  空间复杂度：O(1)
 *  是稳定的算法，适用于顺序存储和**链式存储**

### 2，折半插入排序 ###

**思想**：对直接插入排序进行改进，将其查找插入位置k的过程由**顺序查找改为折半查找**

**代码实现：**

void BInsertSort(int A[],int n){
    	int i,j;
    	int low,high,mid;
    	
    	for(i=2;i<=n;i++){
    		A[0]=A[i];
    		
    		low=1;high=i-1;
    		while(low<high){//折半查找合适的插入位置k
    			mid=(low+high)/2;
    			if(A[mid]>A[0])
    				high=mid-1;
    			else
    				low=mid+1;
    		}
    		for(j=i-1;j>=high+1;j--)//向后移动元素
    			A[j+1]=A[j];
    		A[high+1]=A[0];//插入元素
    	}
    }

## ##

**性能分析：**

*  时间复杂度：O(n2)
 *  空间复杂度：O(1)
 *  是稳定算法
 *  适用于顺序存储

### 3，希尔排序： ###

**思想**：先将排序表分割成d个形如  \[i，i+d，i+2d，i+3d,,,,i+kd\]的特殊子表，分别进行直接插入排序，当整个表中元素已经基本有序时，再对全体记录进行一次直接插入排序。

**代码实现：**

void ShellSort(int A[],int n){
    	int i,j;
    	for(int dk=n/2;dk>n;dk=dk/2){//每次步长取表长的一半
    		for(i=dk+1;i<n;++i){//所有子表同时进行插入排序
    			if(A[i]<A[i-dk]){//如果子表中的大小不是递增排序
    				A[0]=A[i];//将i号元素暂存在A[0]
    				for(j=i-dk;j>0&&A[0]<A[j];j-=dk)//交换两个元素的位置
    					A[j+dk]=A[j];
    				A[j+dk]=A[0];
    			}
    		}
    	}
    	for(int k=1;k<n;k++)//显示排序结果
    		printf("%d\n",A[k]);
    }

**性能分析：**

*  最坏时间复杂度：O(n2)
 *  平均时间复杂度：O(n1.3)
 *  空间复杂度：O(1)
 *  是**不稳定**算法
 *  适用于顺序存储

## 三，交换排序 ##

### 1，冒泡排序： ###

**思想：**假设待排序表长为n，从后往前（从前往后）两两比较相邻元素的值，如果是逆系（A\[i-1\]>A\[i\]）就交换他们，直到序列比较为止。每一趟遍历表的比较就会让一个最大（最小）元素归位，就像冒气泡一样所以叫冒泡排序。n趟比较后所以元素归位。

**代码实现**

void BubbleSort(int A[],int n){
    	int i,j,temp;
    	bool flag;//如果是递增序列直接跳出循环减少运行时间的标志
    	for(i=0;i<n;i++){
    		for(j=n-1;j>i;j--){
    			if(A[j-1]>A[j]){//前面元素大于后面元素，就交换
    				temp=A[j];
    				A[j]=A[j-1];
    				A[j-1]=temp;
    				flag=true;
    			}
    			if(flag==false)
    				return;//是递增序列，结束循环
    		}
    	}
    	for(int k=0;k<n;k++){//打印排序结果
    		printf("%d\n",A[k]);
    		
    	}
    }

**性能分析：**

*  最好时间复杂度：O(n)    数列是递增序列
 *  平均时间复杂度：O(n2)   n(n-1)/2
 *  最坏时间复杂度：O(n2) 
 *  空间复杂度：O(1)
 *  是**稳定**算法
 *  适用于顺序存储和链式存储

### 2，快速排序 ###

**思想：**在排序表【1，，，n】中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为两个部分，pivot前面的元素均小于它，后面的元素均大于它。所以一次划分会让当前的pivot元素归位，进行对已经划分的部分进行相同操作，知道每一个元素归位。

**一次划分实现思路：**

*  初始化标记low为划分部分第一个元素的位置，high为最后一个元素的位置，然后不断地移动标记并交换元素
 *  high向前移动找到第一个比pivot小的元素，
 *  low向后移动找到第一个比pivot大的元素
 *  交换当前两个位置的元素
 *  进行移动标记，执行上述过程，直到low>high为止

**代码实现：**

int Partition(int A[],int low,int high){
    	int pivot=A[low];
    	while(low<high){//一次排序交换一对元素 
    		while(low<high&&A[high]>=pivot)
    			high--;
    		A[low]=A[high];//找到大于pivot的元素，把它存到对应要交换的位置 
    		while(low<high&&A[low]<=pivot)
    			low++;
    		A[high]=A[low];//找到小于pivot的元素，把它存到对应要交换的位置 
    	}
    	A[low]=pivot;
    	return low;
    }
    void QuickSort(int A[],int low,int high){
    	if(low<high){
    		int pivotPos=Partition(A,low,high);
    		QuickSort(A,low,pivotPos-1);//左边部分递归调用 
    		QuickSort(A,pivotPos+1,high);//右边部分递归调用 	
    	}
    }

**性能分析：**

*  最好平均时间复杂度：O(n\*log2n)
 *  最坏时间复杂度：O(n2)：已经是递增序列
 *  最好平均空间复杂度：O(log2n)
 *  最坏空间复杂度：O(n)
 *  是**不稳定**算法
 *  适用于顺序存储和链式存储

## 四，选择排序 ##

### 1，直接选择排序 ###

**思想：**没一趟都在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到n-1趟做完，待排序元素只剩下一个。也就是每次从数量中找到最小元素取出来放到前面排序。

**代码实现**

void SelectSort(int A[],int n){
    	int temp; 
    	for(int i=0;i<n-1;i++){
    		int min=i;//存取最小元素的下标
    		for(int j=i+1;j<n;j++)
    			if(A[j]<A[min])
    				min=j;
    		if(min!=i)//最小值元素不是i时 
    			{
    			 temp=A[i];
    			 A[i]=A[min];
    			 A[min]=temp;
    		} 
    	}
    	for(int k=0;k<n;k++){//打印排序结果
    		printf("%d\n",A[k]);
    		
    	}
    }

**性能分析：**

*  时间复杂度：O(n2)  与初始序列无关
 *  空间复杂度：O(1)
 *  是**不稳定**算法
 *  适用于顺序存储和链式存储

### 2，堆排序 ###

小根堆：数列中第i个元素L(i)<L(2i)，L(i)<L(2i+1)，即根节点小于两个孩子节点

大根堆：数列中第i个元素L(i)>L(2i)，L(i)>L(2i+1)，即根节点大于两个孩子节点

**大根堆的初始化：**

*  如果孩子节点都小于双亲节点，则该节点的调整结束
 *  如果存在孩子节点大于双亲节点，则将最大的孩子节点与双亲节点交换。调整到叶节点为止

**代码实现：**

void AdjustDown(int A[], int k,int len){//调整节点 
    	A[0]=A[k];//暂存该节点的值
    	for(int i=2*k;i<=len;i*=2){
    		if(i<len&&A[i]<A[i+1])//左孩子小于右孩子，就将i指向右孩子 
    			i++;
    		if(A[0]>=A[i])//如果双亲节点的值比孩子节点大就不需要进行交换 
    			break;
    		else{//如果双亲节点的值比孩子节点小就交换
    			A[k]=A[i];
    			k=i;
    		}
    	}
    	A[0]=A[k];
    	
    }
    void BuildMaxHeap(int A[],int len){//初始化大根堆 
    	for(int i=len/2;i>0;i--){
    		AdjustDown(A,i,len);
    	}
    }
    void heapSort(int A[],int len){//堆排序 
    	int temp;
    	BuildMaxHeap(A,len);
    	for(int i=len;i>1;i--){
    		temp=A[i];
    		A[i]=A[1];
    		A[1]=temp;
    		AdjustDown(A,1,i-1);
    	}
    	for(int k=0;k<len;k++){//打印排序结果
    		printf("%d\n",A[k]);
    		
    	}
    }
    
    void AdjustUp(int A[],int k,int len){//插入调整 
    	A[0]=A[k];//暂存插入末尾元素k 
    	int i=k/2;//双亲节点编号 
    	while(i>0&&A[i]<A[0]){//如果双亲节点的值小于末尾节点 
    		A[k]=A[i];//将它与它的双亲节点交换 
    		k=i;
    		i=k/2;
    	}
    	A[k]=A[0];
    }

**性能分析：**

*  时间复杂度：O(n\*log2n) 
 *  空间复杂度：O(1)
 *  是**不稳定**算法
 *  适用于顺序存储和链式存储

## 五，二路归并排序 ##

**思想：**将相邻的两组序列进行有序的归并。开始时一个元素为一组，n个元素为n组，然后将相邻i号元素和i+1号元素归并成有序序列，就出现n/2组，继续对他们进行归并出现n/4组，，，，直到归为一组为止。

**代码实现：**

**(代码有问题）**

void Merge(int A[],int low,int mid,int high){//将相邻序列进行合并 
    	int B[high];
    	for(int k=low;k<high;k++)
    		B[k]=A[k];
    	for(int i=low,j=mid+1,k=i;i<mid&&j<high;i++){
    		if(A[k]=B[j++])
    			A[k]=B[i++];
    		else
    			A[k]=B[j++];
    	}
    	int i,j,k;
    	while(i<=mid)
    		A[k++]=B[i++];
    	while(j<=high)
    		A[k++]=B[j++];
    } 
    void MergeSort(int A[],int low,int high){//归并排序 
    	if(low<high){
    		int mid=(low+high)/2;
    		MergeSort(A,low,mid);//一直递归调用直到把n个元素分为n组 
    		MergeSort(A,mid+1,high);
    		Merge(A,low,mid,high);//将相邻两组合并 
    		
    	}
    }

**性能分析：**

*  时间复杂度：O(n\*log2n) 
 *  空间复杂度：O(n)
 *  是**稳定**算法
 *  适用于顺序存储和链式存储

## 六，基数排序 ##

**思想：**借助“分配”和“收集”两种操作对逻辑关键字进行最高位优先（MSD）和最低位优先(LSD).

以r为基数的最低位优先基数排序过程：

*  现有数组元素：324  768  170  121   962   666   857  503   768
 *  n=9表示元素有9个，d=3表示每个元素有3位，r=10表示所有组成元素的数都0=<r<10
 *  排序时使用r个队列也就是10个队列，0，，，9号队列
 *  按元素个位数进行入队，如：324入队列4，768如队列8，170入队列0....然后0~9号队列元素按顺序出队形成一个新队列
 *  270  121  962  503  324  666  857  768  768
 *  按元素十位数进行入队，如：270入队列7，121如队列2，962入队列6....然后0~9号队列元素按顺序出队形成一个新队列
 *  503  121  324  857  962  666  768  768  270
 *  按元素百位数进行入队，如：530入队列3，121如队列1，324入队列3....然后0~9号队列元素按顺序出队形成一个新队列
 *  121  270  324  503  666  768  768  857  962

**性能分析：**

*  时间复杂度：O(d\*l(n+r)) 
 *  空间复杂度：O(r)
 *  是**稳定，不基于比较**算法

## 七，内部排序算法的比较和应用 ##

![20200725083616222.png][]

1.  直接插入排序，冒泡排序在数列有序的情况下达到最好的时间复杂度O(n)
2.  然而快速排序在数列有序的情况下，却是最坏时间复杂度O(n2)
3.  快速排序中利用了递归栈所以空间复杂度为O(log2n)，二路归并中利用了辅助数组所以空间复杂度为O(n)，基数排序中我们利用了r个辅助队列所以空间复杂度为O(r)
4.  简单选择排序，希尔排序，快速排序，堆排序是不稳定的算法
5.  冒泡排序，简单选择排序，堆排序。每一趟比较中都会确定一个最大（最小）元素最终的位置。快速排序每一趟比较中会确定一个中间元素的位置。

### 内部排序应用： ###

**考虑的因素**

1.  初始元素的数目，元素大小：有的算法需要交换元素，如果元素数目很大就会影响效率
2.  关键字结构及其分布：分布只初始序列是否成有序，无序会影响效率。结构指是是否所有元素位数相同，如果相同就可以用基数排序
3.  稳定性，存储结构，辅助空间

*  如果n较小时(n<50）可以直接插入排序或者简单选择排序，如果n较大时则使用快排，堆排序，归并排序
 *  n很大时，记录关键字位数较少，可以分解。使用基数排序
 *  当文件n个关键字随机分布时，任何借助比较的排序，至少需要O(n\*log2n)的时间
 *  如果初始序列基本有序，则采用直接插入排序或者冒泡排序
 *  当记录的元素比较大，应该避免大量移动的排序算法，尽量采用链式存储

## 八，外部排序： ##

外部排序通常采用归并排序的方法

*  首先，根据缓冲区的大小将外存上含有n个记录的文件分成诺干个长度为h的子文件，依次读入内存并利用有限的内部排序对它进行排序，并将排序后得到的有序子文件重新写会外存，通常我们称这些有序子文件为归并段或顺串
 *  然后对这些归并段进行归并，使得归并段逐渐有小到大直到得到整个有序文件
 *  外部排序总时间=内部排序时间+外部信息读写时间+内部归并时间    T=r\*Tis  + d\*Tio  +  S(n-1)Tmg
 *  例：有20000个记录，初始归并段5000个记录

r=20000/50000=4        r=3\*(4+4)   3次分割才会将分成4块，4次读+4次写      S=2一共需要两次归并

T=4\*Tis  +  3\*(4+4)\*Tio  +2\*(20000-1)Tmg    归并的趟数=logmR  +  1  (m路归并，R为初始归并段数量）

**失败树：**是树形选择排序的一种变形体，可以看成一棵完全二叉树，每个叶节点存放各个归并段在归并过程中当前参加比较的记录，内部节点用来左右子树中的失败者，胜利者向上继续比较，直到根节点。

S趟归并总共需要比较是次数S(n-1)(m-1)=\[logmR +1\]\*(n-1)(m-1) =\[logmR +1\]\*(n-1)

**置换-选择排序：**设初始待排文件为FI，初始归并段问阿金为FO，内存工作区为WA，内存工作区可以容纳w个记录。

思想：

1.  从待排文件FI输入w个记录到工作区WA中
2.  从内存工作区WA中选出其中关键字最小值的记录，记录为MINIMAX
3.  将MINNIMAX记录输出到FO中
4.  如果FI未读完，则从FI输入下一个记录到WA中
5.  从WA中使用关键字比MINIMAX记录的关键字记录中选出最小关键字记录，作为新的MINIMAX
6.  重复3~5，直到WA中选不出新的MINIMAX记录位置，由此得到一个初始归并段，输出一个归并段的结束标志到FO中
7.  重复2~6，直到WA为空，由此得到全部初始归并段

![20200725101239325.png][]

**最佳归并树：**用来描述m归并，并且只有度为0和度为m的节点的严格m叉树

有已知序列构造m叉哈夫曼树，如果叶节点数不足，0补上

度为m的节点个数Nm=(N0-1)/(m-1)，如果(N0-1)%(m-1)==0，说明这N0个叶节点可以构造m叉归并树，如果(N0-1)%(m-1)==u!说明这N0个叶节点有u个节点是多余的，补充m-u-1个节点

![2020072510201727.png][]

# 补充，Java版本: #

package com.deme_security;
    
    import java.lang.reflect.Array;
    import java.util.ArrayList;
    
    /**
     * 插入排序：直接插入排序、二分法插入排序、希尔排序。
     * 选择排序：简单选择排序、堆排序。
     * 交换排序：冒泡排序、快速排序。
     * 归并排序
     * 基数排序
     */
    public class SortTest {
        public static void main(String[] args) {
            int []a={3,4,5,1,2,6,7,10,11,8,9};
            sort1(a);
            System.out.println("====》直接插入排序");
            sort2(a);
            System.out.println("====》折半插入排序");
            sort3(a);
            System.out.println("====》希尔排序");
            sort4(a);
            System.out.println("====》选择排序");
            sort5(a);
            System.out.println("====》堆排序");
            sort6(a);
            System.out.println("====》冒泡排序");
    //        sort7(a,0,a.length-1);
    //        show(a);
    //        System.out.println("====》快速排序");
            sort8(a,0,a.length-1);
            show(a);
            System.out.println("====》归并排序");
    
        }
    
        /**
         * 方法：直接插入排序
         * 思想：
         * 默认第一个元素是有序列表。
         * 记录要排序的元素temp=a[i]
         * 从第二个元素开始，和顺序表中的元素进行比较，找到可以插入元素的位置。
         * 把有序列表中大于temp的元素后移一个位置，空出插入的位置
         * 插入元素
         */
        static void sort1(int a[]){
            int temp,i,j;
            for(i=1;i<a.length;i++){//把第一个数当成一个有序数列，从第二个数开始比较
                temp = a[i];  //保存要比较的值
                for(j=i-1;j>=0&&a[j]>temp;j--){
                    //对前i个已经排好序的列表,从列表的最后一个元素向前遍历，与temp值进行比较，如果有序列表元素a[j]比temp大就把该元素后移
                    //直到a[j]元素比temp小的时候停止移动，即找到了插入位置
                    a[j+1] = a[j]; //依次移动
                }
                a[j+1] = temp; //插入,此处的arr[j+1]其实是上边的“arr[j]”，执行了一个j--操作
            }
            show(a);
        }
    
        /**
         * 方法：折半插入
         * 思想：
         * 记录要插入的元素temp=a[i]
         * 对前面有序列表折半查找可以插入的位置，
         * 将有序列表中比temp大的元素后移一位，流出一个空间插入temp元素
         */
    
            public static void sort2(int[] a) {
                int low, mid, high;
                int temp;
                //从数组第二个元素开始排序
                for (int i = 1; i < a.length; i++) {//每个元素都使用折半查找，在前面有序列表中寻找可以插入的位置
                    temp = a[i];
                    low = 0;//有序列表的头部
                    high = i - 1;//有序列表的尾部
                    while (low <= high) {
                        mid = (low + high) / 2;
                        if (temp < a[mid])//左边区间
                            high = mid - 1;
                        else//右边区间
                            low = mid + 1;
                    }
                    //将a[low]--a[i-1]的数都想后移一位，插入元素的位置空出来
                    for (int j = i; j > low; j--) {
                        a[j] = a[j - 1];
                    }
                    a[low] = temp;    //最后将a[i]插入a[low]
                }
                show(a);
            }
    
        /**
         * 方法：希尔排序
         * 思想：
         * i从0+d开始，因为分组后的第一组是0,d,2d,3d...这样一个序列.所以直接从d开始比较
         * 此循环比较算法区别：假设有一个16项数组，下标为0~15,当d=5时，分为5组
         * 以下标表示：(0,5,10,15),(1,6,11),(2,7,12),(3,8,13),(4,9,14)
         * 如果分别针对每一组插入排序，则下标控制很复杂，所以外层for循环每次对每一分组的前2个数据排序
         * 然后前3个，然后前4个...这和组数有关
         * 即当i=5时，对（0,5,10,15）中的（0,5）排序
         * i=6时，对（1,6,11）中的（1,6）排序.....
         * i=10时，对（0,5,10,15）中的（0,5,10）排序......
         * 一直到d=1时，此时的数组基本有序，数据项移动次数大大减少
         * */
    
            public static void sort3(int[] a) {
                int d = a.length / 2;//组距离从表长的一般开始，每次减半
                int temp;
                while (d > 0) {
                    for (int i = d; i < a.length; i++) {
                        temp = a[i];
                        int j = i;  //从该组最右往左开始比较
                        //j要大于等于第一个数的下标，且temp比上一位数值要小
                        while (j >= d && temp < a[j - d]) {//每组进行直接插入排序
                            a[j] = a[j - d];                //把上一位向后移(组内移动)
                            j -= d;
                        }
                        a[j] = temp;
                    }
                    d = d / 2;
                }
                show(a);
            }
    
        /**
         * 选择排序，每次从后面无序列表中选出最小值插入前方有序列表
         * @param a
         */
        public static void sort4(int[] a) {
            int temp;
            int k, min; //最小数下标K,值为min
            for (int i = 0; i < a.length - 1; i++) { //第i趟排序
                k = i;
                min = a[i];
                //从i+1位开始检索最小值
                for (int j = i + 1; j < a.length; j++) {
                    if (a[j] < min) {       //找到最小值并更新min
                        min = a[j];
                        k = j;
                    }
                }
                if (k != i) {      //将找到的最小值与第i位交换
                    a[k] = a[i];
                    a[i] = min;
                }
            }
            show(a);
        }
    
        /**
         * 堆排序
         * @param a
         */
        public static void sort5(int[] a) {
            int temp;
            for (int i=0;i<a.length;i++){
                for (int j=i;j<a.length;j++){
                    if(a[i]>a[j]){
                        temp=a[j];
                        a[j]=a[i];
                        a[i]=temp;
                    }
                }
            }
            show(a);
        }
    
        /**
         * 冒泡排序
         * @param a
         */
        public static void sort6(int[] a) {
           int temp;
           for (int i=0;i<a.length;i++){
               for (int j=i;j<a.length;j++){
                   if(a[i]>a[j]){
                       temp=a[j];
                       a[j]=a[i];
                       a[i]=temp;
                   }
               }
           }
            show(a);
        }
    
        /**
         * 快速排序
         * @param a
         * @param low
         * @param high
         * @return
         */
    
            public static int[] sort7(int[] a, int low, int high){
                if (low < high){
                    int middle = getMiddle(a,low,high);//得到归位元素的下标
                    sort7(a,0,middle-1);//递归遍历左边的数组
                    sort7(a,middle+1,high);//递归遍历右边的数组
                }
                return a;
            }
    
            public static int getMiddle(int[] a,int low, int high){//归位一个元素使得它的左边元素都比他小，右边元素都比他小
                int temp = a[low];
                while (low<high){
                    //从右向左找比基准小的元素并交换
                    while (low<high && a[high]>=temp){
                        high--;
                    }
                    a[low]  = a[high];
                    //从左往右找比基准大的元素并交换
                    while (low<high && a[low]<=temp){
                        low ++;
                    }
                    a[high] = a[low];
                }
                a[low] =temp;
                return low;
            }
    
    
        /**
         * 归并排序
         */
    
            public static int[] sort8(int[] a,int left,int right){
                if (left < right){
                    //划分为两部分，每次两部分进行归并
                    int middle = (left + right)/2;
                    //两路归并，先递归处理每一部分
                    sort8(a,left,middle);
                    sort8(a,middle+1,right);
                    //将已排好序的两两归并排序进行合并
                    merge(a,left,middle,right);
                }
                return a;
            }
            private static void merge(int[] a, int left, int middle, int right){
                int[] tempArr = new int[a.length];//临时数组tempArr[]，用来存放待合并的两路归并排序数组
                int rightIndex = middle +1;//右数组第一个元素索引
                int tempIndex = left;//记录临时数组的索引
                int tmp = left;//缓存左数组第一个元素位置
                while (left <= middle && rightIndex<=right){
                    //从两个数组中取出最小的放入临时数组
                    if (a[left]<=a[rightIndex]){
                        tempArr[tempIndex++] = a[left++];
                    }else {
                        tempArr[tempIndex++] = a[rightIndex++];
                    }
                }
                //剩余部分以此放入临时数组。以下两个while只会执行其中一个
                while (left<=middle){
                    tempArr[tempIndex++] = a[left++];
                }
                while (rightIndex<=right){
                    tempArr[tempIndex++] = a[rightIndex++];
                }
                //将临时数组中的内容拷贝回原数组
                while (tmp<=right){
                    a[tmp]=tempArr[tmp++];
                }
            }
    
    
    
    
    
    
            public static void show(int []a){
            for (int i=0;i<a.length;i++){
                System.out.print(a[i]+"  ");
            }
        }
    
    
    }

[20200725083616222.png]: /images/20230208/05ea5a9f852b454d9b347736bf9fd1b3.png
[20200725101239325.png]: /images/20230208/d1b79f97d42a403db51be5666138cb8c.png
[2020072510201727.png]: https://img-blog.csdnimg.cn/2020072510201727.png