常用排序算法总结(三)----选择排序 堆排序
SelectSort 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
算法的最差时间复杂度为O(n^2),最优为O(n^2),平均时间复杂度为O(n^2),空间复杂度为O(n),需要辅助空间O(1)
代码
[java] view plaincopyprint?
package Sort;
/**
* @author Biang Hoo
* O(n ^2 )
* 2013年9月10日
*/
public class SelectSort implements Sort{
@Override
public void Sorting(int[] array) {
int min;
int tmp;
for(int i=0;i<array.length;i++){
min=i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[min]){
min =j;
}
}
tmp =array[i];
array[i] =array[min];
array[min]=tmp;
}
}
}
HeapSort
堆排序是指利用堆设计的一种排序算法,近似一个完全二叉树的结构,父节点的键值总是大于子节点。
通常堆是利用一个数组实现的。在起始数组为0的情形中:
- 父节点i的左子节点在位置 (2*i+1);
- 父节点i的右子节点在位置 (2*i+2);
- 子节点i的父节点在位置 (i-1)/2;
在堆的数据结构中,堆中的最大(小)值总是位于根节点。堆中定义以下几种操作:
- 最大(小)堆调整(Max(min)_HeapAdjust):将堆的末端子节点作调整,使得父节点永远大(小)与子节点
- 创建最大(小)堆(Build_Max(Min)_Heap):将堆所有数据重新排序
- 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大(小)堆调整的递归运算
堆排序的过程是:
- 1、创建一个堆H[0..n-1]
- 2、把堆首(最大(小)值)和堆尾互换
- 3、把堆的尺寸减小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
- 4、重复步骤2,直到堆的尺寸为1
堆排序的 最优最差平均时间复杂度均为O(nlgn),空间复杂度为O(n)。
代码
package Sort; import java.util.Arrays; /** * @author Biang Hoo * * 2013年9月14日 */ public class HeapSort implements Sort { public void Sorting(int[] array) { MakeMinHeap(array); for(int i=array.length-1;i>0;i--){ Swap(array,0,i); ShiftDown(array,0,i-1); } } private void MakeMinHeap(int[] array){ int len = array.length; for(int i=len/2-1;i>=0;i--){ ShiftDown(array,i,len); } } private void ShiftDown(int[] array,int i,int n){ int temp = array[i]; int key=2*i+1; while(key<n ){ if(key+1<n && array[key]>array[key+1]){ key++; } if(array[key]>temp){ break; } array[i] =array[key]; i = key; key = 2*i+1; } array[i] = temp; } private void Swap(int[] array,int i,int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } }
补充:软件开发 , Java ,