快速排序

2015年11月19日11:31:12 发表评论 4 views
  • 背景介绍: 又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来 ----- 来自 wikipedia**
  • 算法规则: 本质来说,快速排序的过程就是不断地将无序元素集递归分割,一直到所有的分区只包含一个元素为止。
    由于快速排序是一种分治算法,我们可以用分治思想将快排分为三个步骤:
    1.分:设定一个分割值,并根据它将数据分为两部分
    2.治:分别在两部分用递归的方式,继续使用快速排序法
    3.合:对分割的部分排序直到完成
  • 代码实现(Java版本)
        public int dividerAndChange(int[] args, int start, int end) 
        {   
            //标准值
        	int pivot = args[start];
    		while (start < end) {
    			// 从右向左寻找,一直找到比参照值还小的数值,进行替换
    			// 这里要注意,循环条件必须是 当后面的数 小于 参照值的时候
    			// 我们才跳出这一层循环
    			while (start < end && args[end] >= pivot)
    				end--;
    
    			if (start < end) {
    				swap(args, start, end);
    				start++;
    			}
    			// 从左向右寻找,一直找到比参照值还大的数组,进行替换
    			while (start < end && args[start] < pivot)
    				start++;
    			if (start < end) {
    				swap(args, end, start);
    				end--;
    			}
    		}
    		args[start] = pivot;
    		return start;
    	}
    	public void sort(int[] args, int start, int end) 
        {
    		//当分治的元素大于1个的时候,才有意义
    		if ( end - start > 1) {
                int mid = 0;
    			mid = dividerAndChange(args, start, end);
    			// 对左部分排序
    			sort(args, start, mid);
    			// 对右部分排序
    			sort(args, mid + 1, end);
    		}
    	}
    	private void swap(int[] args, int fromIndex, int toIndex) 
        {
    		args[fromIndex] = args[toIndex];
    	}
  • yiisaa
  • 这是我的微信扫一扫
  • weinxin
  • zhengweiqiangcom
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: