详解桶排序以及排序内容大总结(Detailed bucket sorting and sorting content summary)

一、堆结构(重要):

1、堆结构就是用数组实现的完全二叉树结构

2、完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3、完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4、堆结构的heapinsert与heapify操作

5、堆结构的增大和减少

6、优先级队列结构,就是堆结构

二、变成堆结构的两个重要的过程

1、heapInsert过程

    //index表示当前节点,或者是插入的结点位置
    public static void heapInsert(int[] arr,int index){
        //如果子节点的数大于父节点的数,则进行交换位置,变成大根堆
        while(arr[index]>arr[(index-1)/2]){
            //交换位置
            swap(arr,index,(index-1)/2);
            //将当前节点变为index,继续比较
            index = (index-1)/2;
        }
    }

2、heapify过程

    public static void heapIfy(int[] arr,int index,int heapSize){
        //左孩子的下标
        int left = index * 2 +1;

        while(left<heapSize){//当左孩子的结点下标小于堆的最大空间,因为左孩子的下标小于右孩子,所以说明该结点有孩子
            //两个孩子中,谁的值大,把下标给largest,left+1表示右孩子的下标
            //left+1 < heapSize:表示有右孩子 arr[left+1] > arr[left]:表示右孩子的数大于左结点的数
            //成立的话,将父节点的下标给largest,不成立的话说明左孩子的数大,将左孩子的下标数给largest
            int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left +1:left;

            //上面是比较两个子节点那个数大,接下来比较父节点的数和上面获取到的最大的数
            largest = arr[index] > arr[largest] ? index : largest;

            //如果此时的结点就是父节点,并不用交换,退出循环
            if(largest == index){
                break;
            }
            //否则,交换最大值的位置和父节点的位置,也就是将最大值的交换到父节点
            swap(arr,largest,index);
            //将当前父节点index变为largest
            index = largest;
            //将左孩子的下标变为当前父节点的左孩子下标
            left = index*2+1;
        }
    }

三、堆排序,HeapSort过程

public class code_HeapSort{
public static void heapSort(int arr[]){
//首先判断数组长度为0或者为1的时候,就不用进行堆排序
if(arr == null || arr.length<2){
return;
}
//经过上面的判断,可以进行heapInsert过程
for(int i=arr.length;i>=0;i–){
HeapIfy.heapIfy(arr,i,arr.length);
}
int heapSize = arr.length;
HeapIfy.swap(arr,0,heapSize);
while(heapSize > 0){
//判断,循环条件是此堆里面还有数
HeapIfy.heapIfy(arr,0,–heapSize);
}
}
}

————————

1、 Heap structure (important):

1. Heap structure is a complete binary tree structure implemented by array

2. In a complete binary tree, if the maximum value of each subtree is at the top, it is a large root heap

3. In a complete binary tree, if the minimum value of each subtree is at the top, it is a small root heap

4. Heapinsert and heapify operations of heap structure

5. Increase and decrease of reactor structure

6. The priority queue structure is the heap structure

2、 Two important processes of becoming a heap structure

1、heapInsert过程

    //index表示当前节点,或者是插入的结点位置
    public static void heapInsert(int[] arr,int index){
        //如果子节点的数大于父节点的数,则进行交换位置,变成大根堆
        while(arr[index]>arr[(index-1)/2]){
            //交换位置
            swap(arr,index,(index-1)/2);
            //将当前节点变为index,继续比较
            index = (index-1)/2;
        }
    }

2. Heapify process

    public static void heapIfy(int[] arr,int index,int heapSize){
        //左孩子的下标
        int left = index * 2 +1;

        while(left<heapSize){//当左孩子的结点下标小于堆的最大空间,因为左孩子的下标小于右孩子,所以说明该结点有孩子
            //两个孩子中,谁的值大,把下标给largest,left+1表示右孩子的下标
            //left+1 < heapSize:表示有右孩子 arr[left+1] > arr[left]:表示右孩子的数大于左结点的数
            //成立的话,将父节点的下标给largest,不成立的话说明左孩子的数大,将左孩子的下标数给largest
            int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left +1:left;

            //上面是比较两个子节点那个数大,接下来比较父节点的数和上面获取到的最大的数
            largest = arr[index] > arr[largest] ? index : largest;

            //如果此时的结点就是父节点,并不用交换,退出循环
            if(largest == index){
                break;
            }
            //否则,交换最大值的位置和父节点的位置,也就是将最大值的交换到父节点
            swap(arr,largest,index);
            //将当前父节点index变为largest
            index = largest;
            //将左孩子的下标变为当前父节点的左孩子下标
            left = index*2+1;
        }
    }

3、 Heap sorting, HEAPSORT procedure

public class code_ HeapSort{
public static void heapSort(int arr[]){
//First, when the array length is 0 or 1, there is no need to sort the heap
if(arr == null || arr.length<2){
return;
}
//After the above judgment, the heapinsert process can be performed
for(int i=arr.length;i>=0;i–){
HeapIfy. heapIfy(arr,i,arr.length);
}
int heapSize = arr.length;
HeapIfy. swap(arr,0,heapSize);
while(heapSize > 0){
//It is judged that the cycle condition is that there are still numbers in this heap
HeapIfy. heapIfy(arr,0,–heapSize);
}
}
}