堆排序、归并排序、快速排序总结

浅浅的花香味﹌ 2022-09-28 13:19 121阅读 0赞

昨天刚把这三个排序算法复习了一遍，其中**归并排序**和**快速排序**特别的重要，一定要熟练并理解透彻！

以下排序的结果都默认为非递减

## 1、堆排序（默认大顶堆） ##

堆排序的思想：首先构建一个完全二叉树，从最大的非叶子结点，如果该结点小于孩子结点，则把该结点与最大的孩子结点交换，使该结点不断的往下沉到合适位置。然后又从第二大的非叶子结点开始，不断循环下去直到根节点，这时候便构造出了大顶堆，最后根结点就是堆中最大的节点。交换根结点（arc\[1\]）与最后一个结点（arc\[N--\]），再使新的根节点不断往下沉到合适位置，并形成新的大顶堆，又让根结点（arc\[1\]）与最后一个（arc\[N--\]）交换...不断循环至整个数组有序。

看看具体的代码：

public void heapSort(int arc[]){
    		int N =arc.length-1;
    		for(int i=N/2;i>=1;i--){	       //从最大的非叶子结点开始，构造一个大顶堆		
    			sink(arc,N,i);
    		}
    		while(N>=1){       
    			each(arc,1,N--);              //交换啊arc[1]与arc[N--],注意是N--而不是N
    			System.out.println(arc[N+1]); //输出根结点，即堆中最大的结点
    			sink(arc,N,1);               //使新的根结点往下沉到合适的位置
    		}
    	}
    
    	private void sink(int[] arc,int N,int i) {   //使结点沉到合适的位置
    		
    		int j;
    		while(2*i<=N){
    			j = 2*i;
    			if(j<N&&arc[j]<arc[j+1]){         //j<N防止数据越界，选出两个子结点中的最小值
    				j++;
    			}
    			if(arc[i]>arc[j]){           //如果父结点比两个子结点都大，则跳出循环
    				break;
    			}
    			each(arc,i,j);               //交换父子结点
    			i=j;
    		}
    		
    		
    	}
    
    	private void each(int[] arc, int i, int j) {    //两个结点交换
    		int t;
    
    		t = arc[i];
    		arc[i] = arc[j];
    		arc[j] = t;		
    	}

堆排序算法的几个特点：

1.时间复杂度为O（nlogn）;

2.不稳定

3.适用于大量数据选出小于k（k>0）的元素

## 2、归并排序 ##

归并排序思想：应用了分治思想，即不断的将大问题变小问题，通过解决小问题来解决整个大问题。

### 2.1自上而下的归并排序 ###

自上而下归并排序思想：不断地将无序数组用递归方法划分为两个数组，直到数组变的很小时（如划分到每个数组只有1个元素时）再进行两两归并，最后使得整个数组有序。

看看具体的代码

public void mergeSort(int arc[],int low,int hight){
    		int mid=low+(hight-low)/2;
    		if(low>=hight){            //递归的结束条件
    			return;
    		}
    		mergeSort(arc,low,mid);    //将数组划分为两个数组
    		mergeSort(arc,mid+1,hight);
    		merge(arc,low,mid,hight);   //将两个数组归并
    	}
    
    	private void merge(int[] arc, int low, int mid,int hight) {
    		
    		int a;
    		int i=low,j=mid+1;          //注意i=low,而不是i=0
    		for(int k=low;k<=hight;k++){//k=low,而不是k=0,k<=hight,而不是k<=arc.lenght-1
    			aux[k] = arc[k];        
    		}
    		for(a=low;a<=hight;a++)    //a=low,而不是a=0,a<=hight,而不是a<=arc.lenght-1
    		if(i>mid){                 //如第一个数组元素全部已经归并，则将第二个数组元素直接归并到arc[]
    			arc[a] = aux[j++];  
    		}else if(j>hight){         //如第二个数组元素全部已经归并，则将第一个数组元素直接归并到arc[]
    			arc[a] = aux[i++];
    		}else if(aux[i]<aux[j]){
    			arc[a] = aux[i++];
    		}else{
    			arc[a] = aux[j++];
    		}		
    	}

