1、介绍。
冒泡排序（BubbleSort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序是稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(n) 最差情况：O(n^2) 平均情况：O(n^2)。
2、步骤。
(1)比较相邻的元素。如果第一个比第二个大，就交换他们两个。 (2)对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 (3)针对所有的元素重复以上的步骤，除了最后一个。 (4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3、代码。
publicstaticvoidmain(String[]args){System.out.println("------开始------");//生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。finalintnumber=100000;int[]sortArray=newint[number];int[]sortArrayCopy=newint[number];for(inti=0;i<sortArray.length;i++){sortArray[i]=(int)(Math.random()*number);}System.arraycopy(sortArray,0,sortArrayCopy,0,number);//数组复制Arrays.sort(sortArrayCopy);//开始排序longstartTime=System.currentTimeMillis();bubbleSort(sortArray);//冒泡排序System.out.println("花费时间："+(System.currentTimeMillis()-startTime));//跟系统排序之后数组进行比较，查看是否排序成功。if(Arrays.equals(sortArray,sortArrayCopy)){System.out.println("排序成功");}else{System.out.println("排序失败");}System.out.println("------结束------");}//冒泡排序最佳情况：T(n)=O(n)最差情况：T(n)=O(n2)平均情况：T(n)=O(n2)privatestaticvoidbubbleSort(int[]array){for(inti=1;i<array.length;i++){//n-1轮最后一个无序排序booleanfinish=true;for(intk=0;k<array.length-i;k++){//每轮次数都会减少if(array[k]>array[k+1]){finish=false;//交换位置intflag=array[k];array[k]=array[k+1];array[k+1]=flag;}}if(finish){//本轮没有产生交换，说明后面的不需要排序了break;}}}
4、结果。
二、快速排序
1、介绍。
快速排序由C.A.R.Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是不稳定排序，不需要额外内存，空间复杂度O(logn)。时间复杂度，最佳情况：O(nlogn) 最差情况：O(n^2) 平均情况：O(nlogn)。
2、步骤。
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
3、代码。
publicstaticvoidmain(String[]args){System.out.println("------开始------");//生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。finalintnumber=100000;int[]sortArray=newint[number];int[]sortArrayCopy=newint[number];for(inti=0;i<sortArray.length;i++){sortArray[i]=(int)(Math.random()*number);}System.arraycopy(sortArray,0,sortArrayCopy,0,number);//数组复制Arrays.sort(sortArrayCopy);//开始排序longstartTime=System.currentTimeMillis();quickSort(sortArray,0,sortArray.length-1);System.out.println("花费时间："+(System.currentTimeMillis()-startTime));//跟系统排序之后数组进行比较，查看是否排序成功。if(Arrays.equals(sortArray,sortArrayCopy)){System.out.println("排序成功");}else{System.out.println("排序失败");}System.out.println("------结束------");}//快速排序最佳情况：T(n)=O(nlogn)最差情况：T(n)=O(n2)平均情况：T(n)=O(nlogn) privatestaticvoidquickSort(int[]array,intstart,intend){if(start<end){inti=start;intk=end+1;intcompareValue=array[start];//跳出循环的条件是i>=k//如果i==k的话，就说明array[i]==array[k]==compareValue//如果i==k+1的话，就说明array[i]>=compare>=array[k]//所以最后array[k]要和compare再互换一下while(true){while(array[++i]<compareValue&&i<end);while(array[--k]>compareValue);if(i>=k){break;}else{intflag=array[i];array[i]=array[k];array[k]=flag;}}intflag=array[start];array[start]=array[k];array[k]=flag;//quickSort(array,start,k-1);quickSort(array,k+1,end);}}
4、结果。
