Java實現選擇排序算法的實例教程

2019-11-26 14:23:09

字體：大中小

來源：轉載

供稿：網友

選擇排序概念

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

Java實現代碼：
SelectArray.java

package ch02;public class SelectArray {  // 數組  private long[] arr;  // 數組中有效數據的大小  private int elems;  // 默認構造函數  public SelectArray() {    arr = new long[50];  }  public SelectArray(int max) {    arr = new long[max];  }  // 插入數據  public void insert(long value) {    arr[elems] = value;    elems++;  }  // 顯示數據  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();  }}

結果：

201654151524688.png (513×126)