java快速排序简单代码

一、java快速排序简单代码

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid#d4d4d4;width:98%}div.code{width:98%;border:1px solid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid#ddd;border-left-width:4px;padding:10px 15px}排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case的时间复杂度达到了 O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn)的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn)记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

从数列中挑出一个元素，称为"基准"（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

代码实现 JavaScript实例 function quickSort( arr, left, right){

   var len= arr. length,

     partitionIndex,

     left= typeof left!='number'? 0: left,

     right= typeof right!='number'? len- 1: right;

二、java面试题 很急 谢谢

2,归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

void merge(int data[], int p, int q, int r)

for(i= 0, k= p; i< n1; i++, k++)

for(i= 0, k= q+ 1; i< n2; i++, k++)

for(k= p, i= 0, j= 0; i< n1&& j< n2; k++)

for(j= i; j< n1; j++, k++)

for(i= j; i< n2; i++, k++)

void merge_sort(int data[], int p, int r)

int data[]={44, 12, 145,-123,-1, 0, 121};

printf("-------------------------------merge sort----------------------------\n");

4.对于有n个结点的线性表（e0，e1，…，en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。

若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。

在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。

下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。

反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。

假设线性表的前面I个结点序列e0，e1，…，en-1是已排序的。对结点在这有序结点ei序列中找插入位置，并将ei插入，而使i+1个结点序列e0，e1，…，ei也变成排序的。依次对i=1，2，…，n-1分别执行这样的插入步骤，最终实现线性表的排序。

对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让键值大的结点往下沉，键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。

对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为1使才不再划分。当所有子序列长度都为1时，序列已是排好序的了。

一种树形选择排序，是对直接选择排序的有效改进。一个堆是这样一棵顺序存储的二叉树，它的所有父结点（e[i]）的键值均不小于它的左子结点（e[2*i+1]）和右子结点（e[2*i+2]）的键值。初始时，若把待排序序列的n个结点看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大值。依次类推，直到只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。

将两个或两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并一个有序表的两路合并排序来说，初始时，把含n个结点的待排序序列看作有n个长度都为1的有序子表所组成，将它们依次两两合并得到长度为2的若干有序子表，再对它们作两两合并……直到得到长度为n的有序表，排序即告完成。

后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。

for(t=e[i], j=i-1; j>=0&&t<e[j]; j--)

t=e[j]; e[j]=e[j+1]; e[j+1]=t;

for(k=j-h; k>0&&y<e[k]; k-=h)

void r_quick(int e[], int low, int high)

while(i<j&&e[j]>t) j--;

while(i<j&&e[i]<=t) i++;

另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。

查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。

按查找的条件分类，有按结点的关键码查找、关键码以外的其他数据项查找或其他数据项的组合查找等。按查找数据在内存或外存，分内存查找和外存查找。按查找目的，查找如果只是为了确定指定条件的结点存在与否，成为静态查找；查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。

这里简单介绍几种常见的查找方法。

这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。

分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。

对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。

散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。

三、求java考题,笔试题

This（）：当前类的对象,super父类对象。

Super（）：在子类访问父类的成员和行为,必须受类继承规则的约束

而this他代表当前对象,当然所有的资源都可以访问.

在构造函数中,如果第一行没有写super(),编译器会自动插入.但是如果父类没有不带参数的构造函数,或这个函数被私有化了(用private修饰).此时你必须加入对父类的实例化构造.而this就没有这个要求,因为它本身就进行实例化的构造.

而在方法中super和this使用的方法就差不多了.只不过super要考虑是否能访问其父类的资源.

2.作用域public,protected,private,以及不写时的区别？

Public:不同包、同一包、类内都可用

Protected:不同包的子类、同一包、类内都可用

publicstatic void main(String[] args){

4. JAVA的事件委托机制和垃圾回收机制

Java事件委托机制的概念,一个源产生一个事件并将它送到一个或多个监听器那里。在这种方案中，监听器简单的等待，直到它收到一个事件。一旦事件被接受，监听器将处理这个事件，然后返回。

垃圾回收机制垃圾收集是将分配给对象但不再使用的内存回收或释放的过程。如果一个对象没有指向它的引用或者其赋值为null,则次对象适合进行垃圾回收

5.在JAVA中，如何跳出当前的多重嵌套循环？

6.什么是java序列化，如何实现java序列化？(写一个实例)

序列化:处理对象流的机制，所谓对象流也就是将对象的内容进行流化。可以对流化后的对象进行读写操作，也可将流化后的对象传输于网络之间。序列化是为了解决在对对象流进行读写操作时所引发的问题。

序列化的实现：将需要被序列化的类实现Serializable接口，该接口没有需要实现的方法，implementsSerializable只是为了标注该对象是可被序列化的，然后使用一个输出流(如：FileOutputStream)来构造一个ObjectOutputStream(对象流)对象，接着，使用ObjectOutputStream对象的writeObject(Object obj)方法就可以将参数为obj的对象写出(即保存其状态)，要恢复的话则用输入流。

7.一个".java"源文件中是否可以包括多个类（不是内部类）？有什么限制？

可以。如果这个类的修饰符是public，其类名与文件名必须相同。

8.排序都有哪几种方法？请列举。用JAVA实现一个快速排序？

排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）

9. Overload和Override的区别。Overloaded的方法是否可以改变返回值的类型?

重写Override，子类覆盖父类的方法，将子类传与父类的引用调用的还是子类的方法。

重载Overloading一个类多个方法，名称相同，参数个数类型不同。

两者都是Java多态性的不同表现。

Overloaded的方法是可以改变返回值的类型。

System.out.prinln(8+8+”88”+8+8);

（方法的重写Overriding和重载Overloading是Java多态性的不同表现。重写Overriding是父类与子类之间多态性的一种表现，重载Overloading是一个类中多态性的一种表现。如果在子类中定义某方法与其父类有相同的名称和参数，我们说该方法被重写(Overriding)。子类的对象使用这个方法时，将调用子类中的定义，对它而言，父类中的定义如同被“屏蔽”了。如果在一个类中定义了多个同名的方法，它们或有不同的参数个数或有不同的参数类型，则称为方法的重载(Overloading)。

Overloaded的方法是可以改变返回值的类型。）

属性常量方法不可以overridding类不可以继承

11.继承时候类的执行顺序问题,一般都是选择题,问你将会打印出什么?

System.out.println("FatherClassCreate");

public class ChildClass extends FatherClass{

System.out.println("ChildClassCreate");

public static void main(String[] args){

FatherClass fc= new FatherClass();

ChildClass cc= new ChildClass();

System.out.println("InterClassCreate");

InterClass ic= new InterClass();

System.out.println("OuterClassCreate");

public static void main(String[] args){

OuterClass oc= new OuterClass();

C:>java test/OuterClass InterClass Create OuterClass Create

13.用JAVA实现一种排序，JAVA类实现序列化的方法(二种)？

14.如在COLLECTION框架中，实现比较要实现什么样的接口？

public InsertSort(int num,int mod){

System.out.println("The ArrayList SortBefore:");

al.add(new Integer(Math.abs(rand.nextInt())% mod+ 1));

System.out.println("al["+i+"]="+al.get(i));

for(int i=1;i<al.size();i++){

tempInt=(Integer)al.remove(i);

if(tempInt.intValue()>=((Integer)al.get(MaxSize-1)).intValue()){

System.out.println(al.toString());

for(int j=0;j<MaxSize;j++){

if(((Integer)al.get(j)).intValue()>=tempInt.intValue()){

System.out.println(al.toString());

System.out.println("The ArrayList SortAfter:");

for(int i=0;i<al.size();i++){

System.out.println("al["+i+"]="+al.get(i));

public static void main(String[] args){

InsertSort is= new InsertSort(10,100);

JAVA类实现序例化的方法是实现java.io.Serializable接口

Collection框架中实现比较要实现Comparable接口和 Comparator接口

16.编程：编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。但是要保证汉字不被截半个，如"我ABC"4，应该截为"我AB"，输入"我ABC汉DEF"，6，应该输出为"我ABC"而不是"我ABC+汉的半个"。

public static void split(String source,intnum) throws Exception{

for(int i= 0; i<source.length(); i++){

byte[]b=(source.charAt(i)+"").getBytes();

15、Java编程,打印昨天的当前时刻

public class YesterdayCurrent{

public void main(String[] args){

Calendar cal= Calendar.getInstance();

System.out.println(cal.getTime());

BufferedReader in= new BufferedReader(newFileReader(f));

while((stri=in.readLine())!=null){

i= Integer.parseInt(stri.trim());

PrintWriter out=new PrintWriter(newBufferedWriter(new FileWriter(f,false)));

out.write(String.valueOf(i));//可能是编码的原因，如果直接写入int的话，将出现java编码和windows编码的混乱，因此此处写入的是String

public static void main(String[] ars){

A ab= new B();//执行到此处,结果: 1a2b

ab= new B();//执行到此处,结果: 1a2b2b

}注:类的static代码段,可以看作是类首次加载(被虚拟机加载)执行的代码,而对于类的加载,首先要执行其基类的构造,再执行其本身的构造

(1)接口可以被多重implements,抽象类只能被单一extends(2)接口只有定义,抽象类可以有定义和实现(3)接口的字段定义默认为:publicstatic final,抽象类字段默认是"friendly"(本包可见)

当功能需要累积时用抽象类，不需要累积时用接口。

通过类(Class对象)，可以得出当前类的fields、method、construtor、interface、superClass、modified等，同是可以通过类实例化一个实例、设置属性、唤醒方法。Spring中一切都是返射、struts、hibernate都是通过类的返射进行开发的。

20、类的返射机制中的包及核心类?

①java.lang.Class②java.lang.refrection.Method③java.lang.refrection.Field

④java.lang.refrection.Constructor⑤java.lang.refrection.Modifier⑥java.lang.refrection.Interface

21、得到Class的三个过程是什么?

①对象.getClass()②类.class或Integer.type(int) Integer.class(java.lang.Integer)③Class.forName();

①产生一个Class数组，说明方法的参数②通过Class对象及方法参数得到Method③通过method.invoke(实例,参数值数组)唤醒方法

23、如何将数值型字符转换为数字（Integer，Double）？

Integer.parseInt(“1234”) Double.parseDouble(“123.2”)

25、如何去小数点前两位，并四舍五入。

double d=1256.22d; d=d/100; System.out.println(Math.round(d)*100);

26、如何取得年月日，小时分秒？

Calendar c=Calendar.getInstance();

c.set(Calendar.DAY_OF_MONTH,31);

System.out.println(c.get(Calendar.YEAR)+""+(c.get(Calendar.MONTH)+1)+""+c.get(Calendar.DAY_OF_MONTH));

27、如何取得从1970年到现在的毫秒数

Java.util.Date dat=new Date(); long now=dat.getTime();

28、如何获取某个日期是当月的最后一天？

当前日期加一天，若当前日期与结果的月份不相同，就是最后一天。

取下一个月的第一天，下一个月的第一天-1

public static void main(String[] args){

Calendarc=Calendar.getInstance();

c.set(Calendar.DAY_OF_MONTH,30);

Calendarc1=(Calendar)c.clone();

System.out.println(c.get(Calendar.YEAR)+""+(c.get(Calendar.MONTH)+1)+""+c.get(Calendar.DAY_OF_MONTH));

c.add(Calendar.DAY_OF_MONTH,1);

if(c.get(Calendar.MONTH)!=c1.get(Calendar.MONTH)){

System.out.println("是最后一天");

System.out.println("不是取后一天");

Import java.text. SimpleDateFormat;

SimpleDateFormat sdf=newSimpleDateFormat("yyyy-MM-dd hh:mm:ss");

String str=sdf.format(dat);//把日期转化为字符串

Java.util.Date d1=sdf.parse(“yyyy-mm-dd”);//将字符串转化为日期

30、编码转换，怎样实现将GB2312编码的字符串转换为ISO-8859-1编码的字符串。

String a=new String("中".getBytes("gb2312"),"iso-8859-1");

String a=new String("中".getBytes("iso-8859-1"));

应该是String a=new String("中".getBytes("gb2312"),"iso-8859-1");

String a1=newString(a.getBytes("iso-8859-1"));