基本介紹
- 中文名：冒泡排序
基本介紹,算法原理,算法分析,代碼舉例,
基本介紹
它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。
Java冒泡排序是使用Java語言實現冒泡排序。
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
算法原理
冒泡排序算法的運作如下：（從後往前）
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
算法分析
時間複雜度
若檔案的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數和記錄移動次數均達到最小值：所以，冒泡排序最好的時間複雜度為。若初始檔案是反序的，需要進趟排序。每趟排序要進行
次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：
冒泡排序的最壞時間複雜度為。
綜上，因此冒泡排序總的平均時間複雜度為。
代碼舉例
排序,在命令行接受用戶輸入的N個數字,以-1作為結束標誌,並且-1不計算在內,對這些輸入的數字進行排序輸出,並計算平均數.要求自己寫排序算法,不用漢字,拼音做類名,注釋等等排序算法,不用漢字,拼音做類名,注釋等等import java.io.*;
public class main{
public static void main(String ARGs[]) throws IOException
{
int num[] = new int;
int i = 0;
int temp = 0;
int sum = 0;
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
temp = Integer.parseInt(buf.readLine());
if(temp != -1)
{
num[i] = temp;
i++;
sum += temp;
}
else
{
break;
}
}
System.out.println("平均數：" + (sum / (i - 1)));
PoPo popo = new PoPo(num, i);
popo.sort();
}
}java.io.*;
public class main{
public static void main(StringARGs[]) throws IOException
{
int num[] = new int;
int i = 0;
int temp = 0;
int sum = 0;
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
temp = Integer.parseInt(buf.readLine());
if(temp != -1)
{
num[i] = temp;
i++;
sum += temp;
}
else
{
break;
}
}
System.out.println("平均數：" + (sum / (i - 1)));
PoPo popo = new PoPo(num, i);
popo.sort();
}
}public class PoPo{
int num[] = new int;
int flag = 0;
int length = 0;
public PoPo()
{
}
public PoPo(int[] Num, int i)
{
for(int j = 0; j < i; j++)
{
this.num[j] = Num[j];
}
length = i;
}public void sort()
{
int i = 0;
int j = 0;
int temp = 0;
for(i = 0; i < length; i++)
{
for(j = i; j < length - 1; j++)
{
if(num[i] > num[j + 1])
{
temp = num[j + 1];
num[j + 1] = num[i];
num[i] = temp;
}
}
}
System.out.print("after sort:");
for(i = 0 ; i < length; i++)
System.out.print(num[i] + " ");
System.out.println("");
}
}
先編譯PoPo.java，在編譯main.java
執行主程式時，輸入一個數字敲個回車，輸入－1時結束。
第2種情況：public class Sort{
public static void sort(String arg)
{
String[] args=arg.split(",");
for(int i=0;i<args.length;i++)
{
for(int j=0;j<args.length-i-1;j++)
{
int a=Integer.parseInt(args[j]);
int b=Integer.parseInt(args[j+1]);
if(a>b)
{
a=a^b;
b=a^b;
a=a^b;
}
args[j]=String.valueOf(a);
args[j+1]=String.valueOf(b);
}
}
for(int i=0;i<9;i++)
{
System.out.print(args[i]+",");
}
}
public static void main(String[] args)
{
sort("2,10,3,50,78,22,34,30,65");
}
}
第3種情況：public class Sort{
public static void main(String args[])
{
int[] m =
{ 2, 8, 43, 3, 33 };
int[] n = sort(m);
for (int i = 0; i < m.length; i++)
{
System.out.println(n[i] + "\n");
}
}/* 冒泡排序算法 */
public static int[] sort(int[] m)
{
int intLenth = m.length;
/*執行intLenth次*/
for (int i = 0; i < intLenth; i++)
{
/*每執行一次，將最da的數排在後面*/
for (int j = 0; j < intLenth - i - 1; j++)
{
int a = m[j];
int b = m[j + 1];
if (a > b)
{
m[j] = b;
m[j + 1] = a;
}
}
}
return m;
}
}
public class main{
public static void main(String ARGs[]) throws IOException
{
int num[] = new int;
int i = 0;
int temp = 0;
int sum = 0;
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
temp = Integer.parseInt(buf.readLine());
if(temp != -1)
{
num[i] = temp;
i++;
sum += temp;
}
else
{
break;
}
}
System.out.println("平均數：" + (sum / (i - 1)));
PoPo popo = new PoPo(num, i);
popo.sort();
}
}java.io.*;
public class main{
public static void main(StringARGs[]) throws IOException
{
int num[] = new int;
int i = 0;
int temp = 0;
int sum = 0;
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
temp = Integer.parseInt(buf.readLine());
if(temp != -1)
{
num[i] = temp;
i++;
sum += temp;
}
else
{
break;
}
}
System.out.println("平均數：" + (sum / (i - 1)));
PoPo popo = new PoPo(num, i);
popo.sort();
}
}public class PoPo{
int num[] = new int;
int flag = 0;
int length = 0;
public PoPo()
{
}
public PoPo(int[] Num, int i)
{
for(int j = 0; j < i; j++)
{
this.num[j] = Num[j];
}
length = i;
}public void sort()
{
int i = 0;
int j = 0;
int temp = 0;
for(i = 0; i < length; i++)
{
for(j = i; j < length - 1; j++)
{
if(num[i] > num[j + 1])
{
temp = num[j + 1];
num[j + 1] = num[i];
num[i] = temp;
}
}
}
System.out.print("after sort:");
for(i = 0 ; i < length; i++)
System.out.print(num[i] + " ");
System.out.println("");
}
}
先編譯PoPo.java，在編譯main.java
執行主程式時，輸入一個數字敲個回車，輸入－1時結束。
第2種情況：public class Sort{
public static void sort(String arg)
{
String[] args=arg.split(",");
for(int i=0;i<args.length;i++)
{
for(int j=0;j<args.length-i-1;j++)
{
int a=Integer.parseInt(args[j]);
int b=Integer.parseInt(args[j+1]);
if(a>b)
{
a=a^b;
b=a^b;
a=a^b;
}
args[j]=String.valueOf(a);
args[j+1]=String.valueOf(b);
}
}
for(int i=0;i<9;i++)
{
System.out.print(args[i]+",");
}
}
public static void main(String[] args)
{
sort("2,10,3,50,78,22,34,30,65");
}
}
第3種情況：public class Sort{
public static void main(String args[])
{
int[] m =
{ 2, 8, 43, 3, 33 };
int[] n = sort(m);
for (int i = 0; i < m.length; i++)
{
System.out.println(n[i] + "\n");
}
}/* 冒泡排序算法 */
public static int[] sort(int[] m)
{
int intLenth = m.length;
/*執行intLenth次*/
for (int i = 0; i < intLenth; i++)
{
/*每執行一次，將最da的數排在後面*/
for (int j = 0; j < intLenth - i - 1; j++)
{
int a = m[j];
int b = m[j + 1];
if (a > b)
{
m[j] = b;
m[j + 1] = a;
}
}
}
return m;
}
}
