关于排序之选择排序

选择排序：

分为直接选择排序， 堆排序

 

直接选择排序 ：第i次选取( i到array.Length-1中间)最小的值,放在i位置。

 

堆排序 ： 首先，数组里面用层次遍历的顺序放一棵完全二叉树。从最后一个非终端结点往前面调整，直到到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆 得条件了，于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走）。 主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap， 然后将heap的根放到后面去（即：每次的树大小会变化，但是 root都是在1的位置，以方便计算儿子们的index，所以如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。降序排列则要建立小顶 堆）

 

直接选择排序的源代码：

package com.zhaozy.sort;
 
import java.util.Random;
/**
 * 直接选择排序
 * @author zhaozy
 *
 */
public class StraitSelectionSort {
   public static void main(String[] args) {
     Random random = new Random();
     int [] dataset = new int [10];
     System. out .println( " 原始数据为： " );
     for ( int i = 0; i < dataset. length ; i++) {
        dataset[i] = ( int ) (random.nextDouble() * 100);
        System. out .print(dataset[i] + " " );
     }
     System. out .println();
     StraitSelectionSort strait = new StraitSelectionSort();
     for ( int i = 0; i < dataset. length ; i++) {
        // 找出 dataset [i] 之后小于它的值的下标
        int minIndex = strait.getMindIndex(dataset, i);
       // 和 dataset [i] 交换位置，如果之后没有比 dataset [i] 小的数，即 dataset [i] 和 dataset [i] 交换
        strait.exchange(dataset, i, minIndex);
     }
     System. out .println( " 排好序后： " );
     for ( int i = 0; i < dataset. length ; i++) {
        System. out .print(dataset[i] + " " );
     }
   }
   /*
    * 交换数组中某两个数值的位置的函数
    */
   public void exchange( int [] dataset, int i, int j) {
     if (i < dataset. length && j < dataset. length && i < j && i >= 0
          && j >= 0) {
        int temp = dataset[i];
        dataset[i] = dataset[j];
        dataset[j] = temp;
     }
   }
   /*
    * 找出 dataset [i] 之后小于它的值的下标
    */
   public int getMindIndex( int [] dataset, int i) {
     int minIndex = 0;
     int min = Integer. MAX_VALUE ;
     for ( int j = i; j < dataset. length ; j++) {
        if (dataset[j] < min) {
          min = dataset[j];
          minIndex = j;
        }
     }
     return minIndex;
   }
}

 

到目前为止，自己经历的笔试题中碰到过选择排序（具体方法任选，要是再让我做的话，我当然选择直接选择排序）和快速排序，听同学说他笔试的时候碰到过冒泡排序，不知道其他的排序碰到的几率大不大，以后慢慢看吧。