快捷導(dǎo)航

Java實(shí)現(xiàn)選擇排序算法的實(shí)例教程

更新時(shí)間：2016年05月04日 15:19:32 作者：飛翔的貓咪

這篇文章主要介紹了Java實(shí)現(xiàn)選擇排序算法的實(shí)例教程,選擇排序的時(shí)間復(fù)雜度為О(n²),需要的朋友可以參考下

選擇排序概念

選擇排序也是一種交換排序算法，和冒泡排序有一定的相似度，因此個(gè)人認(rèn)為選擇排序可以視為冒泡排序的一種改進(jìn)算法。它的思路是這樣的：
設(shè)現(xiàn)在要給數(shù)組arr[]排序，它有n個(gè)元素。
1對第一個(gè)元素（Java中，下標(biāo)為0）和第二個(gè)元素進(jìn)行比較，如果前者大于后者，那么它一定不是最小的，但是我們并不像冒泡排序一樣急著交換。我們可以設(shè)置一個(gè)臨時(shí)變量a，存儲這個(gè)目前最小的元素的下標(biāo)。然后我們把這個(gè)目前最小的元素繼續(xù)和第三個(gè)元素做比較，如果它仍不是最小的，那么，我們再修改a的值。如此直到和最后一個(gè)元素比較完，可以肯定a存儲的一定是最小的元素的下標(biāo)。
2.如果a的值不為0（初始值，即第一個(gè)元素的下標(biāo)），交換下標(biāo)為a和0的兩個(gè)元素。
3.重復(fù)上述過程，這次從下標(biāo)為1的元素開始比較，因?yàn)橄聵?biāo)為0的位置已經(jīng)放好了最小的元素了。
4.如此直到只剩下最后一個(gè)元素，可以肯定這個(gè)元素就是最大的了。
5.排序完成。
很顯然，這個(gè)算法也需要n-1輪排序。
需要注意的是，以上闡述的只是每次找最小值的辦法。實(shí)際上也可以每次找最大值，不過那就需要每次放到數(shù)組尾巴上了。

Java實(shí)現(xiàn)代碼：
SelectArray.java

package ch02;

public class SelectArray {
  // 數(shù)組
  private long[] arr;

  // 數(shù)組中有效數(shù)據(jù)的大小
  private int elems;

  // 默認(rèn)構(gòu)造函數(shù)
  public SelectArray() {
    arr = new long[50];
  }

  public SelectArray(int max) {
    arr = new long[max];
  }

  // 插入數(shù)據(jù)
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }

  // 顯示數(shù)據(jù)
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 選擇排序
  public void selectSort(){
    int min = 0;
    long tmp = 0L;
    for(int i = 0; i < elems -1; i++){
      min = i;
      for(int j = i + 1; j < elems; j++) {
        if(arr[j] < arr[min]) {
          min = j;
        }
      }
      tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
}

測試代碼：

package ch02;

public class TestSelectArray {

  public static void main(String[] args) {
    SelectArray sArr = new SelectArray();
    sArr.insert(89);
    sArr.insert(54);
    sArr.insert(667);
    sArr.insert(7);
    sArr.insert(12);
    sArr.insert(43);
    sArr.insert(12);

    sArr.display();
    sArr.selectSort();
    sArr.display();

  }

}

結(jié)果：

201654151524688.png (513×126)