排序算法——基于分治思想的排序

怼烎@ 2022-10-22 15:55 164阅读 0赞

### 文章目录 ###

*   *   *  快速排序
         *   *  取首元素为基准
             *  随机选取基准
             *  三数取中法
             *  性能测试
         *  归并排序
         *   *  递归实现
             *  非递归实现

**分而治之**是计算机领域非常常用的一种思想。在排序中，将数组拆分成不同的组，此为分，每组数据分别在各自组内进行排序，此为治。分治可以很好的利用多处理器的并行计算能力，提高排序效率。今天介绍两种基于分治思想的经典排序算法： **快速排序**和 **归并排序**。

### 快速排序 ###

快速排序的基本思路是，首先选取一个**基准值**，然后根据基准值，将数组拆分为左右两部分，使得基准值左侧的元素，都比基准值小，右侧的元素，都比基准值大。随后，对左右两部分数组进行同样的操作：选取基准值，做划分处理。一直分到不能再分，数组就整体有序了。每经过一轮排序，该轮基准元素的位置就会被确定下来。

图解如下

假设准备对如下数组进行快速排序

![790e9c5f3fb8c5735e35828f81a63fe8.png][]

先随机选取一个元素作为基准值，假设选中的是5

那么把数组分成大于5的部分，和小于5的部分，结果如下

橙色部分表示已被确定位置的基准值元素

![d540e58e3aabcc2f5d68b133a13cd39d.png][]

随后对5左侧，5右侧的部分，做同样的操作

假设被标记为蓝色的元素是被选中的基准值

![7ed777b296d56991b7da67c9badbd96a.png][]

根据基准值，将各自部分的元素，分成左右两部分，结果如下

![40d92d0d8c5cc9fd2333e62cf518c34c.png][]

右半边，由于没有比基准值6小的元素，故只存在右半部分

继续拆分，假设蓝色的元素为被选中的基准值

![3f568426efa3c0bb19f1149a754bc334.png][]

进行拆分，得到

![bf12c38fdbba974ed3ffe94710ef6415.png][]

![e5a5145c175b42a5fa8d5badd250fe7e.png][]

已经拆到不能再分，整个数组有序

用大白话来讲，就是每轮选取一个基准值，用基准值将数组切成两半，左半边是较小的元素，右半边是较大的元素，一直切分到左右半边不能再切，就完成排序。即，一分为二，二分为四，四分为八。一分为二之后，左右两部分的排序互不影响，故可以利用多处理器的资源，进行并行运算，二分为四同理。此为**分而治之**。所以快排可以很好的利用多处理器资源，利用并行计算来提高排序效率。

当然，基准值的选取对快排非常重要，若选择了糟糕的基准值。无法将数组较好地平均分为左右两部分，则快排的效率会急剧下降。

最坏的情况是，每轮排序都选取了当前数组部分的最值，使得划分的结果，只存在右半部分或左半部分，此时的快速排序便退化成了冒泡排序。

常见的基准选取方式包括：

*  取第一个元素
 *  随机选取
 *  三数取中

若数组已经有序，并且每次是选取第一个元素作为基准，那么此时快排的效率是极其糟糕的。故一般会随机选取一个元素作为基准。而三数取中法，则是取左端，中间，右端三个数，对这三个数进行排序后，取中间位置的数作为基准，以期待能够较为平均地将数组分为左右两部分。

来看一看快排的实现思路，以最简单的基准选取方式——取第一个元素作为基准，来进行讲解

#### 取首元素为基准 ####

首先选取当前数组第一个元素作为基准

![78c8837bc860a5c4b7d8e95e8ca0484d.png][]

随后，根据基准来切分数组。切分数组主要还是基于**比较和交换**，这里的**切分思路有两种**，一种是**双边循环**，即使用左右两个指针，从左右两端往中间走，交替与基准值进行比较并交换；还有一种是**单边循环**，单向地从左往右逐渐扩大左侧部分的边界。单边循环的实现更易理解，并且代码更简洁。故采用单边循环的方式来进行图示讲解。

定义一个标志变量mark，用于标记左侧部分的边界，mark的初始位置为基准元素的位置，另外定义一个指针pos，用于从左往右进行遍历，这个指针的初始位置在mark的后一个位置，如图所示

