选择排序：
简单选择排序-->堆排序
简单选择排序：抓扑克牌的时候一把抓起来，先选最小的放第一张，再从生下的选次小的放第二张，以此。。
复杂度：最好最坏平均：log(n^2)；
n个数排序：遍历n-1次，每一次找出这次遍历所有数最小数的下标，然后和第一个数换；
不稳定
public class SimpleSelectSort { static int[] sqlist = {0,9,8,7,5,6,4,3,2,1,12,23,11}; public static void main(String[] args) { // TODO Auto-generated method stub simpleselectsort(sqlist); for (int i = 0; i < sqlist.length; i++) { System.out.print(sqlist[i]+" "); } } /*每一趟找出最小的数的坐标，让这个坐标和每一趟的第一个数交换 * 数据交换次数少，O(n^2)复杂度，性能总体略优于冒泡*/ public static void simpleselectsort(int[] sqlist) { int temp; for (int i = 0; i < sqlist.length; i++) { temp = i; for (int j = i+1; j < sqlist.length; j++) { if (sqlist[j]<sqlist[temp]) { temp=j; } } if (temp!=i) { swap(sqlist, temp, i); } } } private static void swap(int[] sqlist,int i,int j) { int temp = sqlist[i]; sqlist[i] = sqlist[j]; sqlist[j] = temp; } }
堆排序：
堆是一种完全二叉树；每个节点的值都大于或等于其左右孩子节点的值；这称为大顶堆；如果是小于就称为小顶堆；
堆排序思路：
1.先将输入数组构建成一个大顶堆；这样堆顶一定是最大的数字；
for(从i=n/2开始，到i=0结束){
对每个非叶子节点，进行堆调整heapadjust();
}
2.然后将堆顶和层序遍历的最后一个数交换；得到一个n-1的次大堆；
堆这个n-1的堆进行堆调整；重复操作；得到一个有序序列；
复杂度：
最好最坏平均：O（nlogn）
不稳定
public class HeapSort { static int[] sqlist = {0,4,5,1,6}; // static int[] sqlist = {0,50,10,90,30,70,40,80,60,20}; public static void main(String[] args) { // TODO Auto-generated method stub heapsort(sqlist); for (int i = 0; i < sqlist.length; i++) {//0不被排序 System.out.print(sqlist[i]+" "); } } private static void heapsort(int[] sqlist2) { // TODO Auto-generated method stub //把sqlist2数组，构建成一个大顶堆 for (int i = sqlist2.length/2; i > 0 ; i--) { HeapAdjust(sqlist2,i,sqlist2.length-1);//这里和下面都调用了HeapAdjust，注意length参数要一致； } for (int i = sqlist2.length-1; i > 1; i--) { swap(sqlist2, 1, i); HeapAdjust(sqlist2, 1, i-1); } } /*给定一个位置i,以i往下的左右节点都构造成满足堆的完全二叉树*/ private static void HeapAdjust(int[] sqlist2, int i, int length) { // TODO Auto-generated method stub int j = 0; int temp = sqlist2[i]; for (j = 2*i; j <= length; j*=2) { if (j<length&&sqlist2[j]<sqlist2[j+1]) { j++;//说明j+1比j所在的值大；所以J++，现在J所在的值较大 } if (temp>=sqlist2[j]) {//比较i和j的值谁大 break;//如果temp所在顶点本身就是最大的，那么不用比较了 } sqlist2[i]=sqlist2[j];//如果没有break，i这个顶点被赋值为j那个最大值，此时i和j都是最大值 i=j;//i被赋值为J,继续循环j=2*i;即j=2*j;此时，应该被换的就是这个i； } sqlist2[i]=temp; } private static void swap(int[] sqlist,int i,int j) { int temp = sqlist[i]; sqlist[i] = sqlist[j]; sqlist[j] = temp; } }
