java 排序(转载)

JAVA排序算法（非原创）

package Sort;
class Data {

Comparable key;

Object value;

public Data() {

}



public Data(Data data){

    this.key=data.key;

    this.value=data.value;

}



public Data(Comparable key,Object value){

    this.key=key;

    this.value=value;

}

public String toString(){

    return "key="+key+";"+"value="+value+";"+"\n";

}

}



Insertion.java

package Sort;

public class InsertionSort {

public InsertionSort() {

}

//直接插入排序,从下标1开始

public static void straightInsertionSort(Data[] data) {

    int i, j;

    for (i = 2; i <data.length; i++) {

      if (data[i].key.compareTo(data[i - 1].key) < 0) {

        data[0] = data[i];//复制为监视哨

        for (j = i - 1; data[0].key.compareTo(data[j].key) < 0; --j) {

          data[j + 1] = data[j];//记录右移

        }

        data[j + 1] = data[0];//插入

      }

    }

}



//折半插入排序,从下标1开始

public static void BinaryInsertionSort(Data[] data){

    int i,j,low,high,mid;

    for(i=2;i<data.length;i++){

      if (data[i].key.compareTo(data[i - 1].key) < 0) {

        data[0]=data[i];

        //找插入位置

        low=1;high=i-1;

        while(low<=high){

          mid =(low+high)/2;

          if(data[0].key.compareTo(data[mid].key)<0) high=mid-1;

          else low=mid+1;

        }

        //移动插入位置以后的元素

        for(j=i-1;j>=high+1;j--){

          data[j+1]=data[j];

        }

        data[high+1]=data[0];//插入

      }

    }

}



//表插入排序

public static void ListInsertionSort(Data[] data){

int i,j,k;

//inner class:Table

    class Table{

      Comparable key;

      int next;

    }

    Table[] table=new Table[data.length];

    for(i=1;i<data.length;i++){

      table[i]=new Table();

      table[i].key=data[i].key;

    }

    table[0]=new Table();

    table[0].key=new Integer(Integer.MAX_VALUE);

    table[0].next=1;

    table[1].next=0;

    for(i=2;i<data.length;i++){

      for(j=0,k=table[0].next;table[k].key.compareTo(table[i].key)<=0;j=k,k=table[k].next);

      table[j].next=i;

      table[i].next=k;

    }

    Data[] newData=new Data[data.length];

    int position=table[0].next;

    for(i=1;i<data.length;i++){

      newData[i]=data[position];

      position=table[position].next;

    }

    //data=newData;//不知为什么不能把newData赋给data，而必须用下面的

    for(i=1;i<data.length;i++){

      data[i]=newData[i];

    }

}

}



QuickSort.java

package Sort;

import Queue.*;



