选择排序分简单选择排序和堆排序两种。
1.简单选择排序
基本思想：每一次从待排序的记录中选取关键字最小的记录，顺序放在已排好序的记录后面，直到全部记录排序完毕。
特点：时间复杂度为O（n*2），空间复杂度为O（1），不稳定。
简单排序代码：
public void selectionSort( int [] a ){ for ( int i = 0 ; i < a.length - 1 ; i ++ ) { int temp = a[i] ; int tempIndex = 0 ; for ( int j = i + 1 ; j < a.length; j ++ ) { if (a[j] < temp) { temp = a[j] ; tempIndex = j ; } } if (tempIndex > 0 ) { a[tempIndex] = a[i] ; a[i] = temp ; } } }
2.堆排序
基本步骤：a.先把一个无序序列建堆；
b.输出堆顶元素，调整剩余元素成新堆，直至序列有序。
特点：像插入排序算法，它是原地的；像合并排序，时间复杂度是O(nlgn)，即使最坏情况也是如此，这也是它与快速排序相比最大的优点
堆排序代码：
/** 堆排序 * @author het * @date 2010-8-7 */ public class HeapSort { /** * 测试 */ public static void main(String[] args) { int [] a = { 2 , 1 , 4 , 5 , 6 , 7 , 9 , 10 , 98 , 45 , 80 , 0 , 2 , 3333 }; HeapSort sort = new HeapSort(); sort.MaxHeapSort(a); for ( int i = 0 ; i < a.length; i ++ ) { System.out.print(a[i] + " " ); } } /** * 交换数组中指定的两元素的位置 * PS:Java中的基本元素是不支持传址的，必须是对象或数组才能传址（引用） */ public void swap( int [] data, int x, int y) { int temp = data[x]; data[x] = data[y]; data[y] = temp; } /** * 保持堆的性质（非递归） */ private void MaxHeapify( int []a , int i , int n){ int index = 2 * i + 1 ; // 先记录i的左孩子 boolean isMax = false ; int temp = a[i]; while (index <= n && ! isMax){ if ( index < n && a[index] < a[index + 1 ] ) { // 如果右孩子比左孩子更大，用index记录右孩子下标 index ++ ; } if (temp > a[index]) { isMax = true ; } else { // 将大者上移 a[i] = a[index]; i = index ; index = 2 * i + 1 ; } } a[i] = temp ; } /** * 保持堆的性质（递归） */ private void MaxHeapifyRecursion( int [] a , int i , int n){ int lchild = 2 * i + 1 ; // i的左孩子的下标 int rchild = lchild + 1 ; // i的右孩子的下标 int largest = i ; // 记录 a[i],a[lchild],a[rchild]中的最大者的下标 if (lchild <= n && a[lchild] > a[largest]) { largest = lchild ; } if (rchild <= n && a[rchild] > a[largest]) { largest = rchild ; } // 交换 if (largest != i ) { swap(a, largest, i); // 为保持堆的性质，对有孩子的节点继续向下迭代 if (largest <= n / 2 ){ MaxHeapifyRecursion(a, largest , n); } } } /** * 建堆,时间复杂度为O(n) */ private void CreateHeap( int [] a){ int length = a.length - 1 ; // 数组元素的最大下标 // 自a[a.length/2]以后都是叶子节点，故对之前的非叶子节点都调用一次MaxHeapify以建堆 for ( int i = length / 2 ; i >= 0 ; i -- ) { MaxHeapify(a, i,length); // MaxHeapifyRecursion(a, i, length); } } /** * 堆排序（最大堆），得到升序序列,时间复杂度为O（nlgn） */ public void MaxHeapSort( int [] a){ CreateHeap(a); // 输出堆顶元素(交换堆顶元素a[0]与a[a.length-1])，并把剩下的元素调整成一个新堆 for ( int i = a.length - 1 ; i > 0 ; i -- ) { swap(a, 0 , i); MaxHeapify(a, 0 ,i - 1 ); // MaxHeapifyRecursion(a, 0, i-1); } }}
转载于:https://www.cnblogs.com/afirefly/archive/2010/07/18/1780063.html
