欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

排序算法的Java實(shí)現(xiàn)全攻略

 更新時(shí)間：2015年08月06日 16:04:49   作者：zinss26914  
這篇文章主要介紹了排序算法的Java實(shí)現(xiàn),包括Collections.sort()的使用以及各種經(jīng)典算法的Java代碼實(shí)現(xiàn)方法總結(jié),超級(jí)推薦!需要的朋友可以參考下

Collections.sort()

Java的排序可以用Collections.sort() 排序函數(shù)實(shí)現(xiàn)。
用Collections.sort方法對(duì)list排序有兩種方法：
第一種是list中的對(duì)象實(shí)現(xiàn)Comparable接口，如下：

/**
* 根據(jù)order對(duì)User排序
*/
public class User implements Comparable<User>{
  private String name;
  private Integer order;
  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public Integer getOrder() {
    return order;
  }
  public void setOrder(Integer order) {
    this.order = order;
  }
  public int compareTo(User arg0) {
    return this.getOrder().compareTo(arg0.getOrder());
  }
}

測(cè)試一下：

public class Test{

  public static void main(String[] args) {
    User user1 = new User();
    user1.setName("a");
    user1.setOrder(1);
    User user2 = new User();
    user2.setName("b");
    user2.setOrder(2);
    List<User> list = new ArrayList<User>();
    //此處add user2再add user1
    list.add(user2);
    list.add(user1);
    Collections.sort(list);
    for(User u : list){
      System.out.println(u.getName());
    }
  }
}

輸出結(jié)果如下

a
b

第二種方法是根據(jù)Collections.sort重載方法來(lái)實(shí)現(xiàn)，例如：

/**
* 根據(jù)order對(duì)User排序
*/
public class User { //此處無(wú)需實(shí)現(xiàn)Comparable接口
  private String name;
  private Integer order;
  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public Integer getOrder() {
    return order;
  }
  public void setOrder(Integer order) {
    this.order = order;
  }
}

主類中這樣寫即可：

public class Test{
  public static void main(String[] args) {
    User user1 = new User();
    user1.setName("a");
    user1.setOrder(1);
    User user2 = new User();
    user2.setName("b");
    user2.setOrder(2);
    List<User> list = new ArrayList<User>();
    list.add(user2);
    list.add(user1);
    
    Collections.sort(list,new Comparator<User>(){
      public int compare(User arg0, User arg1) {
        return arg0.getOrder().compareTo(arg1.getOrder());
      }
    });
    for(User u : list){
      System.out.println(u.getName());
    }
  }
}

輸出結(jié)果如下

a
b

前者代碼結(jié)構(gòu)簡(jiǎn)單，但是只能根據(jù)固定的屬性排序，后者靈活，可以臨時(shí)指定排序項(xiàng)，但是代碼不夠簡(jiǎn)潔

擇優(yōu)用之。

常用排序算法
下面來(lái)看幾種經(jīng)典排序算法的Java代碼實(shí)踐：

冒泡排序

   

 public static void bubbleSort(int A[], int n) { 
    int i, j; 
     
    for (i = 0; i < n - 1; i ++) { 
      for (j = 0; j < n - i - 1; j ++) { 
        if (A[j] > A[j + 1]) { 
          A[j] = A[j] ^ A[j + 1]; 
          A[j + 1] = A[j] ^ A[j + 1]; 
          A[j] = A[j] ^ A[j + 1]; 
        } 
      } 
    } 
  }

 

直接插入排序

    

public static void insertSort(int A[], int n) { 
    int i, j, tmp; 
   
    for (i = 1; i < n; i++) { 
      tmp = A[i]; 
   
      for (j = i - 1; j >= 0; j--) { 
        if (A[j] > tmp) { 
          A[j + 1] = A[j]; 
        } else { 
          break; 
        } 
      } 
   
      A[j + 1] = tmp; 
    } 
  }

 

直接選擇排序

    