注：数组aux\[\]声明为全局变量，如果作为局部变量的话，在递归过程中会不断实例化新的数组，这样子会增加算法的空间复杂度

### 2.2自下而上的归并排序 ###

自下而上归并排序思想：直接将数组进行两两（每个数组为1个元素）归并，然后四四（每个数组为2个元素）归并，八八（每个数组为4个元素）归并，一直循环下去，直到将整个数组归并。

看看具体的代码

public void mergeSort2(int arc[]){
    		int N = arc.length;
    		int low;
    		for(int sz=1;sz<N;sz*=2){
    			for(int i=0;i<N;i+=2*sz){
    				low = i;
    				merge(arc,low,low+sz-1,Math.min(low+2*sz-1, N-1));
    			}
    		}				
    	}

注：之前一直对merge(arc,low,low+sz-1,Math.min(low+2\*sz-1, N-1));中的low+sz-1和low+2\*sz-1的“-1”难以理解，网上又找不到对它的解释，现在就将我的理解分享出来吧

（sz即为两两、四四、八八归并时的变量，这里不多解释）。假设a指向的元素和a左边的所有元素称为a拥有的元素，因此low+sz-1和low+2\*sz-1中的 “-1”是因为low和sz或者low和2\*sz拥有的元素中，low指向的那个元素重复了，既然重复那么就要-1。

归并排序算法的几个特点：

1.时间复杂度为O（nlogn）;

2.稳定

3.自上而下的归并排序需要创建辅助数组

## 3、快速排序 ##

快速排序的思想：找一个切点，将数组切分为两部分，小于切点的元素交换到切点的左边，大于切点的元素交换到切点的右边，并返回切点下标，再把切点左边和切点右边分别作为一个数组，递归下去，直到low>=high。

看看具体的代码

public void qSort(int arc[],int low,int high){
    		
    		if(low>=high){       //递归的结束条件
    			return;
    		}
    		int pivot = partiton(arc,low,high);  //返回切点
    		qSort(arc,low,pivot);           //将切点左边的数组作为整体递归
    		qSort(arc,pivot+1,high);        //将切点右边的数组作为整体递归
    		
    	}
    
    	private int partiton(int[] arc, int low, int high) {   //将数组切分为两部分，小于切点的元素交换到切点的左边，
    		                                                //  大于切点的元素交换到切点的右边，并返回切点下标
    		int pivotkey = arc[low];		    //默认数组的第一个元素为切点
    		while(low<high){			
    			while(low<high&&arc[high]>=pivotkey){
    				high--;
    			}
    			ench(arc,low,high);    //元素的交换
    			while(low<high&&arc[low]<=pivotkey){
    				low++;
    			}
    			ench(arc,low,high);
    		}		 
    		return low;  //注意返回的是下标而不是pivotkey
    		
    	}
    
    	private void ench(int[] arc, int low, int high) {   //元素的交换
    		
    		int t;
    		t = arc[low];
    		arc[low] = arc[high];
    		arc[high] = t;
    		
    	}

快速排序算法的几个特点：

1.时间复杂度为O（nlogn）;

2.不稳定

## 总结 ##

1.堆排序适用于大量数组选出小于k（k>0）的元素的应用，过程是不断向堆尾添加数据，使新添加的不断往上浮到合适位置，并把根结点（值最大）去掉，重新调整为大顶堆，不断循环，就可以找到小于k的元素。这样大量数据就需要一次性调入内存进行排序，而是调用一部分作为堆，并不断向堆添加数据和删除不符合条件的数据。

2.归并排序分为自上而下和自下而上两种，即递归和非递归。

3.虽然快速排序和归并排序的时间复杂度都一样（nlogn）,但是由于硬件原因，快速排序的平均速度要快于归并排序