`
huntfor
  • 浏览: 194197 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

排序算法(1)之快速排序——java实现

 
阅读更多

题外话:

一般情况下,快速排序被认为是最快的排序算法(人如其名啊),因此可以说是最常用的排序算法,并受大多数公司的青睐,是一定要熟练掌握的。

 

简介:

快速排序是不稳定的,而且是中比较个性的排序

 算法——初始顺序越乱,排序效果越好,一般情况下,我们认为其时间复杂度为O(NlogN)当排序队列已经是顺序队列,时间复杂度达到最差O(n*n),具体是实现是用分治算法,因此涉及到栈,再因此,其空间复杂度略大,达到同样的O(NlogN),在这个效率为先的环境下,以牺牲些许空间换取更短的时间还是非常值得的。

 

算法思想:

快排采取了分治策略,也是分治算法的一个经典习题,因此其算法思想也符合分治算法,具体的思想是:

1.从数列中找到一个数

2.确定该数在队列中的位置,比它小的都放在左边,大的都在右边

3.将左右两部分分而治之。

 

伪代码如下:

void quickSort(int[] a, int begin, int end) {

	/*
	* 找到所选数字的位置,并记录下来该位置index
	*/
	
	quickSort(a, begin, i - 1);//对左边子问题进行排序
	quickSort(a, i + 1, end);//对右边子问题进行排序
	}

 

下一步,好了,算法框架已经搭好,剩下的问题就是,怎么找到所选数字的位置。

结合实例来详细介绍一下:

     ↓(i)                                                                                                                                                  ↓(j)

0 1 2 3 4 5 6 7 8 9 10 11
5 7 8 2 6 125 41 341 34 63 28 97

首先我们需要找到97在数列中的位置:

首先设左右两个指针,i 向左走,j 向右走,a[ i ] 遇到比97大的,就换到a[ j ]的位置,j-- (换 j 向左走)

                                                                        ↓i(换到 j 处)                                              ↓ j   ←    ↓ j

0 1 2 3 4 5 6 7 8 9 10 11
5 7 8 2 6 125 41 341 34 63 28 97

 

得:                                                                    ↓ i                                                                ↓ j

0 1 2 3 4 5 6 7 8 9 10 11
5 7 8 2 6   41 341 34 63 28 125

同理,a[j] 遇到比97小的,就换到a[ i ]的位置,i++

                                                                          ↓ i   →  ↓ i                                                       ↓ j

0 1 2 3 4 5 6 7 8 9 10 11
5 7 8 2 6  28 41 341 34 63   125

 

i、j分别向左走向右走,迟早会遇到。

当两个指针相遇,即i == j时,这样就能完成了比97小的,都被换到了左边,大的都被换到了右边。想不通的面壁去。因此 相遇的位置即97的位置。

 

PS:我们看到每当做一次交换,则换另一个指针走

 

这样每趟只需要做n次对比、操作,分治之后的树的高度是logN,因此时间复杂度为O(NlogN)

 好了,下面用代码实现:

	int i = begin;//记录两个指针的初始位置
	int j = end;
	int tem = a[end];//选择基数,可以随便选,一般选择端点,简单,安全
	boolean tag = true;//标记该哪个指针走,true表示 i 指针走
	while (i != j) {//如果两个指针没相遇,则一直循环下去
		if (tag) {//左边指针走
			if (a[i] < tem) {//如果不满足交换条件,就继续走
				i++;
				continue;
			} else {//满足交换条件,将大数换到右边
				a[j] = a[i];
				j--;//该句可以略去,若略去,a[j]要多对比一次
				tag = !tag;//换右指针向左走
			}
		} else {
			if (a[j] > tem) {//同上
				j--;
				continue;
			} else {
				a[i] = a[j];
				i++;//可略去
				tag = !tag;
			}
		}
	}
	a[i] = tem;//最右当i 、j相遇时,把当时所选的数放进去即可

  

上述代码相对比较傻瓜,是完全按照上面一步一步来的,代码可以进一步压缩:

 

while(i < j){

   while(i < j && a[j] > tem){ j--;}
   swap(a[i],a[j]);//交换两个数
   while(i < j && a[j] < tem){i++;}
   swap(a[i],a[j]);
}
a[i] = tem;

 当然,分治法用到了递归,是肯定要设置一个出口的,

if(end <= begin){
   return;
}

 以上即可。

 

 

附录:

下面把完整外码贴出来

 

public class QuickSort {

	static void quickSort(int[] a, int begin, int end) {

		/*
		 * 找到某个数字的制定位置,并记录下来
		 */
		if(end <= begin){
			return;
		}
		int i = begin;
		int j = end;
		int tem = a[end];
		boolean tag = true;
		while (i != j) {
			if (tag) {
				if (a[i] < tem) {
					i++;
					continue;
				} else {
					a[j] = a[i];
					tag = !tag;
				}
			} else {
				if (a[j] > tem) {
					j--;
					continue;
				} else {
					a[i] = a[j];
					tag = !tag;
				}
			}
		}
		a[i] = tem;
		quickSort(a, begin, i - 1);
		quickSort(a, i + 1, end);
	}

	public static void main(String[] args) {
		int[] a = { 5, 7, 8, 2, 6, 125, 41, 341, 34, 63, 28, 97 };
		quickSort(a, 0, a.length - 1);
	}

}

 

分享到:
评论

相关推荐

    java算法——快速排序

    快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...

    快速排序示例代码(JAVA版)

    与本人博文《算法专项(1)——快速排序》相配套的工程源码,用JAVA实现

    Java数据结构和算法

    (1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结

    数据结构&amp;算法——Java.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    选择排序——Java实现

    冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...

    java代码-使用java解决java排序之-快速排序的问题的源代码

    java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!

    算法与数据结构体系课(java版,16周全+代码+PDF图文资料)

    分享一套算法与数据结构的视频课程——《算法与数据结构体系课》,课程一共16周内容,提供配套的源码和图文资料...【阶段3:算法与数据结构进阶】第10周、冒泡排序,希尔排序和排序算法大总结 【阶段3:算法与数据结

    数据结构与算法分析Java语言描述(第二版)

    堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1...

    数据结构与算法分析_Java语言描述(第2版)]

    堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...

    算法和数据结构——左程云.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    数据结构与算法分析_Java语言描述(第2版)

    7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法...

    java代码-使用java解决快速排序的源代码

    java代码-使用java解决快速排序的源代码 ——学习参考资料:仅用于个人学习使用!

    十种JAVA排序算法实例

    本文件讲了十种JAVA排序方法(冒泡(Bubble)排序——相邻交换 、选择排序——每次最小/大排在相应的位置 、插入排序——将下一个插入已排好的序列中 、壳(Shell)排序——缩小增量 、归并排序 、快速排序 、堆排序 ...

    数据结构与算法分析 Java语言描述第2版

    堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...

    数据结构与算法分析-Java语言描述(第2版)_1_2

    7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...

    C/C++常用算法手册.秦姣华(有详细书签).rar

    4.6 快速排序法 113 4.6.1 快速排序算法 113 4.6.2 快速排序算法示例 114 4.7 堆排序法 116 4.7.1 堆排序算法 116 4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序...

    Data-Structure:《数据结构与算法分析》上的代码实现

    - 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -最小生成树 -深度优先搜索 -双连通性 -欧拉回路 ###第十章 -分治算法:最近点问题 -动态...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...

Global site tag (gtag.js) - Google Analytics