快速排序，冒泡排序，选择排序是比较基础的排序方法，我通过随机生成一个大小1000的数组，然后使用内部类创建线程来比较耗费时间
首先快速排序算法：
快速排序算法其实也叫分治法, 其步骤大致可以分为这么几步:
1. 先从数列中取出一个数作为基准数Num(取得好的话, 是可以减少步骤的)
2. 分区, 将大于Num的数放在它的右边, 小于或等于它的数放在它的左边
3. 再对左右区间重复前两操作, 直到各个区间只有一个数为止.
这里是使用递归方式创建的快速排序
1publicstaticvoidkspxSort(int[] a,intlow,int hight) { 2intstart=low; 3intend=hight; 4intkey=a[low]; 5while(end>start) { 6//从end开始和key比较 7while(end>start&&a[end]>=key) { 8end--; 9 }10if(a[end]<=key) {11inttemp = a[end];12a[end] = a[start];13a[start] = temp; 14 }15while(end>start&&a[start]<=key) {16start++;1718 }19if(a[start]>=key) {20inttemp = a[start];21a[start]=a[end];22a[end]=temp;23 }242526 }2728//递归调用29if(start>low) {kspxSort(a,low,start-1);}30if(end
然后是冒泡排序
将要排序的一组数字进行遍历。
第一次遍历，将相邻的两个数字进行比较，直到这组数字全部比较完成，如果前面比后面的数字大，则进行交换位置，此时可以将最大的数字筛选出来，放到最后的位置上。
第二次遍历，将相邻的两个数字进行比较，直到这组数字全部比较完成，如果前面比后面的数字大，则进行交换位置，将这组数字里面第二大的数字筛选出来，放到倒数第二的位置上。
依次进行遍历，交换位置，直到排序完成。
1publicstaticvoidbubbleSort(int[] a) { 2intn = a.length; 3int temp; 4for(inti=0;ia[j+1]) { 9temp = a[j];10a[j] =a[j+1];11a[j+1] = temp;12 }13 }14 } 15}
然后是选择排序
将要排序的一组数字进行遍历。
第一次遍历，将第一个位置上的数字与后面的数字进行比较，如果后面的数字比第一个位置上的元素小，则将两个数字的位置进行交换。
第二次遍历，将第二个位置上的数字与后面的数字进行比较，如果后面的数字比第二个位置上的元素小，则将两个数字的位置进行交换。
依次进行遍历、位置交换，直到这组数字排序完成。
1publicstaticvoidselectSort(int[] a) { 2for(inti=0;ia[j]){11//给min重新赋值12min = j;13 }14 }1516//交换位置17if(min != i){18int temp;19temp = a[i];20a[i] = a[min];21a[min] = temp;22 }2324 }25}
然后再main方法主线程中中创建一个随机数组，大小100000；读者可以创建更大以便获得更好的效果；
1int[] arry=newint[100000]; 2for(inti=0;i<100000;i++) {3arry[i]= (int)(Math.random()*100000);4}
使用多线程调用
1newThread() {// 1.继承Thread类 2publicvoidrun() {// 2.重写run方法 3longt1 =new Date().getTime(); 4kspxSort(arry, 0, arry.length-1); 5longt2 =new Date().getTime(); 6System.out.println("快速排序消耗时间:"+(t2-t1)); 7 } 8}.start();// 4.开启线程 9new Thread() {10publicvoid run() {11longt1 =new Date().getTime();12 bubbleSort(arry);13longt2 =new Date().getTime();14System.out.println("冒泡排序消耗时间:"+(t2-t1));15 }16 }.start();17new Thread() {18publicvoid run() {19longt1 =new Date().getTime();20 selectSort(arry);21longt2 =new Date().getTime();22System.out.println("选择排序消耗时间:"+(t2-t1));23 }2425}.start();
结果如下：
快速排序消耗时间:33
选择排序消耗时间:2515
冒泡排序消耗时间:4227
相比较之下:快速排序最快，选择排序和冒泡排序相差不大，
在算法中用 0()函数 表示算法的时间效率与算法所处理的数据元素个数n函数关系的最常用函数是0()函数。
定义：
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，
T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=0(f(n)),称0(f(n)) 为算法的渐进时间复杂度，简称时间复杂度
对比三种算法，具体请看https://cloud.tencent.com/developer/article/1350860
首先冒泡排序是基于比较和交换的，比如我们要对n个数字排序，冒泡排序需要n-1次遍历，比如我们有10个数字，第一趟循环需要比较9次，第二趟循环需要比较8次，第三趟需要比较7次，以此类推，最后一趟需要1次比较。
f(10)=9+8+7+......+1 ，可以转为一个等差数列：
f(n)=(n-1)+(n-2)+(n-3)+......+1= (n-1)*n / 2 = 0.5n^2-0.5n
当n趋于无穷大时否f(n)=n^2/2
选择排序类似，但是最坏情况下，选则排序需要交换n-1次，冒泡排序需要交换n^2/2
快速排序
快速排序的递推式为：T(n)=max(T(q) + T(n-q-1)) +O(n)，q为切分长度，如果每次切分都刚好切分成两半，则 q==n-q-1， T(q)==T(n-q-1) ，则简化为 T(n)=2T(n/2)+O(n)。换一下加法项的位置，T(n)=O(n)+2T(n/2)，若 快速排序每次都会以2为低做裂变分解数组，所以最终推出来的渐近复杂度：Ο(nlog2n)
转载于:https://www.cnblogs.com/fmlyzp/p/10370470.html
