package org.rev.algorithm;

/**
 * 选择排序，算法复杂度O(n^2)，算法步骤如下：
 * 
 * 1. 对于一组数列，选出最小的数和第一个位置的数交换。
 * 
 * 2. 在剩余的数中，选出最小的数，与第二个位置的数交换。
 * 
 * 3. 如此循环，直到倒数第二个数与最后一个数比较位置。
 * 
 */
public class SelectionSort {

  public static void main(String[] args) {
    int[] data = {39, 11, 38, 97, 86, 37, 12, 4, 51, 18};
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("排序之后：");
    ss.printData(data);
  }

  /**
   * 选择排序，每次都遍历，都把最小的数放在前面。
   * 
   * @param data 待排序的数组
   */
  public void selectionSort(int[] data) {

    for (int i = 0; i < data.length; i++) {
      int min = i; // 记录最小值的索引

      for (int j = i + 1; j < data.length; j++) { // 在剩余的待排序数列中找到最小的数
        if (data[j] < data[min]) {
          min = j; // 找出最小值的索引
        }
      }
      // 如果最小值的位置发生了变化则交换
      if (min != i) {
        swap(data, i, min);
      }
      System.out.print("第" + (i + 1) + "次后的顺序：\t");
      printData(data);
    }

  }


  /*
   * 交换数组中两个元素的位置
   */
  private void swap(int[] data, int i, int min) {
    int tmp = data[i];
    data[i] = data[min];
    data[min] = tmp;
  }

  /*
   * 打印输出数组中的数据
   */
  private void printData(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }

}

选择排序(JAVA)