快速排序(java实现)

时间:2022-09-06 16:49:38

快速排序

算法思想:基于分治的思想,是冒泡排序的改进型。首先在数组中选择一个基准点(该基准点的选取可能影响快速排序的效率,后面讲解选取的方法),然后分别从数组的两端扫描数组,设两个指示标志(lo指向起始位置,hi指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换lo和hi位置的值,然后从前半部分开始扫秒,发现有元素大于基准点的值,就交换lo和hi位置的值,如此往复循环,直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

排序过程:

快速排序(java实现)

算法实现:

public static int partition(int []array,int lo,int hi){
//固定的切分方式
int key=array[lo];
while(lo<hi){
while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){从前半部分向后扫描
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
} public static void sort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}

快速排序的时间复杂度为O(NlogN).

快速排序的优化

对于基准位置的选取一般有三种方法:固定切分,随机切分和三取样切分。固定切分的效率并不是太好,随机切分是常用的一种切分,效率比较高,最坏情况下时间复杂度有可能为O(N2).对于三数取中选择基准点是最理想的一种。

三数取中切分:

public static int partition(int []array,int lo,int hi){
//三数取中
int mid=lo+(hi-lo)/2;
if(array[mid]>array[hi]){
swap(array[mid],array[hi]);
}
if(array[lo]>array[hi]){
swap(array[lo],array[hi]);
}
if(array[mid]>array[lo]){
swap(array[mid],array[lo]);
}
int key=array[lo]; while(lo<hi){
while(array[hi]>=key&&hi>lo){
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
} public static void swap(int a,int b){
int temp=a;
a=b;
b=temp;
}
public static void sort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}

快速排序在序列中元素很少时,效率将比较低,不然插入排序,因此一般在序列中元素很少时使用插入排序,这样可以提高整体效率。

public static void quick(int []array ,int lo,int hi){
if(hi-lo+1<10){
insertSort(array);
}else{
quickSort(array,lo,hi);
}
}

快速排序(java实现)的更多相关文章

  1. 快速排序 Java实现的快速排序

    快速排序  Java实现的快速排序: package xc; import java.util.Arrays; import java.util.Random; /** * * @author dax ...

  2. 基本排序算法——快速排序java实现

    简单的快速排序算法,我竟然花费了如此多的时间来写作,好好学习. /** * */ package basic.sort; import java.util.Arrays; import java.ut ...

  3. 排序算法----快速排序java

    快速排序是对冒泡排序的一种改进,平均时间复杂度是O(nlogn) import java.util.Arrays; import java.util.Scanner; public class tes ...

  4. 快速排序 java详解

    1.快速排序简介: 快速排序由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此 ...

  5. ADV-297 快速排序 java

    问题描述 用递归来实现快速排序(quick sort)算法.快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x.首先对数组中的元素进行调整,使x放在正确的位置上.同时,所有比x小 ...

  6. 快速排序-java

    排序-快速排序 基本思想: 将数据划分为两部分,左边的所有元素都小于右边的所有元素:然后,对左右两边进行快速排序. 划分方法: 选定一个参考点(中间元素),所有元素与之相比较,小的放左边,大的放右边. ...

  7. 数组排序-冒泡排序-选择排序-插入排序-希尔排序-快速排序-Java实现

    这五种排序算法难度依次增加. 冒泡排序: 第一次将数组相邻两个元素依次比较,然后将大的元素往后移,像冒泡一样,最终最大的元素被移到数组的最末尾. 第二次将数组的前n-1个元素取出,然后相邻两个元素依次 ...

  8. 排序算法之快速排序&lpar;java实现&rpar;

    package com.javaTest300; public class Test039 { public static void main(String[] args) {// 快速排序 int ...

  9. 快速排序java

    快速排序(Quicksort)是对冒泡排序的一种改进.它是先在数组中找到一个关键数,第一趟排序将比关键数小的放在它的左边,比关键数大的放在它的右边.当第一趟排序结束后,再依次递归将左边和右边的进行排序 ...

  10. 快速排序Java实现

    package practice; import edu.princeton.cs.algs4.*; public class TestMain { public static void main(S ...

随机推荐

  1. Hadoop 2&period;0 中的资源管理框架 - YARN&lpar;Yet Another Resource Negotiator&rpar;

    1. Hadoop 2.0 中的资源管理 http://dongxicheng.org/mapreduce-nextgen/hadoop-1-and-2-resource-manage/ Hadoop ...

  2. CustomValidator验证的使用方法

    <asp:TextBox ID="txtNum" runat="server" Width="400px" ></asp: ...

  3. JavaScript的正则表达式使用

    一:遇到问题 今天做项目时,在前台js对身份证号进行验证时,一直达不到预期的效果,我是监控文本域变量, $scope.watch('form.idNo',function(v){ if(!v){ re ...

  4. 【python】python中 简单的 glob模块

    glob模块是最简单的模块之一,内容非常少.用它可以查找符合特定规则的文件路径名.跟使用windows下的文件搜索差不多.查找文件只用到三个匹配符:"*", "?&quo ...

  5. CF 610E&period; Alphabet Permutations

    题目:http://codeforces.com/problemset/problem/610/E 如果存在c1,c2在原串相邻且在询问串中c1在c2前面的话,把它们在原串出现次数加起来记作sum,那 ...

  6. PHP Laravel框架入门心得 &vert; How to study PHP Laravel Framework

    PHP有不少开发框架,其中比较出名的有Symfony和Laravel. 我说说我最近入门Laravel的感受和学习方法吧. 1.第一个感受是Laravel的社区讨论和学习资源真的是太棒了,中文化也做得 ...

  7. Java应用程序使用系统托盘资源

    要想使自己开发的Java SE项目运行在自己的电脑系统托盘上,这并不是什么难事,总共需要如下几步即可: 1.线判断一下,系统托盘是否可用,否则接下来的程序将不可避免的报出异常咯 2.获得一个Syste ...

  8. CentOS 7 Sersync&plus;Rsync 实现数据文件实时同步

    rsync+inotify-tools与rsync+sersync架构的区别? 1.rsync+inotify-tools inotify只能记录下被监听的目录发生了变化(增,删,改)并没有把具体是哪 ...

  9. 使用idea&plus;springboot&plus;Mybatis搭建web项目

    使用idea+springboot+Mybatis搭建web项目 springboot的优势之一就是快速搭建项目,省去了自己导入jar包和配置xml的时间,使用非常方便. 1.创建项目project, ...

  10. mongodb如何设置主键自增

    function getNextSequence(name){ var ret = db.counters.findAndModify({ query: { _id: name}, update:{ ...