public static void selectSort(int A[], int n) { 
    int i, j, loc; 
   
    for (i = 0; i < n; i++) { 
      loc = i; 
   
      for (j = i + 1; j < n; j++) { 
        if (A[j] < A[loc]) { 
          loc = j; 
        } 
      } 
   
      if (loc != i) { 
        A[i] = A[i] ^ A[loc]; 
        A[loc] = A[i] ^ A[loc]; 
        A[i] = A[i] ^ A[loc]; 
      } 
    } 
  }

 

堆排序

 

  /** 
   * 堆排序（從小到大） 
   * 
   * @param A 
   * @param n 
   */ 
  public static void heapSort(int A[], int n) { 
    int tmp; 
   
    // 構(gòu)建大根堆 
    buildMaxHeap(A, n); 
   
    for (int j = n - 1; j >= 1; j--) { 
      tmp = A[0]; 
      A[0] = A[j]; 
      A[j] = tmp; 
   
      maxheapIfy(A, 0, j); 
    } 
  } 
   
  /** 
   * 構(gòu)建大根堆 
   * 
   * @param A 
   * @param n 
   */ 
  private static void buildMaxHeap(int A[], int n) { 
    for (int i = (n - 2) / 2; i >= 0; i--) { 
      maxheapIfy(A, i, n); 
    } 
  } 
   
  /** 
   * 維護(hù)從下標(biāo)i開始的最大堆 
   * 
   * @param A 
   * @param i 
   * @param n 
   */ 
  private static void maxheapIfy(int A[], int i, int n) { 
    int left, right, loc; 
   
    while (i < n) { 
      left = 2 * i + 1; 
      right = 2 * i + 2; 
      loc = i; 
   
      if (left < n && A[left] > A[i]) { 
        i = left; 
      } 
   
      if (right < n && A[right] > A[i]) { 
        i = right; 
      } 
   
      if (loc != i) { 
        A[i] = A[loc] ^ A[i]; 
        A[loc] = A[loc] ^ A[i]; 
        A[i] = A[loc] ^ A[i]; 
      } else { 
        break; 
      } 
    } 
  }

 

快速排序

 

  public static void quickSort(int A[], int bt, int ed) { 
    if (bt < ed) { 
      int pivot = pivotPartition(A, bt, ed); 
   
      quickSort(A, bt, pivot - 1); 
   
      quickSort(A, pivot + 1, ed); 
    } 
  } 
   
  private static void swapVar(int A[], int bt, int ed) { 
    int mid = bt + (ed - bt) / 2; 
   
    if (mid != bt) { 
      A[bt] = A[bt] ^ A[mid]; 
      A[mid] = A[bt] ^ A[mid]; 
      A[bt] = A[bt] ^ A[mid]; 
    } 
  } 
   
  private static int pivotPartition(int A[], int bt, int ed) { 
    // 取中間值作為stand，防止數(shù)組有序出現(xiàn)O(n^2)情況 
    swapVar(A, bt, ed); 
   
    int stand = A[bt]; 
   
    while (bt < ed) { 
      while (bt < ed && A[ed] >= stand) { 
        ed--; 
      } 
      if (bt < ed) { 
        A[bt++] = A[ed]; 
      } 
   
      while (bt < ed && A[bt] <= stand) { 
        bt++; 
      } 
      if (bt < ed) { 
        A[ed--] = A[bt]; 
      } 
    } 
   
    A[bt] = stand; 
   
    return bt; 
  }

歸并排序

  

 public static void mergeSort(int A[], int bt, int ed) { 
    if (bt < ed) { 
      int mid = bt + (ed - bt) / 2; 
   
      mergeSort(A, bt, mid); 
   
      mergeSort(A, mid + 1, ed); 
   
      mergeArray(A, bt, mid, ed); 
    } 
  } 
   
  private static void mergeArray(int A[], int bt, int mid, int ed) { 
    int i, j, k, len = ed - bt + 1; 
    int tmp[] = new int[len]; 
   
    for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) { 
      if (A[i] <= A[j]) { 
        tmp[k] = A[i++]; 
      } else { 
        tmp[k] = A[j++]; 
      } 
    } 
   
    while (i <= mid) { 
      tmp[k++] = A[i++]; 
    } 
   
    while (j <= ed) { 
      tmp[k++] = A[j++]; 
    } 
   
    for (i = 0; i < k; i++) { 
      A[bt + i] = tmp[i]; 
    } 
  }

 