![51294c38ca6510e7b9746a35a106f29f.png][]

接着，比较pos所指向的元素与基准值的大小，若其比基准值大，则将pos右移一位，继续下一轮比较；若其比基准值小，则先将mark加1，并交换pos和mark指向的两个元素，后将pos右移一位，继续下一轮比较。

用大白话讲，就是，pos指针从左依次往右移动，遍历整个数组，只要发现了比基准值小的，就将其交换到最左侧，并扩大左侧部分的边界（mark值增大），相当于不断地把小于基准的元素交换并堆积到左侧。当pos遍历完整个数组后，将基准值和mark指向的元素进行交换，即完成数组的切分。

各个步骤的图解如下：

第一轮，pos指向2，发现2小于基准值4，则先将mark+1，后交换mark和pos所指向的元素

![143c838f402cd5d99c221087098642ea.png][]

然后pos往后移动一位，继续处理下一个元素

![cacd94068eb0827aa6be27fa789f9089.png][]

第二轮，pos指向8，8大于基准值4，则该轮直接结束。继续右移pos

![db7d3930d38ec975ee2ebdd471daf16b.png][]

第三轮，pos指向5，5大于基准值4，继续右移pos

![ebcb9c5bf7c608be063cc2441ec292aa.png][]

第四轮，pos指向7，7大于基准值4，继续右移pos

![14c73241df43acaf928bc827d293c985.png][]

第五轮，pos指向1，1小于基准值4，则mark+1，并交换pos和mark

![68b837568bb37a6ee47c53d1a691412a.png][]

![a79dc33622ac0e74fa603b312adc2647.png][]

继续右移pos

![c1978baefc1a57adda0272a66d0c369c.png][]

第六轮，pos指向3，3小于基准值4，则mark+1，交换mark和pos

![6b8756c48604147e6b67f44780f31875.png][]

![563f0ac632bac6dec26dbb7e4a6ccd86.png][]

继续右移pos

![be6b46d8118a6c0dc1b6edca16ab25ad.png][]

第七轮，pos指向9，9大于基准值4，继续右移pos

![b9673dc307106d19c987d0c58ead4545.png][]

第八轮，pos指向6，6大于基准值4，继续右移pos。

遍历完毕，最后交换mark和基准值4

![630b9f83af5d9211a0af8ee7fa366508.png][]

第一趟排序完毕，根据基准值4成功将数组切分成了左侧小于4的部分，和右侧大于4的部分。

接下来只需要将左右两部分数组看成独立的数组，重复上面的过程，直到数组被切分到不能再分，即完成排序，可以考虑用递归来实现，代码如下

public void quickSort(int[] array) { 
    		quickSortInternal(array, 0, array.length - 1);
    	}
    
    	/** * 对指定部分的数组进行快速排序 * **/
    	private void quickSortInternal(int[] array,int left, int right) { 
    		/* 递归退出条件 */
    		if (left >= right) { 
    			return ;
    		}
    		//取第一个位置作为基准
    		int pivot = array[left];
    		int mark = left;
    		int pos = mark + 1;
    		/* */
    		while (pos <= right) { 
    			if (array[pos] < pivot) { 
    				swap(array, ++mark, pos);
    			}
    			pos++;
    		}
    		swap(array, left, mark);
    		/* 该轮排序结束, 对左右部分进行相同操作, 采用递归方式 */
    		quickSortInternal(array, left, mark - 1);
    		quickSortInternal(array, mark + 1, right);
    	}

#### 随机选取基准 ####

由于选取第一个元素作为基准，很容易造成数组切分不均匀，故进行优化，改用随机选取一个元素，代码和上面大同小异

