冒泡算法：
（對一些部分有序的數(shù)組，效率高）
時間復(fù)雜度：n^2;
一般入門時是這樣寫的：
int [] datas= new int[]{6,5,4,3,2,1};
for (int i=0;i<datas.length;i++){
for (int j=0;j<datas.length-1;j++){
if (datas[j]>datas[j+1]){
int minV=datas[j];
datas[j]=datas[j+1];
datas[j+1]=minV;
}
}
}
for (int data : datas) {
System.out.print(data+" ");
}
得道結(jié)果是12346；沒問題；
但是加上打印每一步驟的結(jié)果值，發(fā)現(xiàn)還有些執(zhí)行相同的
多次，導(dǎo)致浪費計算次數(shù)。于是想到了優(yōu)化；
冒泡算法的優(yōu)化：
優(yōu)化1
1.首先是第二個for循環(huán)的總次數(shù)：
由打印的日志分析知道，每執(zhí)行一次內(nèi)層的循環(huán)一次，就可以將大的值給冒泡交換到最后面了。最大數(shù)，第一遍就給放到最后面了，因此可以不用再交換后面排好序的位置了。
由打印結(jié)果規(guī)律，歸納推導(dǎo)，發(fā)現(xiàn)外層遍歷的下標(biāo)剛好是內(nèi)層循環(huán)排好序的個數(shù)。于是內(nèi)層的遍歷可以在后面便利的總數(shù)減去外層遍歷下標(biāo)。
2.內(nèi)層循環(huán)遍歷時，有一個最小比對值，需要頻繁的申明，使用，再釋放。因此可以放到最外面，兩個循環(huán)的初始下標(biāo)計量也可以放入外邊統(tǒng)一聲明。
于是得到如下：
int [] datas= new int[]{6,5,4,3,2,1};
int change,m=0,n;
for (;m<datas.length;m++){
n=0;
for (;n<datas.length-1;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
}
System.out.format("第 %d 遍的第%d 次交換：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
System.out.format("第 %d 遍最終結(jié)果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
}
結(jié)果是：
發(fā)現(xiàn)最后的結(jié)果明顯內(nèi)循環(huán)每次都減少了次數(shù)。
優(yōu)化2
但是如果數(shù)據(jù)是321456吶？
結(jié)果還是會走那么多次數(shù)，而且再有些步驟中就已經(jīng)排好序了，可是外層循環(huán)還要繼續(xù)排序。
于是，為了這個想去優(yōu)化問題，我們可以設(shè)置一個標(biāo)志位，用來表示當(dāng)前第m趟是否有交換，如果有則要進(jìn)行m+1 趟，如果沒有，則說明當(dāng)前數(shù)組已經(jīng)完成排序。實現(xiàn)代碼如下
int [] datas= new int[]{3,2,1,4,5,6};
int change,m=0,n;
boolean flag;
for (;m<datas.length;m++){
n=0;
flag=true;
for (;n<datas.length-1-m;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
//如果還有沒排好序的，將標(biāo)志位設(shè)置為false;
flag=false;
}
System.out.format("第 %d 遍的第%d 次交換：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
System.out.format("第 %d 遍最終結(jié)果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
//如果沒有要交換位置的，就證明排好序了，直接退出整個循環(huán)
if (flag){
return;
}
}
打印結(jié)果：
發(fā)現(xiàn)好多了，少外層的兩次循環(huán)。
優(yōu)化3
但是還有一個問題，就是上圖中，明明第二次遍歷，第一次的交換就已經(jīng)完成了，但是后面還要繼續(xù)交換，造成了一定的時間浪費。
對于這種問題，我們可以想到一個解決方案，利用一個標(biāo)志位，記錄一下當(dāng)前第m趟所交換的最后一個位置的下標(biāo)，在進(jìn)行第m+1 趟的時候，只需要內(nèi)循環(huán)到這個下標(biāo)的位置就可以了，因為后面位置上的元素在上一趟中沒有換位，這一次也不可能會換位置了?；谶@個規(guī)律，我們可以進(jìn)一步優(yōu)化我們的代碼：
int [] datas= new int[]{3,2,1,4,5,6};
int change,m=0,n,changelen=datas.length-1,tempIndex=0;
boolean flag;
for (;m<datas.length;m++){
n=0;
flag=true;
for (;n<changelen;n++){
if (datas[n]>datas[n+1]){
change=datas[n];
datas[n]=datas[n+1];
datas[n+1]=change;
//如果還有沒排好序的，將標(biāo)志位設(shè)置為false;
flag=false;
tempIndex=n;
}
System.out.format("第 %d 遍的第%d 次交換：", m+1,n+1);
for(int count:datas) {
System.out.print(count+" ");
}
System.out.println();
}
changelen=tempIndex;
System.out.format("第 %d 遍最終結(jié)果：", m+1);
for (int data : datas) {
System.out.print(data+" ");
}
System.out.println();
//如果沒有要交換位置的，就證明排好序了，直接退出整個循環(huán)
if (flag){
return;
}
}
打印結(jié)果：
從打印輸出來看，明顯減少了很多不必要的計算。比原來的更加優(yōu)良，減少了時間復(fù)雜度。
選擇排序：
（適用于無序不重復(fù)的數(shù)列）
時間復(fù)雜度：n^2;
原理：
第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
代碼：
public void selectSort(){
int change,m=0,n;
int [] datas= new int[]{8,1,48,92,12,77,66,6};
for (;m<datas.length;m++){
change=datas[m];
for (n=m+1;n<datas.length;n++){
if (datas[n]<change){
change=datas[n];
datas[n]=datas[m];
datas[m]=change;
}
}
}
for (int data : datas) {
System.out.print(data+" ");
}
}
打印結(jié)果：
1 6 8 12 48 66 77 92 ；