測(cè)試程序

 來(lái)將以上算法歸納總結(jié)一下：

 import java.util.Scanner; 
   
  public class JavaSort { 
    public static void main(String args[]) { 
      Scanner cin = new Scanner(System.in); 
   
      int A[], n; 
   
      while (cin.hasNext()) { 
        n = cin.nextInt(); 
        A = new int[n]; 
   
        for (int i = 0; i < n; i++) { 
          A[i] = cin.nextInt(); 
        } 
   
        // bubbleSort(A, n); 
   
        // insertSort(A, n); 
   
        // selectSort(A, n); 
   
        // heapSort(A, n); 
   
        // quickSort(A, 0, n - 1); 
   
        mergeSort(A, 0, n - 1); 
   
        printArr(A); 
      } 
    } 
   
    /** 
     * 歸并排序 
     * 
     * @param A 
     * @param bt 
     * @param ed 
     */ 
    public static void mergeSort(int A[], int bt, int ed) { 
      if (bt < ed) { 
        int mid = bt + (ed - bt) / 2; 
   
        mergeSort(A, bt, mid); 
   
        mergeSort(A, mid + 1, ed); 
   
        mergeArray(A, bt, mid, ed); 
      } 
    } 
   
    /** 
     * 合并數(shù)組 
     * 
     * @param A 
     * @param bt 
     * @param mid 
     * @param ed 
     */ 
    private static void mergeArray(int A[], int bt, int mid, int ed) { 
      int i, j, k, len = ed - bt + 1; 
      int tmp[] = new int[len]; 
   
      for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) { 
        if (A[i] <= A[j]) { 
          tmp[k] = A[i++]; 
        } else { 
          tmp[k] = A[j++]; 
        } 
      } 
   
      while (i <= mid) { 
        tmp[k++] = A[i++]; 
      } 
   
      while (j <= ed) { 
        tmp[k++] = A[j++]; 
      } 
   
      for (i = 0; i < k; i++) { 
        A[bt + i] = tmp[i]; 
      } 
    } 
   
    /** 
     * 快速排序 
     * 
     * @param A 
     * @param bt 
     * @param ed 
     */ 
    public static void quickSort(int A[], int bt, int ed) { 
      if (bt < ed) { 
        int pivot = pivotPartition(A, bt, ed); 
   
        quickSort(A, bt, pivot - 1); 
   
        quickSort(A, pivot + 1, ed); 
      } 
    } 
   
    private static void swapVar(int A[], int bt, int ed) { 
      int mid = bt + (ed - bt) / 2; 
   
      if (mid != bt) { 
        A[bt] = A[bt] ^ A[mid]; 
        A[mid] = A[bt] ^ A[mid]; 
        A[bt] = A[bt] ^ A[mid]; 
      } 
    } 
   
    /** 
     * 快排尋找基準(zhǔn)點(diǎn)位置 
     * 
     * @param A 
     * @param bt 
     * @param ed 
     * @return 
     */ 
    private static int pivotPartition(int A[], int bt, int ed) { 
      // 取中間值作為stand，防止數(shù)組有序出現(xiàn)O(n^2)情況 
      swapVar(A, bt, ed); 
   
      int stand = A[bt]; 
   
      while (bt < ed) { 
        while (bt < ed && A[ed] >= stand) { 
          ed--; 
        } 
        if (bt < ed) { 
          A[bt++] = A[ed]; 
        } 
   
        while (bt < ed && A[bt] <= stand) { 
          bt++; 
        } 
        if (bt < ed) { 
          A[ed--] = A[bt]; 
        } 
      } 
   
      A[bt] = stand; 
   
      return bt; 
    } 
   
    /** 
     * 堆排序（從小到大） 
     * 
     * @param A 
     * @param n 
     */ 
    public static void heapSort(int A[], int n) { 
      int tmp; 
   
      // 構(gòu)建大根堆 
      buildMaxHeap(A, n); 
   
      for (int j = n - 1; j >= 1; j--) { 
        tmp = A[0]; 
        A[0] = A[j]; 
        A[j] = tmp; 
   
        maxheapIfy(A, 0, j); 
      } 
    } 
   
    /** 
     * 構(gòu)建大根堆 
     * 
     * @param A 
     * @param n 
     */ 
    private static void buildMaxHeap(int A[], int n) { 
      for (int i = (n - 2) / 2; i >= 0; i--) { 
        maxheapIfy(A, i, n); 
      } 
    } 
   
    /** 
     * 維護(hù)從下標(biāo)i開始的最大堆 
     * 
     * @param A 
     * @param i 
     * @param n 
     */ 
    private static void maxheapIfy(int A[], int i, int n) { 
      int left, right, loc; 
   
      while (i < n) { 
        left = 2 * i + 1; 
        right = 2 * i + 2; 
        loc = i; 
   
        if (left < n && A[left] > A[i]) { 
          i = left; 
        } 
   
        if (right < n && A[right] > A[i]) { 
          i = right; 
        } 
   
        if (loc != i) { 
          A[i] = A[loc] ^ A[i]; 
          A[loc] = A[loc] ^ A[i]; 
          A[i] = A[loc] ^ A[i]; 
        } else { 
          break; 
        } 
      } 
    } 
   
    /** 
     * 直接選擇排序 
     * 
     * @param A 
     * @param n 
     */ 
    public static void selectSort(int A[], int n) { 
      int i, j, loc; 
   
      for (i = 0; i < n; i++) { 
        loc = i; 
   
        for (j = i + 1; j < n; j++) { 
          if (A[j] < A[loc]) { 
            loc = j; 
          } 
        } 
   
        if (loc != i) { 
          A[i] = A[i] ^ A[loc]; 
          A[loc] = A[i] ^ A[loc]; 
          A[i] = A[i] ^ A[loc]; 
        } 
      } 
    } 
   
    /** 
     * 直接插入排序 
     * 
     * @param A 
     * @param n 
     */ 
    public static void insertSort(int A[], int n) { 
      int i, j, tmp; 
   
      for (i = 1; i < n; i++) { 
        tmp = A[i]; 
   
        for (j = i - 1; j >= 0; j--) { 
          if (A[j] > tmp) { 
            A[j + 1] = A[j]; 
          } else { 
            break; 
          } 
        } 
   
        A[j + 1] = tmp; 
      } 
    } 
   
    /** 
     * 冒泡排序 
     * 
     * @param A 
     * @param n 
     */ 
    public static void bubbleSort(int A[], int n) { 
      int i, j; 
   
      for (i = 0; i < n - 1; i++) { 
        for (j = 0; j < n - i - 1; j++) { 
          if (A[j] > A[j + 1]) { 
            A[j] = A[j] ^ A[j + 1]; 
            A[j + 1] = A[j] ^ A[j + 1]; 
            A[j] = A[j] ^ A[j + 1]; 
          } 
        } 
      } 
    } 
   
    /** 
     * 打印數(shù)組 
     * 
     * @param A 
     */ 
    public static void printArr(int A[]) { 
      for (int i = 0; i < A.length; i++) { 
        if (i == A.length - 1) { 
          System.out.printf("%d\n", A[i]); 
        } else { 
          System.out.printf("%d ", A[i]); 
        } 
      } 
    } 
  }

相關(guān)文章

  • java控制臺(tái)實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)

    java控制臺(tái)實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了java控制臺(tái)實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2022-02-02
  • 淺談一下Java的雙親委派模式

    淺談一下Java的雙親委派模式

    這篇文章主要介紹了一下Java的雙親委派模式,雙親委派指得是，JVM在加載類時(shí)，會(huì)委派給ExtClassLoader和BootstrapClassLoader進(jìn)?加載，如果沒加載到才由??進(jìn)?加載,需要的朋友可以參考下
    2023-04-04
  • Spring Boot實(shí)現(xiàn)圖片上傳/加水印一把梭操作實(shí)例代碼

    Spring Boot實(shí)現(xiàn)圖片上傳/加水印一把梭操作實(shí)例代碼

    這篇文章主要給大家介紹了關(guān)于Spring Boot實(shí)現(xiàn)圖片上傳/加水印一把梭操作的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • java8傳函數(shù)方法圖文詳解

    java8傳函數(shù)方法圖文詳解

    在本篇文章中小編給大家整理了關(guān)于java8傳函數(shù)方法和相關(guān)知識(shí)點(diǎn)，需要的朋友們學(xué)習(xí)下。
    2019-04-04
  • zookeeper實(shí)戰(zhàn)之實(shí)現(xiàn)分布式鎖的方法

    zookeeper實(shí)戰(zhàn)之實(shí)現(xiàn)分布式鎖的方法

    Zookeeper實(shí)現(xiàn)分布式鎖比Redis簡(jiǎn)單，Zookeeper有一個(gè)特性，多個(gè)線程在Zookeeper里創(chuàng)建同一個(gè)節(jié)點(diǎn)時(shí)，只有一個(gè)線程執(zhí)行成功，Zookeeper主要是利用臨時(shí)有序節(jié)點(diǎn)這一特性實(shí)現(xiàn)分布式鎖，感興趣的朋友跟隨小編一起學(xué)習(xí)吧
    2022-11-11
  • java實(shí)現(xiàn)把對(duì)象數(shù)組通過(guò)excel方式導(dǎo)出的功能

    java實(shí)現(xiàn)把對(duì)象數(shù)組通過(guò)excel方式導(dǎo)出的功能

    本文主要介紹了java實(shí)現(xiàn)把對(duì)象數(shù)組通過(guò)excel方式導(dǎo)出的功能的相關(guān)知識(shí)。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧
    2017-03-03
  • java多線程-同步塊實(shí)例講解

    java多線程-同步塊實(shí)例講解

    本文主要介紹java多線程-同步塊的知識(shí)，這里整理了相關(guān)的詳細(xì)資料及簡(jiǎn)單示例代碼，有興趣的小伙伴可以參考下
    2016-09-09
  • JavaSE實(shí)戰(zhàn)之酒店訂房系統(tǒng)的實(shí)現(xiàn)

    JavaSE實(shí)戰(zhàn)之酒店訂房系統(tǒng)的實(shí)現(xiàn)

    這篇文章主要為大家詳細(xì)介紹了如何利用JavaSE實(shí)現(xiàn)酒店訂房系統(tǒng)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)JavaSE開發(fā)有一定的幫助，需要的可以參考一下
    2022-07-07
  • Spring中的EventListenerMethodProcessor組件詳解

    Spring中的EventListenerMethodProcessor組件詳解

    這篇文章主要介紹了Spring中的EventListenerMethodProcessor組件詳解,EventListenerMethodProcessor 是 Spring 事件機(jī)制中非常重要的一個(gè)組件,它管理了一組EventListenerFactory組件,用來(lái)將應(yīng)用中每個(gè)使用@EventListener注解定義的事件監(jiān)聽,需要的朋友可以參考下
    2023-12-12
  • SpringBoot?使用log4j2的配置過(guò)程

    SpringBoot?使用log4j2的配置過(guò)程

    這篇文章主要介紹了SpringBoot?使用log4j2的配置,springboot默認(rèn)是用logback的日志框架的，所以要在pom中配置排除logback。這里需要注意的是，其實(shí)不止一處使用了logback，所以要在starter中統(tǒng)一排除，然后引入log4j2，需要的朋友可以參考下
    2022-09-09

最新評(píng)論