当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

快速排序思想及其算法实现

发表于: 2013-10-23   作者:come_for_dream   来源:转载   浏览次数:
摘要:                            快速排序思想及其算法实现     快速排序(Quicksor

                           快速排序思想及其算法实现

 

 

快速排序(Quicksort)是对冒泡排序的一种改进。O(N*logN)的算法复杂度使它得到了广泛的应用。

算法的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中的一部分的所有数据都比另一部分都要小,然后按此方法分别对这两部分再分别进行快速排序,这呢哥哥排序过程可以递归处理。

<!--EndFragment-->

以此达到整个数据变成有序序列。

 

算法的过程为:

1.制定杻轴(一般是第一个元素)

2.通过一趟排序将一杻轴为中心,把待排记录分割成独立的两部分,使得左边的记录的关键字小于杻轴值,右边的记录大于杻轴值

3.对左右两部分记录序列重复上述过程,以此类推,直到子序列中只剩下一个记录或不含记录为止

 

 

对于

数据:25   21   65   2   35   7   5   43  

 

第一趟排序的结果:5   21   7   2   25     35   65   43  

第二趟排序的结果:  5   7   21   25   35   65   43 

第三趟排序的结果:2   5   7   21   25   35   65   43 

第四趟排序的结果:2   5   7   21   25   35   65   4

第五趟排序的结果:2   5   7   21   25   35   43   65

第六趟排序的结果:2   5   7   21   25   35   43   65

 

 

 

代码:

/**
	 * 快速排序
	 * 
	 * @param args
	 */

	public void quickSort(int a[], int left, int right) {
		int q;
		if (left < right) {

			q = partition(a, left, right);
			quickSort(a, left, q - 1);
			quickSort(a, q + 1, right);
			
			
		}

	}

	private int partition(int[] a, int left, int right) {
		int s;

		s = a[left];
	
		while (left <right){

			//向左判断
			while (a[right] > s) {
				right--;
			}
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				left++;
			}
			
			//向右判断
			while (a[left] < s) {
				left++;
			}
			//交换
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				right--;
			}			
			 
		
		}
		//打印数组
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "   ");		
		}
		System.out.println();


		return left;
	}

 

快速排序思想及其算法实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
快速排序本想在ubuntu下来写,用g++来编译的。无奈虚拟机里的版本太低,使用到一些库的时候都不行,
二、稍加优化的快速排序(pivot选取) 前面的代码基本实现了快速排序的思想,但是不够优化。对于已
三、再加优化的快速排序(改交换为替换) 前面的优化其实也不是怎么合理,在数据量小和数据分布非基
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 排序算法(So
排序算法是笔试和面试中最喜欢考到的内容,今晚花了好几个小时的时间把之前接触过的排序算法都重新
概括 排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序
快速排序(QuickSort) 1、算法思想  快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用
排序规则 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放
快速排序是对冒泡法排序的一种改进。 快速排序算法 的基本思想是:将所要进行排序的数分为左右两个
主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1],这两个算法尽管在9
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号