public void quickSort(int[] array) { 
    		quickSortInternal(array, 0, array.length - 1);
    	}
    
    	/** * 对指定部分的数组进行快速排序 * **/
    	private void quickSortInternal(int[] array,int left, int right) { 
    		/* 递归退出条件 */
    		if (left >= right) { 
    			return ;
    		}
    		//随机选取一个元素作为基准，并和第一个元素交换
            
            //从left到right之间，随机选取一个位置
            int pivotPos = (new Random()).nextInt(right - left) + left + 1;
            //将被选中的基准元素换到第一个位置
            swap(array, pivotPos, left);
            
    		int pivot = array[left];
    		int mark = left;
    		int pos = mark + 1;
    		/* */
    		while (pos <= right) { 
    			if (array[pos] < pivot) { 
    				swap(array, ++mark, pos);
    			}
    			pos++;
    		}
    		swap(array, left, mark);
    		/* 该轮排序结束, 对左右部分进行相同操作, 采用递归方式 */
    		quickSortInternal(array, left, mark - 1);
    		quickSortInternal(array, mark + 1, right);
    	}

#### 三数取中法 ####

随机选取基准元素的方式仍然不够好，我们考虑用**三数取中**的方法来进行优化，选取基准元素时，先取左端，中间，右端3个元素，取大小排在3个元素的中间的那一个，作为基准，将其交换到数组的首位，后续步骤与前面所述完全一致，来看一下代码实现

public void quickSort(int[] array) { 
    		quickSortInternal(array, 0, array.length - 1);
    	}
    
    	/** * 对指定部分的数组进行快速排序 * **/
    	private void quickSortInternal(int[] array,int left, int right) { 
    		/* 递归退出条件 */
    		if (left >= right) { 
    			return ;
    		}
    		//用三数取中法选取一个元素作为基准，并和第一个元素交换
            
            //根据三数取中，获取基准元素的下标
            int pivotPos = getMidPos(array, left, right);
            //将被选中的基准元素换到第一个位置
            swap(array, pivotPos, left);
            
    		int pivot = array[left];
    		int mark = left;
    		int pos = mark + 1;
    		/* */
    		while (pos <= right) { 
    			if (array[pos] < pivot) { 
    				swap(array, ++mark, pos);
    			}
    			pos++;
    		}
    		swap(array, left, mark);
    		/* 该轮排序结束, 对左右部分进行相同操作, 采用递归方式 */
    		quickSortInternal(array, left, mark - 1);
    		quickSortInternal(array, mark + 1, right);
    	}
    	/** * 对左中右，三个数，进行排序，并返回中间位置的数的下标 * **/
    	private int getMidPos(int[] array, int left, int right) { 
    		int mid = (left + right) >>> 1;
    		int[] pos = { left, mid, right};
    		for (int i = 1; i < pos.length; i++) { 
    			int j = i;
    			while (j - 1 >= 0 && array[pos[j]] < array[pos[j - 1]]) { 
    				swap(array, pos[j], pos[j - 1]);
    				j--;
    			}
    		}
    		return mid;
    	}

#### 性能测试 ####

当测试数组的规模很大时，采用递归实现的快速排序，会出现StackOverflow异常，故改用非递归实现，进行测试，非递归实现的思路需要引入一个栈，用其来存储每一轮排序的起始位置和终止位置，下面给出选取首元素为基准的非递归代码实现，其余基准选取方式类似

public void quickSort(int[] array) { 
    		quickSortInternal(array, 0, array.length - 1);
    	}
    
    	/** * 对指定部分的数组进行快速排序 * **/
    	private void quickSortInternal(int[] array,int left, int right) { 
            //用Deque来模拟栈
    		Deque<Pair<Integer,Integer>> stack = new LinkedList<>();
    		stack.push(new Pair<>(left, right));
            //当栈非空时，执行循环
    		while (!stack.isEmpty()) { 
                //弹出栈顶元素，获取该轮排序的起止位置
    			Pair<Integer, Integer> pop = stack.pop();
    			int l = pop.getLeft();
    			int r = pop.getRight();
    			if (l >= r) { 
    				continue;
    			}
    			//取第一个位置作为基准
    			int pivot = array[l];
    			int mark = l;
    			int pos = mark + 1;
    			/* */
    			while (pos <= r) { 
    				if (array[pos] < pivot) { 
    					swap(array, ++mark, pos);
    				}
    				pos++;
    			}
    			swap(array, l, mark);
    			/* 该轮排序结束, 对左右部分进行相同操作, 采用非递归方式 */
    			stack.push(new Pair<>(l, mark - 1));
    			stack.push(new Pair<>(mark + 1, r));
    		}
    	}
    
    //其中用了一个自定义的类 Pair
    public class Pair<L,R> { 
    
    		private L left;
    
    		private R right;
    
    		public Pair(L left, R right) { 
    			this.left = left;
    			this.right = right;
    		}
    
    		public L getLeft() { 
    			return left;
    		}
    
    		public R getRight() { 
    			return right;
    		}
    }

