排序算法在程序中會(huì)用到很多，這里介紹幾種常見的排序方法以及比較

冒泡排序：對(duì)一個(gè)隊(duì)列里的數(shù)據(jù)，挨個(gè)進(jìn)行輪詢和交換，每次輪詢出一個(gè)當(dāng)前最大或者最小的值放在隊(duì)尾，然后繼續(xù)下次輪詢，輪詢長(zhǎng)度-1，就跟冒泡一樣，所以稱為冒泡排序，運(yùn)算時(shí)間復(fù)雜度N平方

選擇排序：對(duì)一個(gè)隊(duì)列里的數(shù)據(jù)，選出當(dāng)前最大或者最小的值，然后將他與隊(duì)首的數(shù)據(jù)交換，然后從第二個(gè)開始，進(jìn)行相同的操作，運(yùn)算時(shí)間復(fù)雜度N平方，但由于他不像冒泡一樣需要不停的交換位置，所以會(huì)比冒泡快一些

插入排序：對(duì)一個(gè)隊(duì)列里的數(shù)據(jù)，從第二個(gè)開始，與此位置之前的數(shù)據(jù)進(jìn)行比較，形成局部有序的隊(duì)列，循環(huán)此操作，直到隊(duì)尾，運(yùn)算時(shí)間復(fù)雜度依然為N平方，但他由于保證了局部的有序性，所以比較的次數(shù)會(huì)更少一些，相對(duì)前兩種會(huì)更快

希爾排序：其實(shí)就是用步長(zhǎng)控制的插入排序，希爾排序通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進(jìn)行插入排序，從而讓數(shù)據(jù)項(xiàng)可以大幅度移動(dòng)，這樣的方式可以使每次移動(dòng)之后的數(shù)據(jù)離他們?cè)谧罱K序列中的位置相差不大，保證數(shù)據(jù)的基本有序，大大提升了排序速度，運(yùn)算時(shí)間復(fù)雜度N*logN

快速排序：對(duì)一個(gè)隊(duì)列，以他隊(duì)尾的數(shù)據(jù)為基準(zhǔn)值，先劃分成兩塊數(shù)據(jù)，一塊都大于這個(gè)值，一塊小于這個(gè)值，然后對(duì)這兩塊進(jìn)行同樣的操作，這是最快的排序方法，運(yùn)算時(shí)間復(fù)雜度N*logN

下面是代碼：

 public static void sort(int[] a)
 {
  long time1,time2;
  int c;
  time1=System.currentTimeMillis();
//  /*冒泡排序*/
//  for(int i=a.length-1;i>1;i--)
//  {
//   for(int j=0;j<i;j++)
//   {
//
//    if(a[j]<a[j+1])
//    {
//     c=a[j];
//     a[j]=a[j+1];
//     a[j+1]=c;
//    }
//   }
//  }
//  /*選擇排序*/
//  int pos=0;
//  for(int i=0;i<a.length-2;i++)
//  {
//   for(int j=i;j<a.length-1;j++)
//   {
//    if(a[pos]<a[j+1])
//     pos=j+1;
//   }
//   c=a[i];
//   a[i]=a[pos];
//   a[pos]=c;
//   pos=i+1;
//  }
//  /*插入排序*/
//  for(int i=1;i<a.length;i++)
//  {
//   c=a[i];
//   int m=i-1;
//   while(m>=0&&a[m]<c)
//   {
//    a[m+1]=a[m];
//    m--;
//   }
//   a[m+1]=c;
//  }
//  /*希爾排序*/
//  int h=1;
//  int m=0;
//  while(3*h+1<a.length)
//   h=3*h+1;
//  while(h>0)
//  {
//   for(int i=h;i<a.length;i++)
//   {
//    c=a[i];
//    m=i-h;
//    while(m>=0&&a[m]<c)
//    {
//     a[m+h]=a[m];
//     m-=h;
//    }
//    a[m+h]=c;
//    
//   }
//   h=(h-1)/3;
//  }
  /*快速排序*/
  provide(a,0,a.length-1);
  time2=System.currentTimeMillis();
  System.out.println("time:"+(time2-time1));
 }
 /*遞歸調(diào)用劃分*/
 public static void provide(int[] a,int left,int right)
 {
  try
  {
   if(right<=left)
    return;
   else
   {
    /*設(shè)置基準(zhǔn)點(diǎn)*/
    int prov=a[right];
    /*取得劃分中斷點(diǎn)*/
    int par=partitionIt(a,left,right,prov);
    /*對(duì)劃分后的兩邊再次劃分*/
    provide(a,left,par-1);
    provide(a,par+1,right);
    
   }
  }
  catch(Exception e)
  {
   System.out.println("eer:"+left+"."+right);
  }
 }
 /*劃分算法*/
 public static int partitionIt(int[] a,int left,int right,int prov)
 {
  /*設(shè)置左右端點(diǎn)的指針*/
  int leftP=left-1;
  int rightP=right;
  int c;//用于交換的中間變量
  /*當(dāng)左右指針未相遇時(shí)繼續(xù)操作*/
  while(leftP<rightP)
  {
   /*當(dāng)左指針的數(shù)據(jù)小于基準(zhǔn)值時(shí)跳出*/
   while(leftP<a.length-1&&a[++leftP]>prov)
    ;
   /*當(dāng)右指針的數(shù)據(jù)大于基準(zhǔn)值時(shí)跳出*/
   while(rightP>leftP&&a[--rightP]<prov)
    ; 
   /*左右指針都停下時(shí)交換數(shù)據(jù)*/
   c=a[leftP];
   a[leftP]=a[rightP];
   a[rightP]=c;
  } 
  /*劃分結(jié)束，將基準(zhǔn)點(diǎn)與指針的相遇點(diǎn)交換*/
  c=a[rightP];
  a[rightP]=a[right];
  a[right]=c; 
  return leftP;
 }