`
xxtianxiaxing
  • 浏览: 705376 次
  • 性别: Icon_minigender_1
  • 来自: 陕西
社区版块
存档分类
最新评论

Java快速排序实例

阅读更多

      基本思想:

  快速排序是冒泡排序的改进版本,它的思想是通过一趟排序讲待排序的记录分隔成独立的两部分,其中一不分记录的关键字均小于另一部分关键字,则可以分别对这两部门记录继续进行排序,以打倒整个虚列的有序。

  假设待排序的虚列为{L.r[s],L.r[s+1],.......,L.r[t]]},首先选取一个记录(通常可一选择第一个记录L.r[s])作为枢轴(或支点),然后按照下述原则重新排列其他记录,讲所有关键字较它小的记录都安置在它的位置之前,将所有关键字较它大的记录都安置在它的位置之后。由此可以该 “枢轴” 记录最后所落的位置i作为分界,将序列{L.r[s],L.r[s+1],.......,L.r[t]]} 分隔成了两个子序列{L.r[s],L.r[s+1],.......,L.r[i-1]]} 和 {L.r[i+1],L.r[s+1],.......,L.r[t]]},这个过程叫作一趟快速排序(或者一次划分)。

  一趟快速怕序的具体做法是:附设两个指针low和high,他们的初值分别为low和high,设枢轴记录的关键字为privotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指向的位置起向后搜索,找到第一个关键字大于privotkey的记录和枢轴记录互相交换,重复这两步直至low==high位置。

  代码一:

  /**
  * 采用交换方式 排序
  */
  package 排序.交换排序;
  import
java.util.concurrent.Executor;
  import java.util.concurrent.ExecutorService;
  import java.util.concurrent.Executors;
  /**
  * @author liuyi
  */
  public class 快速排序 {
  public static void main(String[] args) throws InterruptedException {
  int
test[] = {15,23,56,7,13,52,20,7};
  new 快速排序().qSort(test, 0, test.length-1);
  for(int k:test) System.out.println(k);
  }
  public void qSort(int []array,int low,int high){
  if(low
  int privot=partition(array,low,high);
  qSort(array,low,privot-1);
  qSort(array,privot+1,high);
  }
  }
  public int partition(int [] array,int low,int high){
  /**
  * 选择low位置作为曲轴(支点)
  */
  int pivot=array[low];
  int temp=0;
  /**
  * 如果 low
  */
  while(low
  /**
  * 先从 high端 开始判断
  */
  while(low=pivot) high--;
  /**
  * 进行 置换操作
  */
  if(low
  temp=array[low];
  array[low]=array[high];
  array[high]=temp;
  low++;
  }
  /**
  * 从 low 端判断
  */
  while(low
  /**
  * 进行 置换操作
  */
  if(low
  temp=array[high];
  array[high]=array[low];
  array[low]=temp;
  high--;
  }
  }
  return low;
  }
  }

  具体实现上述算法时候,每交换一对记录需要进行三次记录的移动(赋值)的操作,而实际上,在排序过程中对枢轴记录的赋值是多余的,因为只有在一趟排序结束时,即low==high的位置菜市枢轴记录的最后位置,由此可改写上述算法,先将记录暂时存在r[0]的位置上,排序过程中做r[low]或r[high]的单向移动,直至一趟排序后再将枢轴记录移至正确位置上。

  改写代码

  代码二:

  /**
  * 改进的 快速排序
  */
  package 排序.交换排序;
  import java.util.concurrent.Executor;
  import java.util.concurrent.ExecutorService;
  import java.util.concurrent.Executors;
  /**
  * @author liuyi
  */
  public class 快速排序_1 {
  public static void main(String[] args) throws InterruptedException {
  int test[] = {15,23,56,7,13,52,20,7};
  new 快速排序_1().qSort(test, 0, test.length-1);
  for(int k:test) System.out.println(k);
  }
  public void qSort(int []array,int low,int high){
  if(low
  int privot=partition(array,low,high);
  qSort(array,low,privot-1);
  qSort(array,privot+1,high);
  }
  }
  public int partition(int [] array,int low,int high){
  /**
  * 选择 low位置 作为曲轴(支点)
  */
  int pivot=array[low];
  int temp=0;
  /**
  * 如果 low
  */
  while(low
  /**
  * 先从 high端 开始判断
  */
  while(low=pivot) high--;
  /**
  * 进行 置换操作
  */
  if(low
  array[low]=array[high];
  low++;
  }
  /**
  * 从 low 端判断
  */
  while(low
  /**
  * 进行 置换操作
  */
  if(low
  array[high]=array[low];
  high--;
  }
  }
  array[low]=pivot;
  return low;
  }
  }

分享到:
评论
1 楼 wuyufeixue 2010-12-28  
    

相关推荐

    基础编程:Java快速排序实例详解

    基础编程:Java快速排序实例详解

    JAVA冒泡排序和快速排序算法

    在JAVA中,实现这两种排序算法可以使用面向对象的特性,创建一个类如`MaopaoKuaisu.java`,在这个类中定义两个方法,分别实现冒泡排序和快速排序。类的结构可能如下: ```java public class MaopaoKuaisu { public...

    Java 冒泡排序、快速排序实例代码

    Java 冒泡排序、快速排序实例代码 Java 冒泡排序、快速排序实例代码是 Java 编程语言中两个常用的排序算法,分别是冒泡排序和快速排序。下面是对这两个算法的详细介绍和实例代码。 冒泡排序 冒泡排序是一种简单的...

    java实现选择排序实例

    在本文中,我们将深入探讨Java编程语言中的选择排序算法,并通过一个实际的示例来解释其工作...在实际开发中,Java程序员通常会使用内置的`Arrays.sort()`方法,它采用了更高效的排序算法,如快速排序、归并排序等。

    java se 经典实例

    例如,你可能会遇到一个关于排序和查找算法的实例,如快速排序或二分查找。 多线程是Java的一大亮点,它允许程序同时执行多个任务。通过并发编程实例,你可以学习如何创建和管理线程,以及如何使用同步机制防止数据...

    Java各种排序算法、Java游戏和实例代码集合

    - **快速排序**:由“分治”策略实现,选取一个基准元素,将数组分为两部分,小于基准的放在左边,大于基准的放在右边,然后递归处理左右两部分。 - **归并排序**:同样采用“分治”,将数组分为两半,分别排序,...

    java算法140实例

    1. **排序算法**:包括经典的冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。这些算法在实际编程中用于数据整理和处理,例如数据库查询优化、数据分析等场景。 2. **查找算法**:二分查找、哈希查找...

    java数据结构实例

    "Java数据结构实例"这个主题,旨在通过具体的代码实例帮助初学者掌握数据结构的基本概念和使用方式,以此来提升编程思维和问题解决能力。在这个压缩包文件中,我们可以预期找到一些用Java实现的数据结构的源代码。 ...

    Java快速排序QuickSort(实例)

    Java快速排序QuickSort算法详解 Java快速排序QuickSort是一种常用的排序算法,它的时间复杂度为O(n log n),空间复杂度为O(log n),是一种高效的排序算法。下面是Java快速排序QuickSort的详细介绍: 算法思想 ...

    java List 排序 Collections.sort

    快速排序是一种分治策略,通过选择一个基准值,将数组分为两部分,左边的元素都小于基准,右边的元素都大于基准,然后再对左右两部分递归地进行快速排序,直到所有元素都在正确的位置上。 此外,对于`List`的排序,...

    15个经典的java课程设计实例.rar

    1. **基础数据结构与算法**:实例可能包含链表、栈、队列、树等基本数据结构的实现,以及排序(冒泡、选择、插入、快速等)和查找算法的运用。 2. **面向对象编程**:Java的核心特性是面向对象,实例可能会展示类的...

    java简单冒泡排序实例解析

    冒泡排序是一种基础的排序算法,它通过重复遍历待排序的序列,比较相邻元素并交换位置,使得每个元素都能逐步“浮”到其正确的位置...在实际开发中,我们通常会选择更高效的排序算法,如快速排序、归并排序或堆排序等。

    Java各种排序算法代码.zip

    在Java中,快速排序通常用递归实现。 5. 归并排序(Merge Sort): 归并排序是一种分治策略,将大问题分解为小问题解决。它将数组分为两个子数组,分别进行排序,然后合并成一个有序数组。Java中,归并排序需要额外...

    Java技术和实例开发讲座-PPT

    总的来说,这个"Java技术和实例开发讲座"涵盖了从Java语言基础到高级特性的广泛内容,结合实例讲解,有助于参与者快速提升Java编程技能,并能够将所学知识应用到实际项目中。通过学习这个讲座,你将能够更好地理解和...

    java简单快速排序实例解析

    java简单快速排序实例解析 一、基本概念 快速排序是一种基于比较的排序算法,通过选择一个基准元素(pivot),将数组分为两个部分,使得左边的元素小于或等于基准元素,右边的元素大于或等于基准元素,然后使用...

    java集合使用实例

    Java集合框架是Java编程语言中一个非常重要的组成部分,它提供了数据结构和算法的实现,使得在处理各种数据存储和操作时更加高效。...通过实践提供的实例,我们可以深入学习这些集合类的使用,并在具体项目中灵活应用。

    Java编程基于快速排序的三个算法题实例代码

    Java编程基于快速排序的三个算法题实例代码 快速排序是一种非常高效的排序算法,它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较小的记录从后面直接移动到前面,从而...

    基于Java的快速排序算法详解与代码实现

    内容概要:本文档详细解析了快速排序(Quicksort)算法在 Java 语言环境下的实现步骤。通过对具体代码片段的研究,展示了如何确定基准点、元素的比较与交换以及递归过程中的边界条件判断。并附带了一个简单的测试...

    JAVA经典排序汇总

    - **快速排序**:以“分治法”为基础,选取一个基准值,将数组分为两部分,然后递归地对这两部分进行快速排序。平均时间复杂度为O(nlogn),是常用的高效排序算法。 3. **选择排序**: - **直接选择排序**:每次...

    java高级实例设计

    在Java高级实例设计中,我们探索的是如何利用Java这一强大且多用途的编程语言来构建复杂的游戏程序和基础性小程序。这些实例对于提升程序员的技能水平、理解和掌握Java的核心概念至关重要。下面,我们将深入探讨一些...

Global site tag (gtag.js) - Google Analytics