三种简单排序算法及其对比代码：class ArraySort{private long[] a;private int nElems;public ArraySort(int max){a = new long[max];nElems=0;}public void insert(long value){a[nElems] = value;nElems++;}public void display(){for(int j = 0;j < nElems; j++){System.out.print(a[j] + " ");}System.out.println("");}//冒泡排序方法public void bubbleSort(){int out,in;for(out=nElems-1;out>1;out--) //外层循环（out指针向数组左方移动）{for (in=0;in<out ;in++ ) //内层循环（in指针向右方移动）{if(a[in]>a[in+1]) //不是左小右大的正确顺序？swap(in,in+1); //交换它们}}} //结束//选择排序方法public void selectSort(){int out, in, min;for(out=0; out<nElems-1; out++) //外层循环{min=out; //将最小值指定为out指针所指位置数值for(in=out+1; in<nElems; in++) //内层循环{if(a[in]<a[min]) //当前in指针的值比min所指的最小值更小吗？min=in; //将最小值重新指定为当前in指针所指数据}swap(out, min); //交换out和min的值}} //结束//插入排序方法public void insertSort(){int in, out;long temp;for(out=1; out<nElems; out++) //out是左边有序部分和右边无序部分的分界线{temp=a[out]; //将分界点数据保存到临时变量中in=out; //从out开始依次向右移动数据while(in>0 && a[in-1] >= temp) //直到移动到一个比out更小的数据时{a[in] = a[in-1]; //将数据向右移动一个位置--in; //in指针左移一个位置}a[in] = temp;}} //结束public void swap(int one,int two){long temp = a[one];a[one]=a[two];a[two]=temp;}public static void main(String[] args){int maxSize=10;ArraySort arr;arr=new ArraySort(maxSize);arr.insert(77);arr.insert(99);arr.insert(45);arr.insert(55);arr.insert(23);arr.insert(86);arr.insert(12);arr.insert(00);arr.insert(65);arr.insert(34);arr.display();arr.insertSort();arr.display();}};排序算法思路描述：public void bubbleSort()，外层for循环的计数器out从数组的最后开始，即out等于nElems-1，每经过一次循环out减一。
下标大于out的数据项都已经是拍好序的了。
变量out在每完成一次内部循环（计数器为in）后就左移一位，因此算法就不再处理那些已经排好序的数据了。
内层for循环计数器in从数组的最开始算起，即in=0，每完成一次内部循环体加一，当它等于out 时结束一次循环。
在内层for循环体中，数组下标为in和in+1的两个数据项进行比较，如果下标为in的数据项大于下标为in+1的数据项，则交换两个数据项。
public void selectSort()，外层循环用循环变量out，从数组开头开始（数组下标为0）向高位增长。
内层循环用循环变量in，从out所指位置开始，同样是向右移位。
在每一个in的新位置，数据项a[in]和a[min]进行比较。
如果a[in]更小，则min被赋值为in的值。
在内层循环的最后，min指向最小的数据项，然后交换out和min指向的数据向。
public void insertSort()，在外层的for循环中，out变量从1开始，向右移动。
它标记了未排序部分的最左端的数据。
而内层的while循环中，in变量从out变量开始，向左移动（复制），直到temp变量小于in所指的数组数据项，或者它已经不能再往左移动为止。
While循环的每一趟都向右移动了一个已排序的数据项。
几种排序的比较：冒泡排序：很容易写，但是一般不用，数据量很小时还是有些应用价值的。
选择排序：虽然交换次数降到最低，但比较次数依然很大，当数据量小，且交换相对于比较更耗时的情况下，可以应用它。
插入排序：数据量小或者基本有序时，插入算法是三者中最好的选择。
相对于随机数据，它一般比冒泡快一倍，比选择也略快一些。
因为它移动数据比交换数据耗费要小。
希尔排序：插入排序的缺点是复制的次数太多，如果数据开始时是相对有序的，那么插入排序的效率就能提高很多。
希尔排序基于插入排序，通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。
当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依此进行下去。
进行这些排序时数据项之间的间隔被称为增量，并且习惯上用字母h表示。
常用的话值序列用公式h=h*3+1产生。
希尔排序比插入排序快很多，原因是，当h值大的时时候，数据项每一趟排序需要移动的元素的个数很少，但是数据项移动的距离很长。
这是非常有效率的。
当h减小时，每一趟排序需要移动的元素的个数增多。
但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。
正是这两种情况的结合才使希尔排序效率这么高。
希尔排序的代码：class shellShort{private static long[] theArray;private static int nElems;public static void display(){System.out.print("A=");for (int j=0; j<nElems; j++){System.out.print(theArray[j] + " ");}System.out.println("");}public static void shellSort(){int inner,outer;long temp;int h = 1;while (h <= nElems/3) //find initial value of h{h = h*3 + 1;}while (h>0) //decreasing h, util h=1{//h-sort the filefor (outer=h; outer<nElems; outer+=h){temp = theArray[outer];inner = outer;// one subpass(eg 0,4,8)while (inner > h-1 && theArray[inner-h] >= temp){theArray[inner] = theArray[inner-h];inner -= h;}theArray[inner] = temp;}//end forh = (h-1)/3; //decrease h} //end while} //end shellSort()public static void main(String[] args){//System.out.println("Hello World!");theArray = new long[1000];for (int j=0; j<1000; j++){long n = (int)(ng.Math.random()*99);theArray[j] = n;nElems++;}//shellShort.display();System.out.println(new java.util.Date());shellShort.shellSort();System.out.println(new java.util.Date());//shellShort.display();}}快速排序：划分是快速排序的根本机制，划分数据就是把数据分为两组，使所有关键字大于特定值得数据项在一组，使所有关键字小于特定值的数据项在另一组。
划分算法由两个指针开始工作，两个指针分别指向数组的两头。
在左边的指针，leftPtr，向右移动，而在右边的指针，rightPtr，向左移动。
当leftPtr遇到比枢纽小的数据项时，它继续向右移，因为这个数据项的位置已经处在数组的正确一边了，但是当遇到比枢纽大的数据时，它就停下来。
类似地，当rightPtr 遇到大于枢纽的数据项时，它继续左移，但是当发现比枢纽小的数据项时，它就停下来。
这可以对两个指针用分别用一个循环来实现，当两个指针都指着数组的错误一方位置上的数据项，就交换这两个数据项。
然后重复之前的指针移动及数据项交换动作。
直到两个指针最终相遇的时候后，划分过程结束。
快速排序算法在大多数情况下都是最快的，执行时间为O（N*LogN）级。
快速排序算法本质上通过吧一个数组划分为两个子数组，然后递归地调用自身为每个子数组进行快速排序来实现的。
算法要解决的问题是选择合适的枢纽，并且对小的划分区域进行排序。
一般取数组左端、右端、中部的三个数中的中间值作为枢纽。
快速排序代码：class QuickSort2{private static long[] theArray;private static int nElems;public static void display(){System.out.print("A=");for (int j=0; j<nElems; j++){System.out.print(theArray[j] + " ");}System.out.println("");}public static void quickSort(){recQuickSort(0, nElems - 1);}public static void recQuickSort(int left, int right){int size = right-left+1;if (size <= 3) //manual sort if small{manualSort(left, right);}else//quick sort if large{long median = medianOf3(left, right); //median item//partition rangeint partition = partitionIt(left, right, median);recQuickSort(left, partition-1);//sort left siderecQuickSort(partition+1, right);//sort right side}} //end recQuickSort()public static long medianOf3(int left, int right){int center = (left+right)/2;//order left & centerif(theArray[left] > theArray[center])swap(left,center);//order left & rightif(theArray[left] > theArray[right])swap(left, right);//order right & centerif(theArray[center] > theArray[right])swap(center, right);swap(center, right-1); //put pivot on rightreturn theArray[right-1];}//end medianOf3()public static int partitionIt(int left, int right, long pivot){int leftPtr = left; //right of first elemint rightPtr = right-1; //left of pivotwhile (true){//find bigger itemwhile (theArray[++leftPtr] < pivot){;}//find smaller itemwhile (theArray[--rightPtr] > pivot){;}if (leftPtr >= rightPtr) //if pointers cross,partition done{break;}else//not crossed, so swap elementsswap(leftPtr, rightPtr);}//end while(true)swap(leftPtr, right-1); //restore pivotreturn leftPtr; //return pivot location}public static void swap(int dex1, int dex2) //swap two elements{long temp;temp = theArray[dex1];theArray[dex1] = theArray[dex2];theArray[dex2] = temp;}public static void manualSort(int left, int right){int size = right-left+1;if(size <= 1)return; //no necessary sortif(size == 2){ //2-sort left and rightif(theArray[left] > theArray[right])swap(left, right);return;}else{if(theArray[left] > theArray[right-1])swap(left, right-1);if(theArray[left] > theArray[right])swap(left, right);if(theArray[right-1] > theArray[right])swap(right-1, right);}}//end manualSort()public static void main(String[] args){//System.out.println("Hello World!");theArray = new long[16];for (int j=0; j<16; j++){long n = (int)(ng.Math.random()*199);theArray[j] = n;nElems++;}QuickSort2.display();//System.out.println(new java.util.Date());QuickSort2.quickSort();QuickSort2.display();}}。
