网站首页 文章专栏 【每周一算法】—— 排序算法之归并排序,快速排序
【每周一算法】—— 排序算法之归并排序,快速排序

排序算法之nlog(N)级别算法

1.归并排序

 原理 :主要思想为分治思想,分而治之,将数组分为两部分,对每一部分进行排序,再分为两部分对每部分排序,直到最后不可再分,也就是单独一个元素一部分,此时每个元素便不需要排序,因为本身便是有序的,只需要对其进行归并到上一级,上一级再归并到上上级,直到最上层,此时的数组便是有序的,归并排序是稳定的


性能:观察排序的过程可得知,如果我们数组有8个元素,那么分到最细粒度,也就是每个元素为一部分的时候,我们是分了3次,也就是log2(8),再看归并的过程,每次处理的数据是8条,如果我们的数组有n个元素,则排序的时间复杂度为nlog(N);分析归并的过程,怎么来归并呢,我们需要引入额外的相同长度的数组,对两个部分的对比,谁小谁放到额外的数组中,同时索引加一,所以它的空间复杂度为O(n)。


代码:

    /**
     * 归并排序 nlogn
     * @param arr:数组
     * @param length:数组长度
     */
    public static void mergeSort(int[] arr,int length){
    	__mergeSort(arr,0,length - 1);    // 开始调用递归函数
    }
    /**
     * 对arr[l,r]范围进行排序( 注意是前闭后闭的 )
     * @param arr:数组
     * @param l:左边界
     * @param r: 右边界
     */
    public static void __mergeSort(int[] arr,int l,int r){
    	if(l >= r){
    	    return;                             // 跳出递归的条件
    	}
    	int mid = (l + r)/2;                    // 计算中点位置
    	__mergeSort(arr,l,mid);                 // 对左部分继续递归分
    	__mergeSort(arr,mid + 1,r);        // 对右部分继续递归分
    	__merge(arr,l,mid,r);               // 归并两部分
    }
    /**
     * 对arr[l,mid] 和  arr[mid +1 ,r] 两部分进行归并
     * @param arr:数组
     * @param l :左索引
     * @param mid :中间索引
     * @param r:右边界
     */
    public static void __merge(int[] arr,int l,int mid,int r){
        int[] aux = new int[r - l + 1];
        for(int i = l;i <= r;i++){
    	    aux[i - l] = arr[i];
        }
    	
        int i = l;
        int j = mid + 1;
        for(int k = l;k <= r;k++){
          if(i > mid){
    	    arr[k] = aux[j - l];
    	    j++;
    	    }else if(j > r){
    	    arr[k] = aux[i - l];
    	    i++;
    	    }else{
    	      if(aux[i - l] < aux[j - l]){
    		    arr[k] = aux[i -l];
    		    i++;
    	      }else{
    		    arr[k] = aux[j -l];
    		    j++;
    	      }
    	    }
         }
    }

改进: 归并时判断 arr[mid] 值,如果此时的 arr[mid] 就是小于 arr[mid+1] 时,这种情况是不需要再归并的,因为此时已经是有序的,但是数组并非近乎有序时,if的判断也是需要耗时的,因此此优化建立在当数组近乎有序时。

        if(arr[mid] > arr[mid + 1]){		//如果是近乎有序的数组,可以这样优化
    	    __merge(arr,l,mid,r);
    	}

还有一种优化,当我们递归到一定数量级时,可以改用插入排序来提升性能,原因是,当数组很小时,插入排序更有优势。

        if(l >= r){
    	    return;                             // 跳出递归的条件
    	}
    	// 我们可以改成以下
    	if(r - l < 15){
    	    insertSort(arr,l,r);
    	    return;
    	}
    	
    	/**
    	 *    插入排序,对[l,r]区间的arr数组插入排序
    	 */
    	public void insertSort(int[] arr,int l,int r){
		    for(int i = l + 1; i <= r; i++){
			int e = arr[i];
			int j;
			for(j = i;j > l && arr[j - 1] > e;j--){
				arr[j] = arr[j - 1];
			}
			arr[j] = e;
	            }
		    return;
	        }