public class QuickSort {

public QuickSort() {

}



//起泡排序

public static void BubbleSort(Data[] data) {

    int i, j, lastChangeIndex;

    Data temp;

    i = data.length - 1;

    while (i > 1) {

      lastChangeIndex = 1;

      for (j = 1; j < i; j++) {

        if (data[j + 1].key.compareTo(data[j].key) < 0) {

          temp = data[j + 1];

          data[j + 1] = data[j];

          data[j] = temp;

          lastChangeIndex = j;

        }

      }

      i = lastChangeIndex;

    }

}



//快速排序

public static void QuickSort(Data[] data) {

    QSort(data, 1, data.length - 1);

}



public static void OptimizeQuickSort(Data[] data){

    OQSort(data,1,data.length-1);

}



private static void QSort(Data[] data, int s, int t) {

    int pivotLoc;

    if (s < t) {

      pivotLoc = Partition(data, s, t); //对data[1...data.length-1]进行一次划分

      QSort(data, s, pivotLoc - 1); //对低子序列进行递归排序

      QSort(data, pivotLoc + 1, t); //对高子序列进行递归排序

    }

}

private static void OQSort(Data[] data,int s,int t){

    int pivotLoc;

    if(s<t){

      pivotLoc=RandomPartition(data,s,t);

      QSort(data, s, pivotLoc - 1); //对低子序列进行递归排序

      QSort(data, pivotLoc + 1, t); //对高子序列进行递归排序

    }

}



private static int RandomPartition(Data[] data,int low,int high){

    //i是low

    int i=(int)Math.random()*(high-low)+low;

    Data temp=data[low];

    data[low]=data[i];

    data[i]=temp;

    return Partition(data,low,high);

}



private static int Partition(Data[] data, int low, int high) {

    Comparable pivotKey;

    data[0] = data[low];

    pivotKey = data[low].key; //枢轴

    while (low < high) {

      while (low < high && data[high].key.compareTo(pivotKey) >= 0) {

        high--;

      }

      data[low] = data[high];

      while (low < high && data[low].key.compareTo(pivotKey) <= 0) {

        low++;

      }

      data[high] = data[low];

    }

    data[low] = data[0];

    return low;

}



//堆排序

public static void HeapSort(Data[] data) {

    //先对顺序表进行堆排序，建立大顶堆

    int i;

    Data temp;

    for (i = (data.length-1)/2; i > 0; i--) {

      HeapAdjust(data, i, data.length-1);

    } //建立大顶堆



    for (i = (data.length - 1); i >1; i--) {

      temp = data[1];

      data[1] = data[i];

      data[i] = temp;

      HeapAdjust(data, 1, i - 1);

    }

}



private static void HeapAdjust(Data[] data, int start, int end) {

    int j;

    Data temp;

    temp = data[start];

    for (j = 2 * start; j <=end; j *=2) {

      if (j < end && data[j].key.compareTo(data[j+1].key) < 0) {

        j++;

      }

      if (temp.key.compareTo(data[j].key) >= 0) {

        break;

      }

      data[start] = data[j];

      start = j;

    }

    data[start] = temp;

}



//简单选择排序

public static void SimpleSelectSort(Data[] data) {

    int i, j;

    Data temp;

    for (i = 1; i < data.length; i++) {

      j = MinKey(data, i);

      if (j != i) {

        temp = data[i];

        data[i] = data[j];

        data[j] = temp;

      }

    }

}



private static int MinKey(Data[] data, int start) {

    int i, j = start;

    Comparable temp;

    temp = data[start].key;

    if (data.length - start == 0) {

      return start;

    }

    for (i = start + 1; i < data.length; i++) {

      if (temp.compareTo(data[i].key) > 0) {

        temp = data[i].key;

        j = i;

      }

    }

    return j;

}



//归并排序

private static Data[] originalnewData2;

private static Data[] newData2;

public static void MergingSort(Data[] data) {

    originalnewData2 = new Data[data.length];

    newData2 = new Data[data.length];

    for (int i = 1; i < data.length; i++) {

      originalnewData2[i]=new Data();

      newData2[i] = new Data();

    }

    MSort(data, data, 1, data.length - 1);

}



private static void MSort(Data[] originalData,Data[] data, int start,

                            int end) {

    if (start == end) {

      data[start] = originalData[start];

    }

    else {

      int mid = (start + end) / 2;

      MSort(originalData, newData2, start, mid);

      MSort(originalData, newData2, mid + 1, end);

      //怎样才能像值传递一样使用引用传递，即不改变它的值

      for(int k=start;k<=end;k++) originalnewData2[k]=new Data(newData2[k]);

      merge(originalnewData2, data, start, mid, end);//这里的data好像不再是一开始传入的data，而是递归时的newData2

    }

}



private static void merge(Data[] newData, Data[] data, int start, int mid,

                            int end) {

    int i, j;

    int k=start;

    for (i = start, j = mid + 1; start <= mid && j <= end; i++) {

      if (newData[start].key.compareTo(newData[j].key) <= 0) {

        data[i] = newData[start++];

      }

      else {

        data[i] = newData[j++];

      }

    }

    if (start <= mid) {

      for (int tempI = start; tempI <= mid; tempI++) {

        data[i++] = newData[tempI];

      }

    }

    if (j <= end) {

      for (int tempJ = j; tempJ <= end; tempJ++) {

        data[i++] = newData[tempJ];

      }

    }

}



//基数排序

public static void RadixSort(Data[] data,int digits){

    int d,j,k,factor=1;

    QueueInterface[] queues=new LinkQueue[10];

    for(int i=0;i<10;i++){

      queues[i]=new LinkQueue();

    }

    for(d=1;d<=digits;factor*=10,d++){

      //distribution

      for(j=1;j<data.length;j++){

        queues[(((Integer)data[j].key).intValue()/factor)%10].put(new Data(data[j]));

      }

      //collection

      for(j=0,k=1;j<10;j++){



        while(!queues[j].isEmpty()){

          data[k++]=(Data)queues[j].removeHead();

        }

      }

    }

}

}

测试类：

package Sort;



public class Test {

public Test() {

}

//产生测试数据

public static Data[] getData(int size){

    Data[] data=new Data[size+1];

    int number;

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

      number=(int) (Math.random() * size*10);

      data[i] = new Data(new Integer(number),new Integer(number));

    }

    return data;

}



//复制测试数据

