插入排序和迭代归并排序以及复杂度分析

港控/mmm° 2022-09-26 02:43 251阅读 0赞

引言： 算法是计算机科学中的基础，程序=算法+数据结构，算法描述了我们将如何来处理数据的过程。本文将介绍两种算法的实现以及其中一种算法的复杂度分析过程。

1.  算法介绍

归并排序是利用归并思想对数列进行排序，核心点是将数组进行分组拆分，拆分到最小单元之时，即为有序；然后进行分组数据的归并排序合并，从而达到排序的目的。

插入排序是将元素插入到某个有序数组之中，并保持原有数据的有序性，以此类推来解决数据排序的问题。

2. 算法实现

插入排序是在这里的实现是从有序数组的最后一个元素来进行比较和插入，当然这里也可以从第一个元素来进行比较和插入操作。

归并元素是基于2分法来进行分拆、排序归并的。

代码如下：

import java.util.Arrays;
    
    public class SortWays {
    
    	/**
    	 * direction:  
    	 * 
    	 * @param data
    	 * @param direction 0: ascendent, 1: descendent
    	 * @return
    	 */
    	public static int[] insertSort(int[] data, int direction) {
    		if (data == null || data.length == 0) return new int[]{};
    		
    		for (int j=1; j<data.length; j++) {
    			int key = data[j];
    			int i = j -1;
    			
    			while ((i>=0)) {
    				if ((data[i] > key) && (direction == 0)) {
    					   data[i+1] = data[i];
    				     i--;  //auto decrease
    				}
    				else if ((data[i]<key) &&(direction == 1)) {
    					data[i+1] = data[i];
    					i--;  //auto decrease
    				}
    				else {
    					break;
    				}
    			}
    			data[i+1] = key;
    		}
    		
    		return data;
    	}
    	
    	public static void mergeSort(int[] data, int startIndex, int endIndex) {
    		if (startIndex < endIndex) {
    			int splitIndex = (int)Math.floor((startIndex+endIndex)/2);
    			mergeSort(data, startIndex, splitIndex);
    			mergeSort(data, splitIndex+1, endIndex);
    			
    			merge(data, startIndex, splitIndex, endIndex);
    		}
    	}
    	
    	/**
    	 * merge method body.
    	 * 
    	 * @param data
    	 * @param startIndex
    	 * @param splitIndex
    	 * @param endIndex
    	 */
    	private static void merge(int[] data, int startIndex, int splitIndex, int endIndex) {
    		int[] tmp = new int[endIndex - startIndex+1]; //临时区域
    		
    		int i = startIndex; // first area index
    		int j = splitIndex +1; //second area index
    		int k = 0;    // temporary area index
    		
    		while (i<= splitIndex && j <= endIndex) {
    			//System.out.println("splitIndex/i/endIndx/j:" + splitIndex + "/" + i + "/" + endIndex + "/" + j);
    			
    			if (data[i] > data[j]) 
    				tmp[k++] = data[j++];
    			else 
    				tmp[k++] = data[i++];
    		}
    		
    		while (i<=splitIndex) {
    			tmp[k++] = data[i++];
    		}
    		
    		while(j<=endIndex) {
    			tmp[k++] = data[j++];
    		}
    		
    		for (int c=0; c<k; c++) 
    			data[startIndex+c] = tmp[c];
    		
    		tmp = null;
    	}
    	
    	public static void main(String[] args) {
    		int[] rawdata = new int[]{7,2, 3,  5, 1, 8, 4, 6};
    		
    		//int[] data = SortWays.insertSort(rawdata, 0);
    		
    		SortWays.mergeSort(rawdata, 0, rawdata.length-1);
    		System.out.println("Array Data:" + Arrays.toString(rawdata));
    	}
    
    }

在插入排序中， direction方向表示： 0为顺序排序，1： 降序排序。

在归并排序中，注意mergeSort的输入参数中最后一个参数为最后一个元素的位置，而非数组长度；比如这里实际的位置为7， 而非长度8.

3.  迭代归并排序的复杂度分析

关于插入排序的复杂度分析， 我们基于其伪代码实现来进行分析：

![Center][]

其运行的总时间为：

![Center 1][]

其在最坏情况下的总时间为：

![Center 2][]

总时间为 N\*N的正相关关系， 故其消耗时间为：

![Center 3][]

故这里的插入算法的复杂度为O(n\*n)，至于其他的n和常量都在复杂度的级别上进行忽略。

对于合并排序的算法复杂度分析，递归算法的时间复杂度公式为：

当n<<c,c为某个常量值之时，则问题规模足够小，可以直接求出其解所需时间，为O(1). T(n) = O（1）

其他情况下，

T(n) = aT(n/b) + D(n)＋Ｃ(n)

其中，a为分解的问题个数，T(n/b)为单个被分级的问题规模所需时间，二分法情况下为 a=b=2;但是大部分情况下，a并不等于b

D(n):将问题分解为子问题所需时间

C(n): 将子问题的解合并为原问题的解所需要的时间

对于归并排序的算法而言：

n = 1 ==> T(n) = O(1)= c \[c为常量，固定时间\]

n>1 => T(n)＝2T(n/2) + O(n) = 2T(n/2) + cn

\[c为常数， n为元素数量正相关的元素\]

我们将递归算法分解为以下图中所示的层次关系：

![Center 4][]

![Center 5][]

从上图可知，整个递归树的层次为lgn+1层，每层的时间消耗为cn，故整体的时间消耗为： cnlgn + cn = cn(lgn+1)  ~~~ O(nlgn)

故迭代归并的时间复杂度为 O(nlgn)

4.总结

对于各个算法的复杂度分析一般会分为最坏情况，最好情况和平均情况，在这里只是使用了最坏情况下的分析，这些数据方便我们了解各个算法在不同情况下的资源和时间消耗，这里并未涉及空间复杂度的讨论，主要是由于资源空间消耗不大，故没有讨论。

5. 参考资料

*    归并排序  http://www.cnblogs.com/skywang12345/p/3602369.html
 *    插入排序  http://blog.csdn.net/cjf\_iceking/article/details/7916194

[Center]: /images/20220717/ad3dfe9f4783401fa9310da1c6dc66fc.png
[Center 1]: /images/20220717/3dc35d8275f84b009a986e2ac951d10d.png
[Center 2]: /images/20220717/0bf875a23dc54a74ba21cd2acef36487.png
[Center 3]: /images/20220717/aae7bd272102472e94ea634136bf0632.png
[Center 4]: /images/20220717/810851b1ce0f478fb8ef7beb1e536493.png
[Center 5]: /images/20220717/3dd181f77e1c413b99895c9664b2eaa1.png