性能测试的结果如下面折线图所示

![63bdbbf9cbba6b4d0458177de4d24451.png][]

可见选取首元素为基准的，性能要明显差于随机选取法，和三数取中法。上图由于选取首元素的耗时太长，无法看出随机选取法和三数取中法的性能差异，故单独对二者进行性能测试，绘制折线图如下

![f792c56ccd8ab1031cad13135e992763.png][]

可见三数取中法的性能要略优于随机选取法

### 归并排序 ###

归并排序是一种建立在归并操作上的排序算法，它是典型的**分而治之**思想的体现。其基本思路是，先对**待排序数组**进行分区，比如一个大小为8的数组，先对它进行分区，一分为二，二分为四，四分为八

![ba8f2803c1286799a639b523024bd58a.png][]

![54fefa565cbb5c72e2ac84c2a7d39d69.png][]

当已经分到不能再分（分区只有一个元素），我们可以认为这个分区是有序的。随后便可以对分区进行两两合并

![095a8350c4f27b7c81aaeeab0cad5a63.png][]

随后，每个分区变为了2个元素，且各个分区内部都是有序的，我们便可以对相邻分区再次进行两两合并

![07fc18b245bec481d8bb3c9a7695e10e.png][]

随后，每个分区变为了4个元素，且各个分区内部都是有序的，再次对相邻分区进行合并

![84b07996b25b38c210a2604dd0be7a19.png][]

只有1个分区，排序结束，数组整体有序

归并排序的代码实现有2种方式：递归实现，非递归实现

先来说代码逻辑较为简单的递归实现：先将数组平均分为左右两个部分，然后对左右两部分数组，递归调用归并排序算法，逻辑上可简单理解为，先把左右两个分区排好序，然后再对左右两个有序分区进行合并操作。关于分区合并的图解说明如下

左半分区的数组下标范围是\[left, mid\]，右半分区的下标范围是\[mid + 1, right\]

先定义2个指针，分别指向2个分区的第一个位置

![6d4e88f1f1a68d617b9dab007d5341e1.png][]

比较posL和posR指向的元素，将较小者拿出来，放到另一个辅助数组中，第一轮被拿出来的是posL指向的1

![e00af496c529bd09c0c566a24981d5c5.png][]

随后posL右移一位，继续比较posL和posR

![fa32c9cf5270bcd5d091b4dd6a1cf5fc.png][]

发现2小于5，则将2拿出来，放到下面数组，posL继续右移

![08792ec703e4b2817e48b2e5969076d6.png][]

发现4小于5，将4放到下面数组，posL继续右移

![8c787dd813263758d6d293451a8ea70e.png][]

发现5小于7，将5放到下面数组，posR右移

![fa73df1537e2172b7b1d0eef269caeac.png][]

发现6小于7，将6放到下面数组，继续右移posR

![3a99230621f9033311092d40903066da.png][]

发现7小于8，将7放到下面数组，右移posL

![f9e93372664ab5d1dd57aa8b33927efb.png][]

发现posL已经超出左半部分的边界mid，即左半分区元素已经全部插入完毕，则只需要将右半分区的剩余元素，挨个插入到下方数组即可，posR当前指向8，则挨个插入8和9

![3db36ceea30275b0efdc5069ba5c615d.png][]

如此，便完成一趟归并，成功将2个有序分区合并成1个有序分区

#### 递归实现 ####

代码如下