public static Data[] duplicationData(Data[] data){

    Data[] duplication=new Data[data.length];

    for(int i=1;i<data.length;i++){

      duplication[i]=new Data(data[i]);

    }

    return duplication;

}



public static void printData(Data[] data){

    for(int i=1;i<data.length;i++)

      System.out.print(data[i].toString());

}



public static void main(String[] args) {

    long startTime,stopTime,sortingTime;

    Data[] data=getData(6000);

    Data[] data1,data2,data3,data4,data5,data6,data7,data8,data9,data10;

    data1=duplicationData(data);

    data2=duplicationData(data);

    data3=duplicationData(data);

    data4=duplicationData(data);

    data5=duplicationData(data);

    data6=duplicationData(data);

    data7=duplicationData(data);

    data8=duplicationData(data);

    data9=duplicationData(data);

    data10=duplicationData(data);





    startTime= System.currentTimeMillis();

    Sort.InsertionSort.straightInsertionSort(data1);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Straight Insertion Sort time is "+ sortingTime);

    //System.out.println("Straight Insertion Sort Answer");

    //printData(data1);





    startTime= System.currentTimeMillis();

    Sort.InsertionSort.BinaryInsertionSort(data2);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Binary Insertion Sort time is "+ sortingTime);

    //System.out.println("Binary Insertion Sort Answer");

    //printData(data2);



    startTime= System.currentTimeMillis();

    Sort.InsertionSort.ListInsertionSort(data3);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("List Insertion Sort time is "+ sortingTime);

    //System.out.println("List Insertion Sort Answer");

    //printData(data3);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.BubbleSort(data4);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Bubble Sort time is "+ sortingTime);

    //System.out.println("Bubble Sort Answer");

    //printData(data4);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.QuickSort(data5);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Quick Sort time is "+ sortingTime);

    //System.out.println("Quick Sort Answer");

    //printData(data5);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.SimpleSelectSort(data6);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Select Sort time is "+ sortingTime);

    //System.out.println("Select Sort Answer");

    //printData(data6);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.MergingSort(data7);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Merging Sort time is "+ sortingTime);

    //System.out.println("Merging Sort Answer");

    //printData(data7);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.RadixSort(data8,5);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Radix Sort time is "+ sortingTime);

    //System.out.println("Radix Sort Answer");

    //printData(data8);



    startTime= System.currentTimeMillis();

    Sort.QuickSort.HeapSort(data);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    //System.out.println("Heap Sort time is "+ sortingTime);

    //System.out.println("Radix Sort Answer");

    //printData(data9);

  

    startTime= System.currentTimeMillis();

    Sort.QuickSort.OptimizeQuickSort(data10);

    stopTime= System.currentTimeMillis();

    sortingTime=stopTime-startTime;

    System.out.println("Optimize Quick Sort time is "+ sortingTime);

    //System.out.println("Optimize Quick Sort Answer");

    //printData(data10);

}

}

测试结果：

各种排序的测试数据表：


数

据

长

度

时

间

排

序

类

型

100

500

1000

10000

直接插入排序

0

10

20

1752

二分插入排序

0

10

10

551

表插入排序

10

10

30

2153

起泡排序

10

30

50

5068

快排

0

0

10

20

简单选择排序

30

20

20

3535

归并排序

0

0

60

190

基数排序

20

20

110

140

堆排序

0

0

0

10

 

关于快排：

快速排序的运行时间与划分是否对称有关，最糟的情况是每次划分时一边是一个元素，一边是n-1个，这种情况的时间复杂度是

在最好的情况是，每次划分的枢轴都是中值，此时的时间复杂度是 ，在一些书上提到快速排序在平均情况下的复杂度也是 ，所以可以提出一个处理恶化的方法，在排序算法的每一步，可以随机选取一个元素关键字作为枢轴，这样总体来说平均划分是对称的。

可以把取枢轴的算法改一下：

int RandomizedPartition(DataType[] a , int p , int r){

       int i= Random(p , r);

       Swap(a[i] ,a[p]);

       return Partition(a,p,r);

}



500

1000

10000

100000

200000

普通快排

10

10

40

501

1181

优化快排

0

0

10

430

1142



可以看出，优化后的快排明显的提高了排序的速度，但是同时也可以看出，当元素很多时，交换的次数也增多了，使得优化后的排序的优势不很明显了，这是因为被排的数据是随机的。

下面显示的是这两种快排对有序的处理时间(数据>7000，内存溢出)：



100

500

1000

3000

6000

普通快排

10

10

80

250

991

优化快排

0

40

20

160

731



由此可知，优化快排能缓解恶化。