图文详解Java数据结构与算法

第图文详解Java数据结构与算法重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

动图展示：

17.2代码实现

importjava.util.Arrays;publicclassHeapSort{

publicstaticvoidmain(String[]args){

int[]arr={4,6,8,5,9};

heapSort(arr);//[4,6,8,5,9]//[4,9,8,5,6]//[4,9,8,5,6]//[9,6,8,5,4]//[9,6,8,5,4]//[9,6,8,5,4]//[8,6,4,5,9]//[8,6,4,5,9]//[6,5,4,8,9]//[6,5,4,8,9]//[5,4,6,8,9]//[5,4,6,8,9]//[4,5,6,8,9]

//堆排序

publicstaticvoidheapSort(int[]arr){

//开始位置是最后一个非叶子节点（最后一个节点的父节点）

intstart=(arr.length-1)/2;

//循环调整为大顶堆

for(inti=start;ii--){

maxHeap(arr,arr.length,i);

//先把数组中第0个和堆中最后一个交换位置

for(inti=arr.length-1;ii--){

inttemp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

//再把前面的处理为大顶堆

maxHeap(arr,i,0);

//数组转大顶堆,size:调整多少（从最后一个向前减），index:调整哪一个（最后一个非叶子节点）

publicstaticvoidmaxHeap(int[]arr,intsize,intindex){

//左子节点

intleftNode=2*index+1;

//右子节点

intrightNode=2*index+2;

//先设当前为最大节点

intmax=index;

//和两个子节点分别对比，找出最大的节点

if(leftNodesizearr[leftNode]arr[max]){

max=leftNode;

if(rightNodesizearr[rightNode]arr[max]){

max=rightNode;

//交换位置

if(max!=index){

inttemp=arr[index];

arr[index]=arr[max];

arr[max]=temp;

//交换位置后，可能会破坏之前排好的堆，所以之间排好的堆需要重新调整

maxHeap(arr,size,max);

//打印每次排序后的结果

System.out.println(Arrays.toString(arr));

}}

17.3时间复杂度

最优时间复杂度：o(nlogn)

最坏时间复杂度：o(nlogn)

稳定性：不稳定

它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。

在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。

在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为log2i＋1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。

空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序是一种不稳定的排序方法。

第18章计数排序

18.1计数排序概念

计数排序（CountingSort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

排序步骤：

找出待排序的数组中最大和最小的元素；

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动图展示：

18.2代码实现

importjava.util.Arrays;publicclassCountingSort{

publicstaticvoidmain(String[]args){

//测试

int[]arr={1,4,6,7,5,4,3,2,1,4,5,10,9,10,3};

sortCount(arr);

System.out.println(Arrays.toString(arr));//[1,1,2,3,3,4,4,4,5,5,6,7,9,10,10]

//计数排序

publicstaticvoidsortCount(int[]arr){

//一：求取最大值和最小值，计算中间数组的长度：

intmax=arr[0];

intmin=arr[0];

intlen=arr.length;

for(inti:arr){

if(imax){

max=i;

if(imin){

min=i;

//二、有了最大值和最小值能够确定中间数组的长度（中间数组是用来记录原始数据中每个值出现的频率）

int[]temp=newint[max-min+1];

//三.循环遍历旧数组计数排序:就是统计原始数组值出现的频率到中间数组temp中

for(inti=0;ilen;i++){

temp[arr[i]-min]+=1;

//四、遍历输出

//先循环每一个元素在计数排序器的下标中

for(inti=0,index=0;itemp.length;i++){

intitem=temp[i];

循环出现的次数

while(item--!=0){

//以为原来减少了min现在加上min，值就变成了原来的值

arr[index++]=i+min;

}}

18.3时间复杂度

最优时间复杂度：o(n+k)

最坏时间复杂度：o(n+k)

稳定性：不稳定

计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法

第19章桶排序

19.1桶排序概念

桶排序（Bucketsort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间o(n)。但桶排序并不是比较排序，他不受到O(nlogn)下限的影响。

排序步骤：

设置一个定量的数组当作空桶；

遍历输入数据，并且把数据一个一个放到对应的桶里去；

对每个不是空的桶进行排序；

从不是空的桶里把排好序的数据拼接起来

动图展示：

静图展示：

19.2代码实现

packagesort;importjava.util.ArrayList;importjava.util.Collections;publicclassBucketSort{

publicstaticvoidmain(String[]args){

int[]arr={29,25,3,49,9,37,21,43};

bucketSort(arr);

//分桶后结果为:[[3,9],[],[21,25],[29],[37],[43,49]]

publicstaticvoidbucketSort(int[]arr){

//大的当小的，小的当大的

intmax=Integer.MIN_VALUE;

intmin=Integer.MAX_VALUE;

//找出最小最大值

for(inti=0,len=arr.length;ii++){

max=Math.max(max,arr[i]);

min=Math.min(min,arr[i]);

//创建初始的桶

intbucketNum=(max-min)/arr.length+1;

ArrayListArrayListIntegerbucketArr=newArrayList(bucketNum);

//这一步是不可缺少的，上面的初始化只初始化了一维列表。二维列表需额外初始化

for(inti=0;ibucketNum;i++){

bucketArr.add(newArrayList());

for(inti=0,len=arr.length;ii++){

intnum=(arr[i]-min)/arr.length;//相同的商在同一个桶中

bucketArr.get(num).add(arr[i]);//根据商的不同，放入不同的桶

for(inti=0;ibucketArr.size();i++){//同一桶内，自己排序

Collections.sort(bucketArr.get(i));

System.out.println(分桶后结果为:+bucketArr.toString());

}}

19.3时间复杂度

最优时间复杂度：o(n)

最坏时间复杂度：o(n^2)

稳定性：稳定

对于桶排序来说，分配过程的时间是O(n)；收集过程的时间为O(k)（采用链表来存储输入的待排序记录）。因此，桶排序的时间为O(n+k)。若桶个数m的数量级为O(n)，则桶排序的时间是线性的，最优即O(n)。

前面说的几大排序算法，大部分时间复杂度都是O(n2)，也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是：首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。其次待排序的元素都要在一定的范围内等等。

第20章基数排序

20.1基数排序概念

基数排序（RadixSort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前

排序步骤：

取得数组中的最大数，并取得位数；

arr为原始数组，从最低位开始取每个位组成radix数组；

对radix进行计数排序（利用计数排序适用于小范围数的特点）

动图展示：

静图分析：

20.2代码实现

importjava.util.Arrays;publicclassRadixSort{

publicstaticvoidmain(String[]args){

int[]arr={4,32,457,16,28,64};

radixSort(arr);//[32,4,64,16,457,28]//[4,16,28,32,457,64]//[4,16,28,32,64,457]

//基数排序

publicstaticvoidradixSort(int[]arr){

//定义临时二维数组表示十个桶

int[][]temp=newint[10][arr.length];

//定义一个一维数组，用于记录在temp中相应的数组中存放数字的数量

int[]counts=newint[10];

//存数组中最大的数字

intmax=Integer.MIN_VALUE;

for(inti=0;iarr.length;i++){

if(arr[i]max){

max=arr[i];

//计算最大数字是几位数（才能知道排序次数）

intmaxLength=(max+).length();

//根据最大长度的数决定比较的次数

for(inti=0,n=1;imaxLength;i++,n*=10){

//把每一个数字分别计算余数

for(intj=0;jarr.length;j++){

//计算余数

intys=arr[j]/n%10;

//把当前遍历的数据放入指定的数组中

temp[ys][counts[ys]]=arr[j];

//记录数量

counts[ys]++;

//记录取的元素需要放的位置

intindex=0;