public void mergeSort(int[] array) { 
    		int[] arrayCopy = new int[array.length];
    		mergeSort(array, 0, array.length - 1, arrayCopy);
    	}
    
    	private void mergeSortInternal(int[] array, int left, int right, int[] arrayCopy) { 
    		//递归退出条件
            if (left >= right) { 
    			return ;
    		}
            //取中间位置
    		int mid = (left + right) >>> 1;
    		//递归调用，逻辑上立即为，先让左右分区的元素排好序
    		mergeSortInternal(array, left, mid, arrayCopy);
    		mergeSortInternal(array, mid + 1, right, arrayCopy);
    		//开始对左右两个有序分区进行合并
    		int posL = left, posR = mid + 1;
    		int i = left;
    		while (posL <= mid && posR <= right) { 
    			if (array[posL] < array[posR]) { 
    				arrayCopy[i++] = array[posL++];
    			} else { 
    				arrayCopy[i++] = array[posR++];
    			}
    		}
    		//若右半部分元素用完了，则左半部分依次插入
    		while (posL <= mid) { 
    			arrayCopy[i++] = array[posL++];
    		}
            //若左半部分元素用完了，则右半部分依次插入
    		while (posR <= right) { 
    			arrayCopy[i++] = array[posR++];
    		}
    		//将该次归并的结果，写回到原数组
    		for (int j = left; j <= right; j++) { 
    			array[j] = arrayCopy[j];
    		}
    	}

注意到归并排序，在对分区进行合并时，需要一个额外的数组来暂存合并的结果

递归实现的思想比较简单，注意到，递归调用到最深处，也是从大小为1的分区开始两两合并，2个大小为1的分区，合并为1个大小为2的分区，2个大小为2的分区，合并为1个大小为4的分区…

#### 非递归实现 ####

下面介绍非递归的实现

我们可以发现，归并总是从大小为1的分区开始进行的，则可以这样考虑。我们用分区大小作为循环变量，先从分区大小为1开始，执行相邻分区两两合并，再将分区大小变为2，执行合并，再将分区大小变为4，执行合并…写成代码如下

public void mergeSortNonRecursive(int[] array) { 
    		int[] temp = new int[array.length];
    		for (int blockSize = 1; blockSize <= array.length; blockSize *= 2) { 
    			for (int i = 0; i < array.length; i += 2 * blockSize) { 
    				//对当前区块进行合并
    				int left = i;
    				int mid = (i + blockSize) < array.length ? (i + blockSize) : array.length;
    				int right = (i + 2 * blockSize) < array.length ? (i + 2 * blockSize) : array.length;
    				int posL = left, posR = mid;
    				int k = left;
    				while (posL < mid && posR < right) { 
    					if (array[posL] < array[posR]) { 
    						temp[k++] = array[posL++];
    					} else { 
    						temp[k++] = array[posR++];
    					}
    				}
    				while (posL < mid) { 
    					temp[k++] = array[posL++];
    				}
    				while (posR < right) { 
    					temp[k++] = array[posR++];
    				}
    			}
    			//一轮结束，整个数组进行了一趟归并
                //准备扩大区块的大小，进行下一趟归并
    			//交换2个数组,进行下一轮排序
    			int[] p = array;
    			array = temp;
    			temp = p;
    		}
    	}

