快速排序
博客专区 > JiaChang 的博客 > 博客详情
快速排序
JiaChang 发表于1年前
快速排序
  • 发表于 1年前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

快速排序

基本思路:从待排序的数据序列中任取一个数据(通常是第一个数据)作为分界值,所有比分界值小的元素一律放在分界值的左边,所有比分界值大的数据一律放在分界值的右边。经过这样一趟排序下来,待排序序列被分成左,右两个子序列,左边序列中的数据都比分界值小,右边序列中的数据都比分界值大。

接下来对左,右两个子序列进行递归,对两个子序列重新选择分界值并依次规则调整,直到每个子序列的元素只剩下一个,排序完成。

具体步骤

(1)选出指定的分界值(如第一个元素)

(2)定义一个 i 变量,i 变量从左边第一个索引开始,找大于分界值的元素的索引,并用 i 来记录它。

(3)定义一个 j 变量,j 变量从右边第一个索引开始,找小于分界值的元素的索引,并用 j 来记录它。

(4)如果 i < j ,则交换 i , j两个索引处的元素。

重复执行以上 2 ~ 4步,直到 i ≥ j,此时,j 左边的数据元素都小于分界值,j 右边的数据元素都大于分界值,最后将分界值和 j 索引处的元素交换即可。

因为经过一趟排序之后,分界值的位置在待排序的数据元素中的位置就已经确定下来了,所以继续分别递归分界值左边的子序列和右边的子序列,直至每个子序列的元素只剩一个,排序结束。

快速排序的实现:

	/***
	 * 对data数组中从start到end索引范围内的子虚列进行排序
	 * 使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
	 * @param data 待排序数组
	 * @param start 开始下标
	 * @param end 结束下标
	 */
	public static <E> void quickSort(int[] data,int start,int end){
		//需要排序
		if(start<end){
			//以第一个元素作为分界值
			int pivot = data[start];
			// i 从左边进行搜索,搜索大于分界值的元素的索引
			int i = start;
			// j 从右边进行搜索,搜索小于分界值的元素的索引
			int j = end+1;
			while(true){
				//找到第一个大于分界值的元素的索引,或者 i 已经到end处
				while(i < end && data[++i] <= pivot);
				//找到第一个小于分界值的元素的索引,或者 j 已经到start处
				while(j > start && data[--j] >= pivot);
				//需要交换
				if(i<j){
					//交换 i j 元素
					int temp = data[i];
					data[i] = data[j];
					data[j] = temp;
				}
				//不需要交换则结束循环
				else break;
			}
			//交换 j 和 start 处的元素, 此时 j 的在排序中位置已经固定
			int temp = data[start];
			data[start] = data[j];
			data[j] = temp;
			//交换完之后,接着递归 j 的左边子序列
			quickSort(data,start,j-1);
			//递归 j 的右边的子序列
			quickSort(data,j+1,end);
		}
	} 


测试代码: 

 

 

共有 人打赏支持
粉丝 3
博文 32
码字总数 18002
×
JiaChang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: