常见内部排序算法之选择排序
程序员文章站
2024-01-25 19:03:34
...
常见内部排序算法
包括选择排序算法,交换排序算法,插入排序算法,基数算法,桶式算法还有归并算法。
其中选择排序算法又包括:简单选择排序算法与堆排序。
选择算法,顾名思义,就是从中选择需要的,然后再与目标地址进行交换。
简单选择排序算法:
堆排序:包括大顶堆,小顶堆。根据不同需求把根节点与最后一个元素进行交换,每次都循环一个建堆-交换的过程。下面是大顶堆例子:
包括选择排序算法,交换排序算法,插入排序算法,基数算法,桶式算法还有归并算法。
其中选择排序算法又包括:简单选择排序算法与堆排序。
选择算法,顾名思义,就是从中选择需要的,然后再与目标地址进行交换。
简单选择排序算法:
package test.aglorith; public class SelectSort { //从小到大 public void sort(int[] data) { int data_len=data.length; for (int i = 0; i < data_len; i++) { int big=0; for (int j=1;j<data_len-i;j++) { if (data[big]<data[j]) { big=j; } } int point=data_len-1-i; if (big!=point) { int temp=data[point]; data[point]=data[big]; data[big]=temp; } print(data); System.out.println(""); } } public static void print(int[] data) { for(int d:data){ System.out.print(d+","); } } public static void main(String[] args) { int[] data=new int[]{1,10,2,5,3,6,9}; System.out.println("排序之前!"); print(data); System.out.println(""); System.out.println("开始排序!"); new SelectSort().sort(data); } }
堆排序:包括大顶堆,小顶堆。根据不同需求把根节点与最后一个元素进行交换,每次都循环一个建堆-交换的过程。下面是大顶堆例子:
package test.aglorith; public class HeapSort { //排序入口 public void sort(int[] data) { int lastIndex=data.length-1; for (int i = 0; i < data.length; i++) { buildHeap(data, lastIndex-i); swap(data, 0,lastIndex-i); print(data); System.out.println(i); } } //建堆过程 public static void buildHeap(int[] data,int lastIndex) { for(int i=((lastIndex-1)/2);i>=0;i--){ int k=i; while(2*k+1<lastIndex){ int biggerIndex=2*k+1; //判断是否有右子节点 if (biggerIndex<lastIndex) { //选择左右子节点中相对较大的 if (data[biggerIndex]<data[biggerIndex+1]) { biggerIndex++; } } if (data[k]<data[biggerIndex]) { swap(data, k, biggerIndex); k=biggerIndex;//need?有根没有相差不多 }else { break; } } } } //交换目标 public static void swap(int[] data,int i,int j) { int temp=data[i]; data[i]=data[j]; data[j]=temp; } //打印 public static void print(int[] data) { for(int d:data){ System.out.print(d+","); } } public static void main(String[] args) { int[] data=new int[]{1,10,2,5,3,6,9,19,15}; System.out.println("排序之前!"); print(data); System.out.println(""); System.out.println("开始排序!"); long pre=System.currentTimeMillis(); for (int i = 0; i < 30000; i++) { new HeapSort().sort(data); } long end=System.currentTimeMillis(); System.out.println((end-pre)/300); } }
下一篇: 八大排序算法总结