另一种写法:以上是递归的写法,自上而下,下面写一种自下而上,思想还是一样的。

    public static void mergeSortBU(int[] arr,int length){
    	for(int sz = 1;sz <= length;sz += sz){
    	    for(int i = 0;i + sz < length;i += sz + sz){
    	        __merge(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,length - 1));               // 还是调用相同的归并
    	    }
    	}
    }



2.快速排序

快速排序在排序界可算是大佬级别的,声名显赫,盛名之下,我们来看下其原理以及写法,再看看能不能优化下。

 原理 :不同于归并排序,上来就分两部分,快速排序是先取一个元素作为标准,想办法把他移动到排好序他应该所处的位置,这样该元素之前的都是小于他的,该元素后面的元素都是大于他的,对于分割的两部分,继续按照上述思路来递归分割。那么问题来了,怎么把该元素移动到排好序应该所处的位置呢?我们定义三个索引,j 记录边界,就是区分大于该元素,小于该元素的位置,i 记录遍历的当前元素,v是参照标准值,我们取第一个元素的值,那么先取得第一个待遍历的值(注意该值的索引起始为第二个元素),如果该值大于v,则继续遍历下一个,如果小于v,则将 j 记录的位置的下一个元素与i所处的值交换。


性能:观察排序的过程可得知,其思想也是分割数组,分治解决,当每次取出的标准值恰好为数组的中间值,其最优时间复杂度也是nlog(N),当每次取得参照标准为数组最小值时,其排序相当于冒泡排序了,最差时间复杂度为O(n2),我们可以通过随机化选择pivot来将空间复杂度降低到O(log2n),平均复杂度为nlog(n)。快速排序是不稳定的

在空间上:

     最优的情况下空间复杂度为:O(logn)  ;每一次都平分数组的情况

     最差的情况下空间复杂度为:O( n )      ;退化为冒泡排序的情况


