快速排序

快速排序
关键字: 快速排序
再一些面试中,我们经常被问到快速排序,你明白快速排序嘛?
首先来看一下快速排序的算法:
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
让我们看一看下面的例子吧!

Java代码
1、
package cy.arithmetic.quick;
public class Data {
private int value;
public Data(int value){
  this.value = value;
}
public int getValue() {
  return value;
}
public void setValue(int value) {
  this.value = value;
}

}

2、
package cy.arithmetic.quick;

import java.util.ArrayList;
import java.util.List;

/**
*
*
* 快速排序是对冒泡排序的一种改进。 它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，
* 其中一部分的所有数据都比另外一不部分的所有数据都要小，
* 然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行， 以此达到整个数据变成有序序列。
*
*
* @author Administrator
*
*/
public class QuickSort {
private ArrayList list;

public QuickSort(){
  list = new ArrayList();
}
public void addData(Data data) {
  if (null != data) {
   list.add(data);
  }
}
public int getSize(){
  return list.size();
}
private void checkListSize() {
  // 校验数组
  int size = 0;
  if (null != list) {
   size = list.size();
  }
  if (size < 3) {
   System.out.println("白痴，太简单了！！");
   System.exit(0);
  }
}

public void sort(int start, int end) {
  checkListSize();    // 校验
  int div = this.divList(start, end); 
  if((div - start) > 1){
   this.sort(start, div-1);
  }
  if((end - start) > 1){
   this.sort(div+1, end);
  }
 
}

private int divList(int start, int end) {
  /*
   * 将数据分割成两个部分。
   */
  int axis = start; //  轴的位置
  Data axis_data = (Data) list.get(axis);
 
  for(;start<end;){
  
   if(start == axis && axis < end){
    //  轴 == 前  与 end 比较
    Data end_data = (Data) list.get(end);
    if(axis_data.getValue() > end_data.getValue()){
     list.set(axis,end_data);  //修改 对应 的对象
     start++;
     axis = end;
    }
    else{
     end--;
    }
   }
   if(end == axis && axis > start){
    //  轴 == 末  与 start 比较
    Data start_data = (Data) list.get(start);
    if(start_data.getValue() > axis_data.getValue()){
     list.set(axis,start_data);  //修改 对应 的对象
     end--;
     axis = start;
    }
    else{
     start++;
    }
   }

  }
  if(start == end){
   list.set(axis, axis_data);  //  将值 还原回来啊！
  }
  return axis;
 
}

public void print(){
  for(int i=0; i<list.size(); i++){
   System.out.println(i + ":  " + ((Data)list.get(i)).getValue());
  }
}
}


3、

package cy.arithmetic.quick;

public class MainTest {


public static void main(String args[]){
  QuickSort s = new QuickSort();
  s.addData(new Data(3));
  s.addData(new Data(5));
  s.addData(new Data(1));
  s.addData(new Data(3));
  s.addData(new Data(1));
  s.sort(0, s.getSize()-1);
  s.print();
}
}