[790e9c5f3fb8c5735e35828f81a63fe8.png]: /images/20221022/5b1ee8cd740241e9934f35b08229dd08.png
[d540e58e3aabcc2f5d68b133a13cd39d.png]: /images/20221022/774c07debdc04350b07be3c4c616402a.png
[7ed777b296d56991b7da67c9badbd96a.png]: /images/20221022/56959d7bdc9c4ebc855d3354ce1a6746.png
[40d92d0d8c5cc9fd2333e62cf518c34c.png]: /images/20221022/8aa67ff19b074533b6eef965807b81e3.png
[3f568426efa3c0bb19f1149a754bc334.png]: /images/20221022/7e60de8e02ed47d394ff58c92dd92548.png
[bf12c38fdbba974ed3ffe94710ef6415.png]: /images/20221022/a7aac2ecceca46d68d688e5cb8a4cfc7.png
[e5a5145c175b42a5fa8d5badd250fe7e.png]: /images/20221022/e8481a73096a4f89b186d7aec2ff9053.png
[78c8837bc860a5c4b7d8e95e8ca0484d.png]: /images/20221022/e644d55392624544a308ebe936c5ba68.png
[51294c38ca6510e7b9746a35a106f29f.png]: /images/20221022/add84f97d08e442e98a4ff754b773e02.png
[143c838f402cd5d99c221087098642ea.png]: /images/20221022/d16a98afed464404b0868becd19cc334.png
[cacd94068eb0827aa6be27fa789f9089.png]: /images/20221022/370acee628c4489cbbf738820af106bb.png
[db7d3930d38ec975ee2ebdd471daf16b.png]: /images/20221022/13b8bc83bbbc4460be5d0f2ec8d44d1a.png
[ebcb9c5bf7c608be063cc2441ec292aa.png]: /images/20221022/708a2668bdab409aa4bdc09a906283ff.png
[14c73241df43acaf928bc827d293c985.png]: /images/20221022/b269240bd33346299988fee13374e7d8.png
[68b837568bb37a6ee47c53d1a691412a.png]: /images/20221022/55b0dbca644044d794139c52e9160d8c.png
[a79dc33622ac0e74fa603b312adc2647.png]: /images/20221022/e28665aee9134b26997b1e5c90c1fc2a.png
[c1978baefc1a57adda0272a66d0c369c.png]: /images/20221022/3a585899a3d144a280a52db36eecbb35.png
[6b8756c48604147e6b67f44780f31875.png]: /images/20221022/847f884c9fa549e585be8474b0f3fe1f.png
[563f0ac632bac6dec26dbb7e4a6ccd86.png]: /images/20221022/f6e63703e1224edfa2e590b92b3c84be.png
[be6b46d8118a6c0dc1b6edca16ab25ad.png]: /images/20221022/4e94b63b6922427883a76f878200c8d8.png
[b9673dc307106d19c987d0c58ead4545.png]: /images/20221022/2b9f19b099434112a7162e173d6c9033.png
[630b9f83af5d9211a0af8ee7fa366508.png]: /images/20221022/2307c4a05c74458093f8721d863af8ef.png
[63bdbbf9cbba6b4d0458177de4d24451.png]: /images/20221022/03ad9a6d42f34d74b8f31165f9fa7cbf.png
[f792c56ccd8ab1031cad13135e992763.png]: /images/20221022/2c2ddbde8f2e4b27b9524b910cc5fd02.png
[ba8f2803c1286799a639b523024bd58a.png]: /images/20221022/5cb04ed41d8941e5bb5e785b2559a96f.png
[54fefa565cbb5c72e2ac84c2a7d39d69.png]: /images/20221022/1e38d6a8e8884e4ba0c942376b0d13cb.png
[095a8350c4f27b7c81aaeeab0cad5a63.png]: /images/20221022/8d83e061a6074e8296ca164d76ca3997.png
[07fc18b245bec481d8bb3c9a7695e10e.png]: /images/20221022/fd693a8a812346d3be0c62f397ada9ea.png
[84b07996b25b38c210a2604dd0be7a19.png]: /images/20221022/483dcd01a459431c90720614a5363e25.png
[6d4e88f1f1a68d617b9dab007d5341e1.png]: /images/20221022/3f483b6fa533417187c98f393306f474.png
[e00af496c529bd09c0c566a24981d5c5.png]: /images/20221022/551dc3378eea4c189d0665d7016463d5.png
[fa32c9cf5270bcd5d091b4dd6a1cf5fc.png]: /images/20221022/fc1e773884ef4313b2563bf2238da420.png
[08792ec703e4b2817e48b2e5969076d6.png]: /images/20221022/bd270d790f4f45c89dc59891d007abd4.png
[8c787dd813263758d6d293451a8ea70e.png]: /images/20221022/dd72fc2e36414bf58d0eb2eb473ddde7.png
[fa73df1537e2172b7b1d0eef269caeac.png]: /images/20221022/915fba702f1b4b98ab5ab6d5c8027bc9.png
[3a99230621f9033311092d40903066da.png]: /images/20221022/22b7e25e0e984238aa3a23ebb1daa5be.png
[f9e93372664ab5d1dd57aa8b33927efb.png]: /images/20221022/7e2dca761efc44188067136828172583.png
[3db36ceea30275b0efdc5069ba5c615d.png]: /images/20221022/941769d5fb0c4c7da188ebe925fc2e2d.png