【2】数据结构与算法 —— 选择排序算法

选择排序分为简单选择排序和堆排序，下面看看两个算法直接的对比。

1、简单选择排序

简单选择排序法就是通过n-i此关键字间的比较，从n-i-1个记录中选出关键字最小的记录，并且和第i个记录交换。实现如下：

package com.sort.exe;

public class SelectSort {

  public  void selectSort(int[] arrs){
    int i,j,min=0;
    for( i=0;i<arrs.length;i++){
      //将第一个下标设为最小值；
      min=i;
      for( j=i+1;j<arrs.length;j++){
        //若第j个下标表示的值比 min表示的值小，就将下标j赋值给min;如此操作直到数组尾部
        if(arrs[min] > arrs[j])
          min=j;
      }
      //如果min改变了，说明找到了最小值
      if(min != i){
        int temp=arrs[i];
        arrs[i]=arrs[min];
        arrs[min]=temp;
      }
    }
  }
  
  public static void main(String[] args){
     int[] a={1,12,3,9,5,6,8}; 
     new SelectSort().selectSort(a);
     for(int i=0;i<a.length;i++){ 
       System.out.print(a[i]+" "); 
    } 
  }
}      

时间复杂度O（n^2）

2、堆排序