剑指offer——快速排序

        快速排序是目前所有排序中性能较好的一种算法,最好情况和平均情况下时间复杂度均为O(nlogn),最坏的情况下时间复杂度为O(n^2)。快速排序采用递归,用空间换取时间。由于使用了递归,因此需要额外的存储空间。

快速排序由三个函数构成,分别为QuickSort(int[] arr)、QuickSort(int[] arr,int start,int end)、partition(int[] arr,int start,int end)。其中partition函数能够从当前待排序序列中找出一个主元,并使得主元左侧的元素均小于主元,主元右侧的元素均大于主元。Partition函数完成对待排序序列的分割后,交给QuickSort(int[] arr,int start,int end)处理,QuickSort分别将被Partition分隔的两个子序列进行快速排序。QuickSort(int[] arr)是整个快速排序的入口函数,用户只需传入待排序数组即可。

下面为java实现的快速排序,若有bug欢迎拍版

/**
 * 实现快速排序 
 * @author chibozhou
 */
public class QuickSort {
	
	/**
	 * 本函数实现一趟快速排序,以数组的第一个元素为主元,
	 * 本函数运行结束后使得主元左侧的元素小于主元,主元右侧的元素大于主元。
	 * @param arr 待排序的数组
	 * @return 返回经一趟排序后主元的下标
	 */
	private static int partition(int[] arr,int start,int end){
		//健壮性判断
		if(arr.length<=0){
			System.out.println("数组为空!");
			return -1;
		}
		if(start<0 || end<0 || start>end){
			System.out.println("start、end非法!");
			return -1;
		}
		
		//i指向数组头、j指向数组尾
		int i=start+1,j=end;
		//选择数组第一位为主元
		int key = arr[start];
		//若i与j未相遇,则执行以下循环
		while(i<j){
			//i从左向右扫描,直到当前元素大于主元时停下
			while(arr[i]<=key && i<end){
				i++;
			}
			//j从右向左扫描,直到当前元素小于主元时停下
			while(arr[j]>=key && j>start){
				j--;
			}
			//i、j停下有两种情况:1.
			if(i<j)
				swap(arr,i,j);
		}
		//将主元与j交换
		swap(arr,start,j);
		System.out.println("某一趟排序结果:"+printArray(arr));
		//返回新的主元下标
		return j;
	}
	
	
	
	/**
	 * 快速排序入口函数
	 * @param arr 待排序数组
	 * @return 返回有序的数组
	 */
	public static void QuickSort(int[] arr){
		//健壮性判断
		if(arr==null || arr.length<=0){
			System.out.println("数组为空!");
			return;
		}
		
		//通过递归进行快速排序
		QuickSort(arr,0,arr.length-1);
	}
	
	
	
	/**
	 * 快速排序的递归函数
	 * @param arr 待排序数组
	 * @param start 数组的起始下标
	 * @param end 数组的结束下标
	 * @return 返回当前有序子序列
	 */
	private static void QuickSort(int[] arr,int start,int end){
		if(start<end){
			//获取主元
			int key = partition(arr,start,end);
			//对主元左侧的序列进行快速排序
			QuickSort(arr,start,key-1);
			//对主元右侧的序列进行快速排序
			QuickSort(arr,key+1,end);
		}
	}
	
	
	/**
	 * 实现i与j位置的元素交换
	 * @param arr 数组
	 * @param i 下标
	 * @param j 下标
	 */
	private static void swap(int[] arr,int i,int j){
		//健壮性判断
		if(arr==null || arr.length<=0){
			System.out.println("数组为空!");
			return;
		}
		
		//定义临时变量temp实现交换
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	
	
	/**
	 * 输出数组元素
	 * @param arr
	 * @return
	 */
	private static String printArray(int[] arr){
		if(arr==null){
			System.out.println("数组为空!");
			return null;
		}
		
		StringBuffer sb = new StringBuffer();
		for(int i=0;i<arr.length;i++){
			sb.append(arr[i]);
		}
		
		return sb.toString();
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

《常见排序算法》

1.概述 常见的排序算法,虽然很基础,但是很见功力,如果能思路清晰,很快写出来各个算法的代码实现,还是需要花一点功夫的,今天,就跟大家盘点下常用的一些算法。 冒...

1857
来自专栏超然的博客

ECMAScript 6 笔记(一)

       1996年11月,JavaScript的创造者Netscape公司,决定将JavaScript提交给国际标准化组织ECMA,希望这种语言能够成为国...

833
来自专栏向治洪

Koltin数据类之解构申明

所谓的解构声明就是将一个对象解构(destructure)为多个变量,也就是意味着一个解构声明会一次性创建多个变量.简单的来说,一个解构声明有两个动作: 声明了...

19610
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

1765
来自专栏PHP技术

新手快速学习ES6语法,用最快的速度入门ES6就看这里

最近正在学习ES6,对于ES6的语法有一些自己的理解,想写这篇文章帮助跟我一样的新手快速入门ES6而不至于连代码都看不懂.至于开发环境的搭建什么的例如balel...

1043
来自专栏海天一树

小朋友学C语言(27):选择排序

(一)基本原理(由小到大): 如果有n个数,需要比较n-1轮: 第1轮,将n个数中最小的数与a[0]对换,当然若a[0]就是最小的数则不用对换。 第2轮,将a[...

2888
来自专栏深度学习思考者

Python学习(三) 八大排序算法的实现(下)

本文Python实现了插入排序、基数排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的后面四种。 上篇:Python学习(三) 八大排序算...

23310
来自专栏Java3y

归并排序就这么简单

归并排序就这么简单 从前面已经讲解了冒泡排序、选择排序、插入排序,快速排序了,本章主要讲解的是归并排序,希望大家看完能够理解并手写出归并排序快速排序的代码,然后...

5227
来自专栏Java3y

希尔排序就这么简单

一、希尔排序介绍 来源百度百科: 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort...

3946
来自专栏向治洪

算法之冒泡排序

冒泡排序算法需要遍历几次数组。每次遍历都要比较连续相邻的元素,如果某一对相邻元素是降序,则互换它们的值,否则,保持不变。由于较小的值像“气泡”一样逐渐浮想顶部,...

1727

扫描关注云+社区