快速排序
算法思想:基于分治的思想,是冒泡排序的改进型。首先在数组中选择一个基准点(该基准点的选取可能影响快速排序的效率,后面讲解选取的方法),然后分别从数组的两端扫描数组,设两个指示标志(lo指向起始位置,hi指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换lo和hi位置的值,然后从前半部分开始扫秒,发现有元素大于基准点的值,就交换lo和hi位置的值,如此往复循环,直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。
排序过程:
算法实现:
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实现)的更多相关文章
-
快速排序 Java实现的快速排序
快速排序 Java实现的快速排序: package xc; import java.util.Arrays; import java.util.Random; /** * * @author dax ...
-
基本排序算法——快速排序java实现
简单的快速排序算法,我竟然花费了如此多的时间来写作,好好学习. /** * */ package basic.sort; import java.util.Arrays; import java.ut ...
-
排序算法----快速排序java
快速排序是对冒泡排序的一种改进,平均时间复杂度是O(nlogn) import java.util.Arrays; import java.util.Scanner; public class tes ...
-
快速排序 java详解
1.快速排序简介: 快速排序由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此 ...
-
ADV-297 快速排序 java
问题描述 用递归来实现快速排序(quick sort)算法.快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x.首先对数组中的元素进行调整,使x放在正确的位置上.同时,所有比x小 ...
-
快速排序-java
排序-快速排序 基本思想: 将数据划分为两部分,左边的所有元素都小于右边的所有元素:然后,对左右两边进行快速排序. 划分方法: 选定一个参考点(中间元素),所有元素与之相比较,小的放左边,大的放右边. ...
-
数组排序-冒泡排序-选择排序-插入排序-希尔排序-快速排序-Java实现
这五种排序算法难度依次增加. 冒泡排序: 第一次将数组相邻两个元素依次比较,然后将大的元素往后移,像冒泡一样,最终最大的元素被移到数组的最末尾. 第二次将数组的前n-1个元素取出,然后相邻两个元素依次 ...
-
排序算法之快速排序(java实现)
package com.javaTest300; public class Test039 { public static void main(String[] args) {// 快速排序 int ...
-
快速排序java
快速排序(Quicksort)是对冒泡排序的一种改进.它是先在数组中找到一个关键数,第一趟排序将比关键数小的放在它的左边,比关键数大的放在它的右边.当第一趟排序结束后,再依次递归将左边和右边的进行排序 ...
-
快速排序Java实现
package practice; import edu.princeton.cs.algs4.*; public class TestMain { public static void main(S ...
随机推荐
-
Hadoop 2.0 中的资源管理框架 - YARN(Yet Another Resource Negotiator)
1. Hadoop 2.0 中的资源管理 http://dongxicheng.org/mapreduce-nextgen/hadoop-1-and-2-resource-manage/ Hadoop ...
-
CustomValidator验证的使用方法
<asp:TextBox ID="txtNum" runat="server" Width="400px" ></asp: ...
-
JavaScript的正则表达式使用
一:遇到问题 今天做项目时,在前台js对身份证号进行验证时,一直达不到预期的效果,我是监控文本域变量, $scope.watch('form.idNo',function(v){ if(!v){ re ...
-
【python】python中 简单的 glob模块
glob模块是最简单的模块之一,内容非常少.用它可以查找符合特定规则的文件路径名.跟使用windows下的文件搜索差不多.查找文件只用到三个匹配符:"*", "?&quo ...
-
CF 610E. Alphabet Permutations
题目:http://codeforces.com/problemset/problem/610/E 如果存在c1,c2在原串相邻且在询问串中c1在c2前面的话,把它们在原串出现次数加起来记作sum,那 ...
-
PHP Laravel框架入门心得 | How to study PHP Laravel Framework
PHP有不少开发框架,其中比较出名的有Symfony和Laravel. 我说说我最近入门Laravel的感受和学习方法吧. 1.第一个感受是Laravel的社区讨论和学习资源真的是太棒了,中文化也做得 ...
-
Java应用程序使用系统托盘资源
要想使自己开发的Java SE项目运行在自己的电脑系统托盘上,这并不是什么难事,总共需要如下几步即可: 1.线判断一下,系统托盘是否可用,否则接下来的程序将不可避免的报出异常咯 2.获得一个Syste ...
-
CentOS 7 Sersync+Rsync 实现数据文件实时同步
rsync+inotify-tools与rsync+sersync架构的区别? 1.rsync+inotify-tools inotify只能记录下被监听的目录发生了变化(增,删,改)并没有把具体是哪 ...
-
使用idea+springboot+Mybatis搭建web项目
使用idea+springboot+Mybatis搭建web项目 springboot的优势之一就是快速搭建项目,省去了自己导入jar包和配置xml的时间,使用非常方便. 1.创建项目project, ...
-
mongodb如何设置主键自增
function getNextSequence(name){ var ret = db.counters.findAndModify({ query: { _id: name}, update:{ ...