算法-快速排序

硅谷探秘者 2850 0 0

百科:

快速排序(Quicksort)是对冒泡排序的一种改进。

        快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列


java实现:

package sort.fast;

/**
 * 快速排序
 * @author jiajiajia
 *
 */
public class Fast {
	public static int a[],step=0,s=0;
	/**
	 * 递归函数
	 * @param left 数组左区间开始
	 * @param right 数组右区间结束
	 */
	public static void quicksort(int left, int right) {
		int i, j,temp;
		if(left > right)
			return;
	    temp = a[left]; //temp中存的就是基准数
	    i = left;
	    j = right;
	    while(i != j){ //两探针没有碰头
	    	while(a[j] >= temp && i < j)//顺序很重要,要先从右边开始找
	    		j--;
	    	while(a[i] <= temp && i < j)//再找右边的
	    		i++;       
	    	if(i < j){ //交换两个数在数组中的位置
	    		a[i] = a[i]+a[j];
	    		a[j] = a[i]-a[j];
	    		a[i] = a[i]-a[j];
	    	}
	    }
	    //最终将基准数归位
	    a[left] = a[i];
	    a[i] = temp;
	    s++;
		if(s>step) {//计算递归深度
			step=s;
		}
	    quicksort(left, i-1);//继续递归处理左区间数据
	    quicksort(i+1, right);//继续递归处理右区间数据
	    s--;
	}
	public static void main(String[] args) {
		a= new int[]{4,5,6,1,2,3,7,8,9,0};
		quicksort(0,a.length-1);
		
		for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
		
		System.out.println();
		System.out.println("递归深度:"+step);
	}
}


猜你喜欢
数据结构与算法 3220 流程--来自百度百科首先设定一个分界值,通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分
数据结构与算法 705 思想将待集合以该集合中随机的一个数为分界点分成左右两个集合,一次使其右边的集合的数据全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述操作,直到递归集合没有数据,递归结束完
数据结构与算法 4674 十种理解(前五)1.冒泡冒泡是一种简单的。它重复地走访过要的数列,一次比较两个元素,如果它们的顺错误就把它们交换过来。描述:比较相邻的元素。如果第一个比第二个大,就
数据结构与算法 596 思想:把所有需要的数据分成两个集合,一个是待集合,一个是已的集合,每次从未集合顺或随机拿取一个数据,把它加入到已集合使其有,直到未集合中的数据被取走完,结束
数据结构与算法 613 思想:希尔是插入的增强版,其主要的思想还是插入的思想。描述:在插入的基础上,对待数组进行间隔为inc的分组,然后对每个分组进行直接插入,一次完成后,减小inc
数据结构与算法 4131 (英语:Heapsort)是指利用堆这种数据结构所设计的一种。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
数据结构与算法 684 思想该使用递归实现,思路为:每次递归将待数组在中间位置分成左右两组,分别对左右两个数组进行归并,递归的条件是数组长度必须大于等于3,所以当数组中只有两个数据的时候可以直接进行比较
数据结构与算法 646 思想:对冒泡的一种改进,每次从没有的集合a中拿取一个最大或最小的元素,放入有的集合b中,直到a集合中的元素被取完描述:用变量i遍历整个数组,用变量j遍历i后面的数组,每次遍历i初始
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio
目录
祝愿神州十三飞行乘组平安归来