代码:

    /**
     * 快速排序
     * @param arr:数组
     * @param length:数组长度
     */
    public static void quickSort(int[] arr,int length){
       	// 调用函数
       	__quickSort(arr,0,length - 1);   
    }
    /**
     * 对arr[l,r]部分进行快速排序
     * @param arr:数组
     * @param l:左边界
     * @param r:右边界
     */
    public static void __quickSort(int[] arr,int l,int r){
    	if(l >= r){
    	    return;   // 跳出递归条件
    	}
    	int p = __partition2(arr,l,r);    // 计算该元素应处的位置 p
    	__quickSort(arr,l,p-1);        // 继续递归对[arr,p-1]区间快速排序
    	__quickSort(arr,p+1,r);
    }
     /**
     * 对arr[l,r]部分进行partition操作,返回p,使得arr[l,p-1] < arr[p], arr[p+1] > arr[p]
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int __partition(int[] arr,int l,int r){
    	int v = arr[l];
    	int j = l;
    	for(int i = l + 1;i <= r; i++){
    		if(arr[i] < v){
    		    int temp = arr[j + 1];
    		    arr[j + 1] = arr[i];
    		    arr[i] = temp;
    		    j++;
    		}
    	}
    	int temp = arr[j];
    	arr[j] = arr[l];
    	arr[l] = temp;
    	return j;
    }

改进:

    (1):分析排序过程可知,影响算法时间复杂度的关键在于参照标准的选择,我们做出以下改进,使得将空间复杂度降低到O(log2n)。

        int temp1 = arr[l];
    	int index = new Random().nextInt(r - l + 1) + l;
    	arr[l] = arr[index];
    	arr[index] = temp1;

        上述代码加在__partition();函数的开始部分,目的是取得随机数,将第一位的值与随机索引位置的值调换。

    (2):假如有这样一个场景,我们需要排序10万的元素,而这10万个元素基本上都是重复的,比如都是1-10的整数,就算我们选择了5来作为参照标准,也很有可能造成两边的大小不一致,很有可能1-5之间存在9万条数据,6-10之间只有1万条,此时算法的复杂度又降低到O(n2)级别了。

        对于这种情况,我们可以采用从两侧同时扫描数组(双路快速排序),左边为i,右边为j,两边同时扫描,直到左边遇到一个大于等于v的元素,右边遇到一个小于等于v的元素,此时,交换i,j索引的位置,这样就算存在大量重复元素,我们也做了交换,最大程度让两边保持差不多的元素。

     public static int __partition2(int[] arr,int l,int r){
    	int temp1 = arr[l];
    	int index = new Random().nextInt(r - l + 1) + l;
    	arr[l] = arr[index];
    	arr[index] = temp1;
    	
    	int v = arr[l];
    	int i = l + 1;
    	int j = r;
    	while(true){
    		while(i <= r && arr[i] < v){
    		    i ++;
    		}
    		while(j >= l + 1 && arr[j] > v){
    		    j --;
    		}
    		if(i > j){
    		    break;
    		}
    		int temp2 = arr[j];
    		arr[j] = arr[i];
    		arr[i] = temp2;
    		i++;
    		j--;
    	}
    	int temp3 = arr[j];
		arr[j] = arr[l];
		arr[l] = temp3;
    	return j;
    }

    (3)当然也可以向归并排序一样,在递归到一定数量级后转用插入排序。


    (4)终极优化:在第二种改进后发现,当存在大量重复数据时,我们做了很多无用功,想一下,既然我们把数组分为小于等于标准值,大于等于标准值两部分,那么我们何不分为三部分呢,直接小于,等于,大于,三部分,只需要操作一次重复值。

9Z}Q6I0QJ]7]FLQF5`XSH80.png

    /**
     * 三路快速排序
     * @param arr
     * @return
     */
    public static void threeWaysQuickSort(int[] arr,int length) {
	__threeWaysQuickSort(arr,0,length - 1);
    }
    public static void __threeWaysQuickSort(int[] arr,int l,int r) {
	if(r - l < 15){
	    insertSort(arr, r,l);
        }
		
	int index = new Random().nextInt(r - l + 1) + l;
	int temp1 = arr[l];
    	arr[l] = arr[index];
    	arr[index] = temp1;
    	
    	int v = arr[l];
    	int lt = l;
    	int gt = r + 1;
    	int i = l + 1;
    	while(i < gt){
    		if(arr[i] < v){
    		    int temp2 = arr[lt + 1];
    		    arr[lt + 1] = arr[i];
    		    arr[i] = temp2;
    		    lt++;
    		    i++;
    		}else if(arr[i] < v){
    		    int temp3 = arr[gt - 1];
    		    arr[gt - 1] = arr[i];
    		    arr[i] = temp3;
    		    // 这里没有 i++操作,因为交换来的值仍旧需要考察
    		    gt--;		
    		}else{
    		    i++;
    		}
    	}
    	int temp4 = arr[lt];
    	arr[lt] = arr[l];
    	arr[l] = temp4;
    	
    	// 减一是因为arr[l] 与 arr[lt] 交换了,lt-1才是不包含v的范围
    	__threeWaysQuickSort(arr, l, lt - 1);	
    	__threeWaysQuickSort(arr, gt, r);
    }

总结提问:

        排序方式千变万化,很多种实现方式,包括还有堆排序,桶排序等等,重点在于搞懂其思想,而非流于形。

        根据以上排序思想提出两个问题以供大家思考:

        (1):求一个数组的逆序对个数,比如 8 9 4 7 2,其逆序对为84,87,82,94,97,92,42,72,用nlog(n)级别复杂度实现。

        (2):求一个数组的第n大元素,用O(n)级别复杂度实现。




版权声明:本文由星尘阁原创出品,转载请注明出处!

本文链接:http://www.52xingchen.cn/detail/37




赞助本站,网站的发展离不开你们的支持!
来说两句吧
最新评论