排序算法笔记:快速排序 QuickSort in java
博客专区 > CheN_exe 的博客 > 博客详情
排序算法笔记:快速排序 QuickSort in java
CheN_exe 发表于4年前
排序算法笔记:快速排序 QuickSort in java
  • 发表于 4年前
  • 阅读 253
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

/**
 * 快速排序
 * 简述:
 * 		取array[high],将之前小于array[high]的数字置于array[high]之前,大于array[high]的置于array[high]之后,最后将array[high]放置于比它大的数字和比它小的数字之间.再利用递归重复之前的步骤至low < high为止.
 * 时间复杂度:
 * 		the best case: T(n)=T(n - 1)+Θ(n) = Θ(n^2)
 * 		the worst case: T(n)<=2T(n/2)+Θ(n)=Θ(nlgn)
 * 		average case: T(n)<=T(9n/10)+T(n/10)+cn=O(nlgn)
 * 空间复杂度:
 * 		O(logn)
 * 优点:
 * 		常见通用性较高的算法中,时间复杂度非常低的算法.推荐算法.
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 *
 */
public class QuickSort {
	public static int[] asc(int[] array) {
		quickSort(array, 0 , array.length - 1 );
		return array;
	}
	
	private static void quickSort(int[] array, int low , int high ){
		if( low < high ){
			int middle = getMiddle( array , low , high );
			quickSort( array , low , middle - 1 );
			quickSort( array , middle + 1 , high );
		}
	}
	
	private static int getMiddle(int[] array, int low , int high ){
		int x = array[high];
		for( int j = low ; j < high ; j++ ){
			if( array[j] <= x ){
				int temp = array[low];
				array[low] = array[j];
				array[j] = temp;
				low++;
			}
		}
		int temp = array[low];
		array[low] = array[high];
		array[high] = temp;
		return low;
	}
	
}


若有错误或不妥之处,敬请谅解并指点。

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