JAVA算法起步之快速排序实例

2024-12-23 21:46:55

快速排序一听这个名字可能感觉很快，但是他的算法时间复杂度最坏情况却跟插入排序是一样的。之所以成为快速排序是因为他的平均效率比堆排序还要快，快速排序也是基于分治思想与归并排序差不多，但是快速排序是原址的，直接在原数组操作不需要再开辟新的存储空间。快速排序的思想很简单，就是选定一个关键字k将原数组分成两份g1与g2，g1中所有的元素都比k小或者相等，而g2中所有的数据都比k大或者等于，这样对g1与g2分别进行快速排序，最终我们得到的就是一个有序的数组。代码中的sort方法就是对刚才语句的描述。而关键的算法就是去寻找k的位置将原数组分为大小两部分的过程。方法getPlocation就是快速排序的核心。他的实现原理有点像插入排序只是有点像。每次都把map中end位置的元素作为关键字，通过与end元素对比将数组分成大小两部分，而i与j则是两个分割线，i与j之间的数都是比core大的元素，i与j就像一条贪吃蛇，当j的下一个数比core大的时候j+1，i到j的长度增大了，而如果比core小的话，i与j都向前走一下，并将那个小数放在i的前面。这样循环一遍后，start到end-1之间就是按大小分开的，最后将core放在中间，将core的位置返回就是分界线了。

代码如下:

public class QuickSort {
public int getPlocation(int[] map,int start,int end){
  int core=map[end];
  int i=start-1;
  for(int j=start;j<=end-1;j++){
   if(map[j]<=core){
    i++;
    int cache=map[j];
    map[j]=map[i];
    map[i]=cache;
   }
  }
  i++;
  map[end]=map[i];
  map[i]=core;
  return i;
}
public void sort(int[] map,int start,int end){
  if(start<end){
  int p=getPlocation(map, start, end);
  sort(map, start, p-1);
  sort(map,p+1,end);
  }
}
public static void main(String[] args) {
  int[] map=new int[]{4,1,5,3,7,12,65,7};
  QuickSort qs=new QuickSort();
  qs.sort(map, 0, map.length-1);
  for (int i = 0; i < map.length; i++) {
   System.out.println(map[i]);
  }
}
}

快速排序算法原理及java递归实现

快速排序对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指
java 算法之快速排序实现代码

java 算法之快速排序实现代码摘要: 常用算法之一的快速排序算法的java实现原理:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描, 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素, 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分. /** * * @author 阿信sxq-2015年7月16日 * * @param args */ public static void main(String[] args) { int
java实现快速排序算法

1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于
详解Java中使用泛型实现快速排序算法的方法

快速排序算法概念快速排序一般基于递归实现.其思路是这样的: 1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为"枢轴"(pivot). 2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边. 3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上. 4.对两个子数组分别重复上述过程,直到每个数组只有一个元素. 5.排序完成. 基本实现方式: public static void quickSort(int[] arr){ qsort(arr,
详解快速排序算法中的区间划分法及Java实现示例

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.该方法的基本思想是: 1．先从数列中取出一个数作为基准数. 2．分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3．再对左右区间重复第二步,直到各区间只有一个数. 算法的思路很清晰,但是如果在区间划分过程中边界值没有处理好,也是很容易出现bug的.下面给出两种比较清晰的思维来指导区间划分代码的编写. 第一种思维即所谓的挖坑法思维,下面通过分析一个实例来分析一下挖坑法的过程: 以一个数组作为示例,取区间
浅析java快速排序算法

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)
图文讲解Java中实现quickSort快速排序算法的方法

相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主
Java编程中快速排序算法的实现及相关算法优化

时间复杂度平均情况:O(nlgn) 最坏情况:O(n*n),发生在当数据已经是排序状态时快排算法的基本原理 1.从数据中选取一个值a[i]作为参考 2.以a[i] 为参考,将数据分成2部分:P1.P2,P1中的数据全部≤a[i],P2中的数据全部>a[i],数据变为{{P1}{a[i]}{P2}} 3.将P1.P2重复上述步骤,直到各部分中只剩1个数据 4.数据完成升序排列基本示例: 原始数据: {3,9,8,5,2,1,6} 第1步:选取第1个数据:3 第2步:将数据分成2部分,左边≤3
java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:
Java实现快速排序算法(Quicktsort)

快速排序算法介绍快速排序和归并排序都使用分治法来设计算法,区别在于归并排序把数组分为两个基本等长的子数组,分别排好序之后还要进行归并(Merge)操作,而快速排序拆分子数组的时候显得更有艺术,取一个基准元素,拆分之后基准元素左边的元素都比基准元素小,右边的元素都不小于基准元素,这样只需要分别对两个子数组排序即可,不再像归并排序一样需要归并操作.基准元素的选取对算法的效率影响很大,最好的情况是两个子数组大小基本相当.为简单起见,我们选择最后一个元素,更高级的做法可以先找一个中位数并把中位数与最后一

JAVA算法起步之快速排序实例

相关推荐

随机推荐