程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 冒泡排序的三種完成辦法

冒泡排序的三種完成辦法

編輯：關於C++

冒泡排序的三種完成辦法。本站提示廣大學習愛好者：（冒泡排序的三種完成辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是冒泡排序的三種完成辦法正文

冒泡排序長短常輕易懂得和完成，以從小到年夜排序舉例：

設數組長度為N。

1．比擬相鄰的前後二個數據，假如後面數據年夜於前面的數據，就將二個數據交流。

2．如許對數組的第0個數據到N-1個數據停止一次遍歷後，最年夜的一個數據就“沉”到數組第N-1個地位。

3．N=N-1，假如N不為0就反復後面二步，不然排序完成。

依照界說很輕易寫出代碼：

//冒泡排序1
void BubbleSort1(int a[], int n)
{
       int i, j;
       for (i = 0; i < n; i++)
              for (j = 1; j < n - i; j++)
                     if (a[j - 1] > a[j])
                            Swap(a[j - 1], a[j]);
}

上面對其停止優化，設置一個標記，假如這一趟產生了交流，則為true，不然為false。顯著假如有一趟沒有產生交流，解釋排序曾經完成。

//冒泡排序2
void BubbleSort2(int a[], int n)
{
       int j, k;
       bool flag;

       k = n;
       flag = true;
       while (flag)
       {
              flag = false;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = true;
                     }
              k--;
       }
}

再做進一步的優化。假如有100個數的數組，僅後面10個無序，前面90個都已排好序且都年夜於後面10個數字，那末在第一趟遍歷後，最初產生交流的地位一定小於10，且這個地位以後的數據一定曾經有序了，記載下這地位，第二次只需從數組頭部遍歷到這個地位便可以了。

//冒泡排序3
void BubbleSort3(int a[], int n)
{
int j, k;
int flag;

flag = n;
while (flag > 0)
{
  k = flag;
  flag = 0;
  for (j = 1; j < k; j++)
   if (a[j - 1] > a[j])
   {
    Swap(a[j - 1], a[j]);
    flag = j;
   }
}
}

冒泡排序究竟是一種效力低下的排序辦法，在數據范圍很小時，可以采取。數據范圍比擬年夜時，最好用其它排序辦法。

以隨意，只是方不便利罷了），然後便可以經由過程下面的文件生成我們須要的類文件了。
protoc --java_out=寄存源代碼的途徑 --proto_path=proto文件的途徑 proto詳細文件
--proto_path指定的是proto文件的文件夾途徑，其實不是單個文件，重要是為了import文件查找應用的，可以省略

如我須要把源代碼放在D:\protobufferVsJson\src，而我的proto文件寄存在D:\protoFiles
那末我的編譯敕令就是：

protoc --java_out=D:\protobufferVsJson\src 
D:\protoFiles\teacher.proto D:\protoFiles\student.proto

留意，這裡最初的文件，我們須要指定須要編譯的一切文件

編譯後可以看到生成的文件。
代碼就不貼出來了，太多了。年夜家可以暗裡看看，代碼外面有一年夜堆Builder，信任一看就曉得是建造者形式了。
這時候可以把代碼貼到你的項目中了，固然，毛病一堆了。

記得我們後面下載的源代碼嗎？解壓它吧，不要手軟。然後找到src/main/java/復制個中的一堆到你的項目，固然，你也能夠ant或許maven編譯，但這兩個器械我都不熟，就不獻丑了，我照樣習氣直接復制到項目中。

代碼失足，哈哈，正常。不曉得為什麼，GOOGLE非要留下這麼個坑給我們。
翻回到protobuffer目次下的\java看到有個readme.txt了吧，找到一句：

看來看去，感到這個代碼會有點奇異的，似乎錯錯的感到，橫豎我是沒按誰人履行，我的敕令是:

<span >protoc --java_out=照樣下面的放代碼的處所 proto文件的途徑（這裡是descriptor.proto文件的途徑）</span>

履行後，我們可以看到代碼中的毛病木有了。

3、接上去固然就是測試了。
我們先輩行GPB寫入測試：

package com.shun.test; 
 
import java.io.FileOutputStream; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 
 
import com.shun.StudentProto.Student; 
import com.shun.TeacherProto.Teacher; 
 
public class ProtoWriteTest { 
 
  public static void main(String[] args) throws IOException { 
     
    Student.Builder stuBuilder = Student.newBuilder(); 
    stuBuilder.setAge(25); 
    stuBuilder.setId(11); 
    stuBuilder.setName("shun"); 
     
    //結構List 
    List<Student> stuBuilderList = new ArrayList<Student>(); 
    stuBuilderList.add(stuBuilder.build()); 
     
    Teacher.Builder teaBuilder = Teacher.newBuilder(); 
    teaBuilder.setId(1); 
    teaBuilder.setName("testTea"); 
    teaBuilder.addAllStudentList(stuBuilderList); 
     
    //把gpb寫入到文件 
    FileOutputStream fos = new FileOutputStream("C:\\Users\\shun\\Desktop\\test\\test.protoout"); 
    teaBuilder.build().writeTo(fos); 
    fos.close(); 
  } 
 
}</span>

我們去看看文件，如有意外，應當是生成了的。
生成了以後，我們確定要讀回它的。

package com.shun.test; 
 
import java.io.FileInputStream; 
import java.io.FileNotFoundException; 
import java.io.IOException; 
 
import com.shun.StudentProto.Student; 
import com.shun.TeacherProto.Teacher; 
 
