快捷導(dǎo)航

Java冒泡排序法和選擇排序法的實(shí)現(xiàn)

更新時間：2019年09月12日 09:56:43 作者：神經(jīng)大條蕾弟

這篇文章主要介紹了Java冒泡排序法和選擇排序法的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

冒泡排序法和選擇排序法

本人學(xué)生黨一枚。Java學(xué)習(xí)過程，寫這個博客純屬當(dāng)復(fù)習(xí)，有什么錯誤的地方請大家指出來在評論里指點(diǎn)指點(diǎn)我。謝謝

冒泡排序法

概念:

從前向后(或從后向前)依次比較相鄰的元素，若發(fā)現(xiàn)逆順序，則交換。小的向前換，大的向后換，像水底的氣泡逐漸向上冒，顧名思義冒泡排序法。

通俗一點(diǎn)就是把大的往上挪！向冒泡一樣。

是交換式排序法的一種。冒泡排序法效率較低。

冒泡過程

冒泡排序法思路

1：外層循環(huán)：控制它要走幾次。
假設(shè)你有5個數(shù)，那就要走4次，最后一次不用走，最后那個數(shù)已經(jīng)在它位置了所以就要length-1次。
2：內(nèi)層循環(huán)：控制逐一比較，如果發(fā)現(xiàn)前一個數(shù)比后一個數(shù)大，則交換。
注意！因?yàn)樵奖容^長度就越小了，所以長度要length-1-i。

package com.test_1;

public class Demo5_3 {

  public static void main(String[] args) {
    // TODO Auto-generated method stub

    int arr [ ] ={1,6,0,-1,9};
    int temp=0;//中間值
    //-------冒泡排序法
    //外層循環(huán),它決定一共走幾趟
    for(int i = 0;i<arr.length-1;i++){
      //內(nèi)層循環(huán),開始逐個比較
      //如果我們發(fā)現(xiàn)前一個數(shù)比后一個數(shù)大,則交換
      for(int j=0;j<arr.length-1-i;j++){
        if (arr[j]>arr[j+1]) {
          //換位
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }

    }
    //輸出結(jié)果
    for(int i = 0;i<arr.length;i++){
      System.out.print(arr[i]);
    }

  }

}

選擇排序法

概念：
第一次從R[0]~R[n-1]中選取最小值，與R[0]交換。第二次從R[1]~R[n-1]中選取最小值與R[1]交換。。。以此類推。
通俗點(diǎn)說就是每次找到后面元素的最小值然后與之交換。
選擇排序法效率中。

選擇排序過程

選擇排序思路
1：外層循環(huán)：要走幾趟，同樣是length-1。
2：設(shè)置一個最小值。假設(shè)第一個就是最小值。
3：設(shè)置一個最小值下標(biāo)
4：內(nèi)層循環(huán)：那你當(dāng)前的最小值去逐一比較。當(dāng)有比當(dāng)前最小值小的數(shù)時，記錄最小值，記錄下標(biāo)。
5：退出內(nèi)層循環(huán)后就交換位置。

package com.test_1;

public class Demo5_3 {

  public static void main(String[] args) {


    //簡單測試數(shù)組
    int arr [ ] ={1,6,0,-1,9,1000,-1000,98,-687};

    //調(diào)用選擇排序法
    Select select = new Select();
    select.sort(arr);
  }

}


//--------------選擇排序法
class Select{
  public void sort(int arr[]){
    //中間值
    int temp = 0;

    //外循環(huán):我認(rèn)為最小的數(shù),從0~長度-1
    for(int j = 0; j<arr.length-1;j++){
      //最小值:假設(shè)第一個數(shù)就是最小的
      int min = arr[j];
      //記錄最小數(shù)的下標(biāo)的
      int minIndex=j;

      //內(nèi)循環(huán):拿我認(rèn)為的最小的數(shù)和后面的數(shù)一個個進(jìn)行比較
      for(int k=j+1;k<arr.length;k++){
        //找到最小值
        if (min>arr[k]) {
          //修改最小
          min=arr[k];
          minIndex=k;
        }
      }
      //當(dāng)退出內(nèi)層循環(huán)就找到這次的最小值
      //交換位置
      temp = arr[j];
      arr[j]=arr[minIndex];
      arr[minIndex]=temp;
    }
    //輸出結(jié)果
    for(int i = 0;i<arr.length;i++){
      System.out.print(arr[i]+"  ");
    }

  }
}

最后再比較一下兩個排序法之間的效率差異：
代碼

package com.test_1;

import java.util.Calendar;

public class Demo5_3 {

