堆排序

目录

堆排序（不稳定）：

    代码实现：

    思路分析：

     总结：

---

堆排序（不稳定）：

   如果想要一段数据从小到大进行排序，则要先建立大根堆，因为这样每次堆顶上都能取到数据中最大的，可以交换到一段数据最后面。

    代码实现：

public static void heapSort(int[] arr) {createHeap(arr);int end = arr.length - 1;while(end > 0) {swap(arr,0,end);siftDown(arr,0,end);end--;}}//建立大根堆public static void createHeap(int[] arr) {for (int i = (arr.length-1-1) / 2; i >= 0 ; i--) {siftDown(arr,i, arr.length);}}//向下调整private static void siftDown(int[] arr,int parent, int k) {int child = 2 * parent + 1;while(child < k) {if(child + 1 < k && arr[child + 1] > arr[child]) {child++;}if(arr[child] > arr[parent]) {//交换swap(arr,parent,child);parent = child;child = 2 * parent + 1;}else {break;}}}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

    思路分析：

        

       红色代表数组下标。

        首先，想要从小到大排序，在堆排序开始之前，先对数据建立一个大根堆，之后，交换0下标和数据末尾的值，这样最后一个下标的值得到的是该段数据中最大的值了，再从0下标位置开始向下调整这个堆，以此往复，当 end 为 0 时停止。此时从上往下，从左往右得到的就是升序的数据了。

        

     总结：

        排升序要建大堆，排降序建小堆。