快速排序，冒泡排序，選擇排序是比較基礎(chǔ)的排序方法，我通過隨機(jī)生成一個(gè)大小1000的數(shù)組，然后使用內(nèi)部類創(chuàng)建線程來比較耗費(fèi)時(shí)間
首先快速排序算法：
快速排序算法其實(shí)也叫分治法, 其步驟大致可以分為這么幾步:
1. 先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)Num(取得好的話, 是可以減少步驟的)
2. 分區(qū), 將大于Num的數(shù)放在它的右邊, 小于或等于它的數(shù)放在它的左邊
3. 再對左右區(qū)間重復(fù)前兩操作, 直到各個(gè)區(qū)間只有一個(gè)數(shù)為止.
? 這里是使用遞歸方式創(chuàng)建的快速排序
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//遞歸調(diào)用29if(start>low) {kspxSort(a,low,start-1);}30if(end
?然后是冒泡排序
將要排序的一組數(shù)字進(jìn)行遍歷。
第一次遍歷，將相鄰的兩個(gè)數(shù)字進(jìn)行比較，直到這組數(shù)字全部比較完成，如果前面比后面的數(shù)字大，則進(jìn)行交換位置，此時(shí)可以將最大的數(shù)字篩選出來，放到最后的位置上。
第二次遍歷，將相鄰的兩個(gè)數(shù)字進(jìn)行比較，直到這組數(shù)字全部比較完成，如果前面比后面的數(shù)字大，則進(jìn)行交換位置，將這組數(shù)字里面第二大的數(shù)字篩選出來，放到倒數(shù)第二的位置上。
依次進(jìn)行遍歷，交換位置，直到排序完成。
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}
然后是選擇排序
將要排序的一組數(shù)字進(jìn)行遍歷。
第一次遍歷，將第一個(gè)位置上的數(shù)字與后面的數(shù)字進(jìn)行比較，如果后面的數(shù)字比第一個(gè)位置上的元素小，則將兩個(gè)數(shù)字的位置進(jìn)行交換。
第二次遍歷，將第二個(gè)位置上的數(shù)字與后面的數(shù)字進(jìn)行比較，如果后面的數(shù)字比第二個(gè)位置上的元素小，則將兩個(gè)數(shù)字的位置進(jìn)行交換。
依次進(jìn)行遍歷、位置交換，直到這組數(shù)字排序完成。
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方法主線程中中創(chuàng)建一個(gè)隨機(jī)數(shù)組，大小100000；讀者可以創(chuàng)建更大以便獲得更好的效果；
1int[] arry=newint[100000];? ? 2for(inti=0;i<100000;i++) {3arry[i]= (int)(Math.random()*100000);4}
???? 使用多線程調(diào)用
1newThread() {// 1.繼承Thread類 2publicvoidrun() {// 2.重寫run方法 3longt1 =new Date().getTime(); 4kspxSort(arry, 0, arry.length-1); 5longt2 =new Date().getTime(); 6System.out.println("快速排序消耗時(shí)間:"+(t2-t1)); 7? ? ? ? ? ? ? ? } 8}.start();// 4.開啟線程 9new Thread() {10publicvoid run() {11longt1 =new Date().getTime();12? ? ? ? ? ? ? ? bubbleSort(arry);13longt2 =new Date().getTime();14System.out.println("冒泡排序消耗時(shí)間:"+(t2-t1));15? ? ? ? ? ? }16? ? ? ? }.start();17new Thread() {18publicvoid run() {19longt1 =new Date().getTime();20? ? ? ? ? ? ? ? selectSort(arry);21longt2 =new Date().getTime();22System.out.println("選擇排序消耗時(shí)間:"+(t2-t1));23? ? ? ? ? ? }2425}.start();
結(jié)果如下：
快速排序消耗時(shí)間:33
選擇排序消耗時(shí)間:2515
冒泡排序消耗時(shí)間:4227
相比較之下:快速排序最快，選擇排序和冒泡排序相差不大，
在算法中用 0()函數(shù) 表示算法的時(shí)間效率與算法所處理的數(shù)據(jù)元素個(gè)數(shù)n函數(shù)關(guān)系的最常用函數(shù)是0()函數(shù)。
定義：
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，
T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=0(f(n)),稱0(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度
?? 對比三種算法，具體請看https://cloud.tencent.com/developer/article/1350860
?? 首先冒泡排序是基于比較和交換的，比如我們要對n個(gè)數(shù)字排序，冒泡排序需要n-1次遍歷，比如我們有10個(gè)數(shù)字，第一趟循環(huán)需要比較9次，第二趟循環(huán)需要比較8次，第三趟需要比較7次，以此類推，最后一趟需要1次比較。
f(10)=9+8+7+......+1 ，可以轉(zhuǎn)為一個(gè)等差數(shù)列：
f(n)=(n-1)+(n-2)+(n-3)+......+1= (n-1)*n / 2 = 0.5n^2-0.5n
當(dāng)n趨于無窮大時(shí)否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)。換一下加法項(xiàng)的位置，T(n)=O(n)+2T(n/2)，若 快速排序每次都會以2為低做裂變分解數(shù)組，所以最終推出來的漸近復(fù)雜度：Ο(nlog2n)
轉(zhuǎn)載于:https://www.cnblogs.com/fmlyzp/p/10370470.html
