java实现、配图解，附源码十大经典排序算法( 五 ) _排序算法

8.1实现原理假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：

扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；
扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1 。

文章插图

8.2 动图演示

文章插图

8.3实例展示

文章插图

 1 public class CountSort { 2public static void main(String[]args){ 3//排序的数组 4int a[]={15,63,97,12,235,66}; 5int b[]=countSort(a); 6for(int i:b){ 7System.out.print( i+","); 8} 9System.out.println();10}11public static int[] countSort(int[]a){12int b[] = new int[a.length];13int max = a[0],min = a[0];14for(int i:a){15if(i>max){16max=i;17}18if(i<min){19min=i;20}21}//这里k的大小是要排序的数组中，元素大小的极值差+122int k=max-min+1;23int c[]=new int[k];24for(int i=0;i<a.length;++i){25c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小26}27for(int i=1;i<c.length;++i){28c[i]=c[i]+c[i-1];29}30for(int i=a.length-1;i>=0;--i){31b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素32}33return b;34}35 }

文章插图

排序结果展示：

文章插图

堆排序
堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
9.1实现原理

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1 。

文章插图

9.2 动图演示

文章插图

9.3实例展示

文章插图

 1 public static int[] heapSort(int[] array) { 2//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1 3for (int i = array.length / 2 - 1; i >= 0; i--) {4adjustHeap(array, i, array.length);//调整堆 5} 67// 上述逻辑，建堆结束 8// 下面，开始排序逻辑 9for (int j = array.length - 1; j > 0; j--) {10// 元素交换,作用是去掉大顶堆11// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置12swap(array, 0, j);13// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了 。14// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因15// 而这里，实质上是自上而下，自左向右进行调整的16adjustHeap(array, 0, j);17}18return array;19}2021/**22* 整个堆排序最关键的地方23* @param array 待组堆24* @param i 起始结点25* @param length 堆的长度26*/27public static void adjustHeap(int[] array, int i, int length) {28// 先把当前元素取出来，因为当前元素可能要一直移动29int temp = array[i];30for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {//2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树31// 让k先指向子节点中最大的节点32if (k + 1 < length && array[k] < array[k + 1]) {//如果有右子树,并且右子树大于左子树33k++;34}35//如果发现结点(左右子结点)大于根结点，则进行值的交换36if (array[k] > temp) {37swap(array, i, k);38// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断39i=k;40} else {//不用交换，直接终止循环41break;42}43}44}4546/**47* 交换元素48* @param arr49* @param a 元素的下标50* @param b 元素的下标51*/52public static void swap(int[] arr, int a, int b) {53int temp = arr[a];54arr[a] = arr[b];55arr[b] = temp;56}