算法-快速排序

硅谷探秘者 3021 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);
	}
}


猜你喜欢
数据结构与算法 3381 流程--来自百度百科首先设定一个分界值,通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分
数据结构与算法 905 思想将待集合以该集合中随机的一个数为分界点分成左右两个集合,一次使其右边的集合的数据全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述操作,直到递归集合没有数据,递归结束完
数据结构与算法 4795 十种理解(前五)1.冒泡冒泡是一种简单的。它重复地走访过要的数列,一次比较两个元素,如果它们的顺错误就把它们交换过来。描述:比较相邻的元素。如果第一个比第二个大,就
数据结构与算法 713 思想:把所有需要的数据分成两个集合,一个是待集合,一个是已的集合,每次从未集合顺或随机拿取一个数据,把它加入到已集合使其有,直到未集合中的数据被取走完,结束
数据结构与算法 753 思想:希尔是插入的增强版,其主要的思想还是插入的思想。描述:在插入的基础上,对待数组进行间隔为inc的分组,然后对每个分组进行直接插入,一次完成后,减小inc
数据结构与算法 4275 (英语:Heapsort)是指利用堆这种数据结构所设计的一种。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
数据结构与算法 823 思想该使用递归实现,思路为:每次递归将待数组在中间位置分成左右两组,分别对左右两个数组进行归并,递归的条件是数组长度必须大于等于3,所以当数组中只有两个数据的时候可以直接进行比较
数据结构与算法 780 思想:对冒泡的一种改进,每次从没有的集合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月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。