public class ProtoReadTest { 
 
  public static void main(String[] args) throws FileNotFoundException, IOException { 
     
    Teacher teacher = Teacher.parseFrom(new FileInputStream("C:\\Users\\shun\\Desktop\\test\\test.protoout")); 
    System.out.println("Teacher ID:" + teacher.getId() + ",Name:" + teacher.getName()); 
    for (Student stu:teacher.getStudentListList()) { 
      System.out.println("Student ID:" + stu.getId() + ",Name:" + stu.getName() + ",Age:" + stu.getAge()); 
    } 
  } 
 
}</span>

代碼很簡略，由於GPB生成的代碼都幫我們完成了。
下面曉得根本的用法了，我們重點來存眷GPB跟JSON生成文件年夜小的差別，JSON的具體代碼我這裡就不貼了，以後會貼出示例，年夜家有興致可以下載。
這裡我們用Gson來解析JSON，上面只給出對象轉換成JSON後寫出文件的代碼：
兩個類Student和Teacher的根本界說就不弄了，年夜家隨便就行，代碼以下：

package com.shun.test; 
 
import java.io.FileWriter; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 
 
import com.谷歌.gson.Gson; 
import com.shun.Student; 
import com.shun.Teacher; 
 
public class GsonWriteTest { 
 
  public static void main(String[] args) throws IOException { 
    Student stu = new Student(); 
    stu.setAge(25); 
    stu.setId(22); 
    stu.setName("shun"); 
     
    List<Student> stuList = new ArrayList<Student>(); 
    stuList.add(stu); 
     
    Teacher teacher = new Teacher(); 
    teacher.setId(22); 
    teacher.setName("shun"); 
    teacher.setStuList(stuList); 
     
    String result = new Gson().toJson(teacher); 
    FileWriter fw = new FileWriter("C:\\Users\\shun\\Desktop\\test\\json"); 
    fw.write(result); 
    fw.close(); 
  } 
 
}</span>

接上去正式進入我們的真正測試代碼了，後面我們只是在列表中放入一個對象，接上去，我們順次測試100,1000,10000,100000,1000000,5000000這幾個數目的GPB和JSON生成的文件年夜小。
改良一下之前的GPB代碼，讓它生成分歧數目的列表，再生成文件：

package com.shun.test; 
 
import java.io.FileOutputStream; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 
 
import com.shun.StudentProto.Student; 
import com.shun.TeacherProto.Teacher; 
 
public class ProtoWriteTest { 
 
  public static final int SIZE = 100; 
   
  public static void main(String[] args) throws IOException { 
     
    //結構List 
    List<Student> stuBuilderList = new ArrayList<Student>(); 
    for (int i = 0; i < SIZE; i ++) { 
      Student.Builder stuBuilder = Student.newBuilder(); 
      stuBuilder.setAge(25); 
      stuBuilder.setId(11); 
      stuBuilder.setName("shun"); 
       
      stuBuilderList.add(stuBuilder.build()); 
    } 
     
    Teacher.Builder teaBuilder = Teacher.newBuilder(); 
    teaBuilder.setId(1); 
    teaBuilder.setName("testTea"); 
    teaBuilder.addAllStudentList(stuBuilderList); 
     
    //把gpb寫入到文件 
    FileOutputStream fos = new FileOutputStream("C:\\Users\\shun\\Desktop\\test\\proto-" + SIZE); 
    teaBuilder.build().writeTo(fos); 
    fos.close(); 
  } 
 
}</span>

這裡的SIZE順次改成我們下面聽說的測試數，可以獲得以下：

然後我們再看看JSON的測試代碼：

package com.shun.test; 
 
import java.io.FileWriter; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 
 
import com.谷歌.gson.Gson; 
import com.shun.Student; 
import com.shun.Teacher; 
 
public class GsonWriteTest { 
 
  public static final int SIZE = 100; 
   
  public static void main(String[] args) throws IOException { 
     
    List<Student> stuList = new ArrayList<Student>(); 
    for (int i = 0; i < SIZE; i ++) { 
      Student stu = new Student(); 
      stu.setAge(25); 
      stu.setId(22); 
      stu.setName("shun"); 
       
      stuList.add(stu); 
    } 
     
     
    Teacher teacher = new Teacher(); 
    teacher.setId(22); 
    teacher.setName("shun"); 
    teacher.setStuList(stuList); 
     
    String result = new Gson().toJson(teacher); 
    FileWriter fw = new FileWriter("C:\\Users\\shun\\Desktop\\test\\json" + SIZE); 
    fw.write(result); 
    fw.close(); 
  } 
 
}</span>

異樣的辦法修正SIZE，並作響應的測試。

可以顯著得看到json的文件年夜小跟GPB的文件年夜小在數據量漸漸年夜上去的時刻就會有比擬年夜的差異了，JSON顯著要年夜上很多。

下面的表應當可以看得比擬清晰了，在年夜數據的GPB長短常占優勢的，但普通情形下客戶端和辦事端其實不會直接停止這麼年夜數據的交互，年夜數據重要產生在辦事器真個傳輸上，假如你面臨需求是天天須要把幾百M的日記文件傳到別的一台辦事器，那末這裡GPB能夠就可以幫你的年夜忙了。

說是深度比較，其實重要比較的是年夜小方面，時光方面可比性不會太年夜，也沒相差太年夜。
文章當選擇的Gson解析器，有興致的同伙可以選擇Jackson或許fastjson，又或許其他的，但生成的文件年夜小是一樣的，只是解析時光有差別。