久久久久久久综合综合狠狠,免费a级毛片18禁网站免费

腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

java簡單冒泡排序?qū)嵗馕?/h1>

更新時(shí)間：2021年08月27日 09:19:13 作者：五歲i

這篇文章主要為大家詳細(xì)介紹了java簡單冒泡排序?qū)嵗?，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一、算法原理

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

二、實(shí)現(xiàn)思路

用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。假如有n個(gè)數(shù)需要進(jìn)行排序，則外循環(huán)重復(fù)n-1次，內(nèi)循環(huán)依次重復(fù)n-1，n-2，...，1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用a[j]和a[j+1]標(biāo)識(shí)，i的值依次為1,2,...,n-1，對(duì)于每一個(gè)i，j的值依次為0,1,2,...n-i 。

設(shè)數(shù)組長度為N：

1．比較相鄰的前后二個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個(gè)數(shù)據(jù)交換。
2．這樣對(duì)數(shù)組的第0個(gè)數(shù)據(jù)到N-1個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第N-1個(gè)位置。
3．N=N-1，如果N不為0就重復(fù)前面二步，否則排序完成。

三、代碼實(shí)現(xiàn)

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
 * 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
 * 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
 * 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交換兩數(shù)位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

四、性能分析

若記錄序列的初始狀態(tài)為"正序"，則冒泡排序過程只需進(jìn)行一趟排序，在排序過程中只需進(jìn)行n-1次比較，且不移動(dòng)記錄；反之，若記錄序列的初始狀態(tài)為"逆序"，則需進(jìn)行n（n-1)/2次比較和記錄移動(dòng)。因此冒泡排序總的時(shí)間復(fù)雜度為O(n*n)。

五、算法優(yōu)化

冒泡排序法存在的不足及改進(jìn)方法：

第一、在排序過程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無法判斷是否完成排序，為了解決這一不足，可設(shè)置一個(gè)標(biāo)志位flag，將其初始值設(shè)置為true，表示被排序的表是一個(gè)無序的表，每一次排序開始前設(shè)置flag值為true，在進(jìn)行數(shù)據(jù)交換時(shí)，修改flag為false。在新一輪排序開始時(shí)，檢查此標(biāo)志，若此標(biāo)志為false，表示上一次沒有做過交換數(shù)據(jù)，則結(jié)束排序；否則進(jìn)行排序；

第二、在冒泡排序中，一趟掃描有可能無數(shù)據(jù)交換，也有可能有一次或多次數(shù)據(jù)交換，在傳統(tǒng)的冒泡排序算法及近年來的一些改進(jìn)的算法中，只記錄一趟掃描有無數(shù)據(jù)交換的信息，對(duì)數(shù)據(jù)交換發(fā)生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對(duì)每一反序數(shù)據(jù)對(duì)進(jìn)行局部冒泡排序處理，稱之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時(shí)間復(fù)雜度，并且在正序和逆序的情況下，所需的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)完全相同。由于局部冒泡排序和冒泡排序的數(shù)據(jù)移動(dòng)次數(shù)總是相同的，而局部冒泡排序所需關(guān)鍵字的比較次數(shù)常少于冒泡排序，這意味著局部冒泡排序很可能在平均比較次數(shù)上對(duì)冒泡排序有所改進(jìn)，當(dāng)比較次數(shù)較少的優(yōu)點(diǎn)不足以抵消其程序復(fù)雜度所帶來的額外開銷，而當(dāng)數(shù)據(jù)量較大時(shí)，局部冒泡排序的時(shí)間性能則明顯優(yōu)于冒泡排序。對(duì)于N個(gè)無序數(shù)據(jù)，我們?cè)谶M(jìn)行一趟冒泡排序時(shí)，如果第k個(gè)數(shù)據(jù)和第k+1個(gè)數(shù)據(jù)逆序，那么對(duì)第k+1個(gè)數(shù)據(jù)進(jìn)行一趟向前的冒泡排序，使其移動(dòng)到合適的位置，也就是說讓前面k+1個(gè)數(shù)據(jù)調(diào)節(jié)為正序。因?yàn)檫@種冒泡法只對(duì)前k+1個(gè)數(shù)據(jù)冒泡處理，所以我們稱它為——局部冒泡

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交換兩數(shù)位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: