排序算法：归并排序、快速排序

落日映苍穹つ 2022-03-22 18:56 345阅读 0赞

相关博客：

[排序算法：冒泡排序、插入排序、选择排序、希尔排序][Link 1]

[排序算法：归并排序、快速排序][Link 2]

[排序算法：桶排序、计数排序、基数排序][Link 3]

[排序算法：堆排序][Link 4]

[十大排序算法小结][Link 5]

--------------------

# 一、归并排序： #

**1、工作原理：**

归并排序的采用分治思想，如果要排序一个数组，我们先把数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

**2、动图演示：**

![20181219185934258][]

**3、Java代码实现：**

public class MergeSort {
    	//归并排序：
    	public void mergeSort(int[] a,int p,int r){
    		//递归终止条件
    		if(p>=r) return;
    		
    		int q=(p+r)/2;//取数组的中间点
    		mergeSort(a,p,q);//对前半部分进行排序
    		mergeSort(a,q+1,r);//对后半部分进行排序
    		
    		merge(a, p, q, r);//合并前后两个部分
    	}
    	
            //merge()函数是归并排序的重点
    	public void merge(int[] a,int p,int q,int r){
    		//初始化变量：i表示前半部分的下标，j表示后半部分的下标，k表示临时数组的下标
    		int i=p;int j=q+1;int k=0;
    		int[] tmp = new int[r-p+1];
    		
    		while(i<=q && j<=r){
    			if(a[i]<=a[j]){
    				tmp[k++]=a[i++];
    			}else{
    				tmp[k++]=a[j++];
    			}
    		}
    		
    		//将剩余数据拷贝到临时数组中
    		for(;i<=q;i++) tmp[k++]=a[i];
    		for(;j<=r;j++) tmp[k++]=a[j];
    		
    		//将tmp临时数组拷贝回原数组
    		for(int x=0;x<r-p+1;x++) a[p+x]=tmp[x];
    	}
    }

**4、算法分析：**

（1）归并排序是一种稳定的排序算法；

（2）最好、最好、平均时间复杂度都是O(nlogn)。

（3）空间复杂度是O(n)，所以不是原地排序。这也是归并排序的一个致命弱点。

--------------------

# 二、快速排序： #

**1、工作原理：**

快速排序也是利用分治思想。如果要排序一组数据，我们先选择这组数据中任意一个数据作为分区点pivot，然后遍历这组数据，将小于分区点pivot的放到左边，大于分区点pivot的放到右边，将pivot放到中间。然后再分别对左右两部分进行排序。

**2、图片演示：**

![4d892c3a2e08a17f16097d07ea088a81.jpg][]

**3、Java代码实现：**

public class QuickSort {
    
    	public void quickSort(int[] a,int p,int r){
    		//递归终止条件：
    		if(p>=r) return;
    		
    		//获取分区点：
    		int q=partition(a,p,r);
    		quickSort(a,p,q-1);//对左分区进行排序
    		quickSort(a,q+1,r);//对右分区进行排序
    	}
    	
    	//返回分区点,快速排序的核心：
    	public int partition(int[] a,int p,int r){
    		
    		int i=p;int pivot = a[r];
    		for(int j=p;j<=r;j++){
    			if(a[j]<pivot){
    				swap(a,i,j);
    				i++;
    			}
    		}
    		swap(a, i, r);
    		return i;
    	}
    	
    	public void swap(int[] a,int x,int y){
    		int temp=a[x];
    		a[x]=a[y];
    		a[y]=temp;
    	}
    }

其中，快速排序的核心就是paitition()分区函数，它的过程如下图所示：

![086002d67995e4769473b3f50dd96de7.jpg][]

**4、算法分析：**

（1）快速排序是一种原地排序，空间复杂度为O(1)。

（2）快速排序是一种不稳定算法。

（3）快速排序是的最好时间复杂度、平均时间复杂度为O(nlogn)。但是在极端情况下，如果数组中的数据原来就是有序的，比如1,3,5,6,8，如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间就是不均等的，我们需要大约进行n次分区操作，才能完成快排的整个过程，每次分区我们平均要扫描大约n/2个元素，这时时间复杂度为O(n^2)，也就是最坏时间复杂度。

--------------------

**三、小结：归并与快排的区别：**

（1）归并排序和快速排序都是用分治的思想，代码都是通过递归来实现的，但是归并排序的核心是merge()合并函数，而快速排序的核心是partition()分区函数。归并排序的处理过程是从下到上，先处理子问题，然后再合并。而快速排序的处理过程正好相反，它的处理过程是从上到下的，先分区，然后再处理子问题。这两种排序的处理过程如下图所示：

![aa03ae570dace416127c9ccf9db8ac05.jpg][]

（2）归并排序算法是一种任何情况下时间复杂度都比较稳定的排序算法，时间复杂度都是O(nlogn)；快速排序算法最坏情况下时间复杂度为O(n^2)，但是平均时间复杂度都是O(nlogn)，不仅如此，快速排序时间复杂度退化到O(n^2)的概率非常小，我们可以通过合理选择pivot来避免这种情况。

（3）归并排序不是原地排序算法，空间复杂度比较高，为O(n)；快速排序是原地排序算法，空间复杂度为O(1)。

（4）归并排序是稳定的算法，快速排序不稳定。

[Link 1]: https://blog.csdn.net/a745233700/article/details/86683603
[Link 2]: https://blog.csdn.net/a745233700/article/details/86689225
[Link 3]: https://blog.csdn.net/a745233700/article/details/86693150
[Link 4]: https://blog.csdn.net/a745233700/article/details/86696956
[Link 5]: https://blog.csdn.net/a745233700/article/details/80794084
[20181219185934258]: /images/20220322/877e71b8b0da4fdfaefa622c2503b12b.png
[4d892c3a2e08a17f16097d07ea088a81.jpg]: /images/20220322/d0574ba56f5e44b19eab92afdb41dd81.png
[086002d67995e4769473b3f50dd96de7.jpg]: /images/20220322/e4a05482ba2a498196f8650a8106ac6b.png
[aa03ae570dace416127c9ccf9db8ac05.jpg]: /images/20220322/51b5d36fd8e542bd98660140b1e102da.png