  public static void main(String[] args) {

    //構(gòu)建一個龐大的無序數(shù)組用于測試時間
    int len=100000;
    int arr1 [] = new int [len];
    for(int i=0;i<len;i++){
      //讓程序隨機(jī)產(chǎn)生一個1~10000的數(shù)
      //Math.random()會產(chǎn)生一個0~1的數(shù)
      int t = (int)(Math.random()*10000);
      arr1[i] = t;
    }

    //簡單測試數(shù)組
    int arr [ ] ={1,6,0,-1,9,1000,-1000,98,-687};

    //獲得時間實(shí)例
    Calendar cal = Calendar.getInstance();

    //在排序前打印系統(tǒng)時間
    System.out.println("冒泡排序法開始"+cal.getTime());
    //調(diào)用冒泡排序法
    Bubble bubble = new Bubble();
    bubble.sort(arr1);
    //重新獲得時間實(shí)例
    cal = Calendar.getInstance();
    System.out.println("冒泡排序法結(jié)束"+cal.getTime());


    //重新獲得時間實(shí)例
    cal = Calendar.getInstance();
    System.out.println("選擇排序法開始"+cal.getTime());
    //調(diào)用選擇排序法
    Select select = new Select();
    select.sort(arr1);
    //重新獲得時間實(shí)例
    cal = Calendar.getInstance();
    System.out.println("選擇排序法結(jié)束"+cal.getTime());
  }

}

//-----------------冒泡排序法
class Bubble{
  //排序方法
  public void sort(int arr[]){
    int temp=0;//中間值
    //-------冒泡排序法
    //外層循環(huán),它決定一共走幾趟
    for(int i = 0;i<arr.length-1;i++){
      //內(nèi)層循環(huán),決定每一趟循環(huán)的次數(shù)
      //如果我們發(fā)現(xiàn)前一個數(shù)比后一個數(shù)大,則交換
      for(int j=0;j<arr.length-1-i;j++){
        if (arr[j]>arr[j+1]) {
          //換位
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }

    }  
    /*//輸出結(jié)果
        for(int i = 0;i<arr.length;i++){
          System.out.print(arr[i]+"  ");
        }*/
  }  
}


//--------------選擇排序法
class Select
{
  public void sort(int arr[])
  {
    //中間值
    int temp = 0;

    //外循環(huán):我認(rèn)為最小的數(shù),從0~長度-1
    for(int j = 0; j<arr.length-1;j++)
    {
      //最小值:假設(shè)第一個數(shù)就是最小的
      int min = arr[j];
      //記錄最小數(shù)的下標(biāo)的
      int minIndex=j;

      //內(nèi)循環(huán):拿我認(rèn)為的最小的數(shù)和后面的數(shù)一個個進(jìn)行比較找到下標(biāo)
      for(int k=j+1;k<arr.length;k++)
      {
        //找到最小值
        if (min>arr[k]) 
        {
          //修改最小
          min=arr[k];
          minIndex=k;
        }
      }
      //當(dāng)退出內(nèi)層循環(huán)就找到這次的最小值
      //交換位置
      temp = arr[j];
      arr[j]=arr[minIndex];
      arr[minIndex]=temp;
    }
    /*//輸出結(jié)果
    for(int i = 0;i<arr.length;i++){
      System.out.print(arr[i]+"  ");
    }*/

  }
}

運(yùn)行結(jié)果：