1 package exchange; 2  3 import java.util.Scanner; 4  5 /*算法思想：一趟快速排序是以一个“枢轴”，将序列分为两部分，枢轴的一边全比它小（或小于等于），一边全比它大（或大于等于）。接着 6  * 用同样的方法对这两部分进行排序，依次下去，经过几次这样的排序，最终得到一个有序的序列。通常都选第一个元素作为枢轴。 7  * 待排序的序列越接近无序，快速排序的效率越高，越接近有序，效率越低。 8  * 平均时间复杂度是O（nlog2(n)）[2是底],就平均时间而言，快速排序是所有排序算法中最好的，快速排序的趟数和初始序列有关 9  * 空间复杂度O(log2(n)) [2是底]，快排是递归进行的，递归需要栈的辅助。*/10 public class kuaisusort {11 12     public static void main(String[] args){13         Scanner cin = new Scanner(System.in);14         String str = cin.nextLine();15         String[] st = str.split(" ");16         int c[] = new int[st.length];17         for(int i=0;i<st.length;i++){18             c[i]=Integer.parseInt(st[i]);19         }20         sort(c,0,c.length-1);21         for(int i=0;i<c.length;i++){22             System.out.print(c[i]);23             System.out.print(" ");24         }25         cin.close();26     }27     public static void sort(int R[],int l,int r){28         int temp;29         int i = l,j = r;30         if(l<r){31             temp = R[0];32             while(i!=j){33                 while(j>i&&R[j]>temp)j--;//从右向左遍历找到一个小于temp的元素34                 if(l<j){35                     R[i]=R[j];36                     i++;37                 }38                 while(i<j&&R[i]<temp)i++;//从左向右遍历找到大于temp的元素39                 if(i<j){40                     R[j]=R[i];41                     j--;42                 }43             }44             R[i]=temp;//把temp放在最终的位置上45             sort(R,0,i-1);//递归对temp左边的元素进行排序46             sort(R,i+1,j);//递归对temp右边的元素进行排序47         }48     }49 }