`

Java快速排序

    博客分类:
  • java
阅读更多

快速排序的基本思想

         通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序。

 

       先看一下这幅图:



 把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比它小交换,比它大不做任何处理;交换了以后再和小的那端比,比它小不交换,比他大交换。这样循环往复,一趟排序完成,左边就是比中轴小的,右边就是比中轴大的,然后再用分治法,分别对这两个独立的数组进行排序。

1	public int getMiddle(Integer[] list, int low, int high) {  
2	        int tmp = list[low];    //数组的第一个作为中轴  
3	        while (low < high) {  
4	            while (low < high && list[high] > tmp) {  
5	                high--;  
6	            }  
7	            list[low] = list[high];   //比中轴小的记录移到低端  
8	            while (low < high && list[low] < tmp) {  
9	                low++;  
10	            }  
11	            list[high] = list[low];   //比中轴大的记录移到高端  
12	        }  
13	        list[low] = tmp;              //中轴记录到尾  
14	        return low;                   //返回中轴的位置  
15	    }  

   递归形式的分治排序算法:

16	public void _quickSort(Integer[] list, int low, int high) {  
17	        if (low < high) {  
18	            int middle = getMiddle(list, low, high);  //将list数组进行一分为二  
19	            _quickSort(list, low, middle - 1);        //对低字表进行递归排序  
20	            _quickSort(list, middle + 1, high);       //对高字表进行递归排序  
21	        }  
22	    }  

 

23	public void quick(Integer[] str) {  
24	        if (str.length > 0) {    //查看数组是否为空  
25	            _quickSort(str, 0, str.length - 1);  
26	        }  
27	    }  

 编写测试方法:

 

28	public class TestMain {  
29	  
30	    /**  
31	     * @param args  
32	     */  
33	    public static void main(String[] args) {  
34	        // TODO Auto-generated method stub  
35	         Integer[] list={34,3,53,2,23,7,14,10};  
36	         QuicSort qs=new QuicSort();  
37	         qs.quick(list);  
38	         for(int i=0;i<list.length;i++){  
39	             System.out.print(list[i]+" ");  
40	         }  
41	         System.out.println();  
42	    }  
43	  
44	}  

 看一下打印结果吧:

     2 3 7 10 14 23 34 53

 这样就排序好了,快速排序是对冒泡排序的一种改进,平均时间复杂度是O(nlogn)

 

 

  • 大小: 84.6 KB
分享到:
评论

相关推荐

    java快速排序算法实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R....这个压缩包中的"java快速排序算法"可能包含了更多关于快速排序的示例代码、详细解析和实践练习,可以帮助初学者更好地理解和掌握这种高效的排序算法。

    java 快速排序 折半查找的界面实现 (递归与分治法)

    总的来说,快速排序和折半查找是计算机科学中不可或缺的算法,通过递归和分治策略,可以在Java中高效地实现这些算法,并结合界面设计,为用户提供直观的交互体验。在实际项目中,理解和掌握这些算法有助于优化数据...

    Java 快速排序

    以下是一个简单的Java快速排序算法的实现: ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low ) { // 找到基准元素的正确位置 int pivotIndex = ...

    java 快速排序程序

    java 编写的快速排序程序递归形式我做的课堂作业,,希望能帮助大家。。。

    Java 快速排序算法

    Java 快速排序,目前来说效率很高的一种排序算法,好理解。

    java快速排序动画jar

    之前做的四种排序动画,快排比较快,所以为快排专门做一个动画

    java 快速排序 折半查找的界面实现

    总的来说,"java 快速排序 折半查找的界面实现"项目旨在通过可视化的方式帮助学习者理解和掌握这两种经典的算法。通过实际的代码实现和交互式的界面,不仅能够锻炼编程技能,还能加深对算法本质的理解,对于提升编程...

    JAVA快速排序法.pdf

    JAVA快速排序法 JAVA快速排序法是一种高效的排序算法,属于选择排序的一种。它的主要思想是通过选择一个基准元素,将数组分成两个部分:一部分比基准元素小,一部分比基准元素大,然后递归地对这两个部分进行排序。...

    快速排序 java代码

    java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码

    [原]Java 快速排序

    以上就是Java快速排序的基本原理和源码分析。快速排序的平均时间复杂度为O(n log n),在最坏情况下(已经排序或逆序)时间复杂度为O(n^2)。由于其高效的性能和相对简单的实现,快速排序在实际应用中被广泛使用。

    java快速排序算法和案例

    java快速排序算法和案例

    快速排序算法的java实现

    在Java中实现快速排序,我们通常会定义一个`quickSort()`方法,该方法接受一个整数数组作为参数。快速排序的核心在于选择一个基准元素(pivot),并重新排列数组使得所有小于基准的元素都在其前,所有大于基准的元素...

    java实现快速排序

    在Java中实现快速排序,我们可以遵循以下步骤: 1. **选择基准值(Pivot)**:首先,我们需要从数组中选取一个元素作为基准,这个元素将被用来分割数组。通常选择第一个或最后一个元素,但也可以是随机选取的。 2....

    java快速排序法

    清楚明确的代码书写,让你轻易学懂快速排序法

    简单的快速排序

    在Java中实现快速排序,我们需要定义一个方法来执行这个过程。下面是一个简化的快速排序算法的Java实现: ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if ...

    java快速排序工具类

    使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。

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

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

    快速排序算法java代码

    "快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...

    算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    java快速排序、随机优化快排

    java快速排序,和随机优化快排 注解详细,多个版本可选,最简洁版、最高效率版、随机优化版...

Global site tag (gtag.js) - Google Analytics