堆排序递归和非递归

在了解堆排序之前&＃xff0c;基本的二叉树的概念是需要知道的

完全二叉树&＃xff1a;叶子节点在最后一层或者次一层&＃xff0c;且节点从左往右连续

大根堆&＃xff1a;任何根节点都比他的左右子节点都要大

i为节点在数组中的索引&＃xff0c;求节点的父节点&＃xff1a;(i - 1) / 2, 求节点的左节点 i * 2 &＃43; 1,求节点的右节点 i * 2 &＃43; 2

在构建一个堆之前&＃xff0c;我们需要先把他们的左右节点构建成堆&＃xff0c;所以我们从下往上依次构建堆&＃xff0c;由于叶子节点是没有子节点的&＃xff0c;所以从最后一个节点的父节点开始构建&＃xff0c;想画个个图&＃xff0c;可是实力实在不允许那就都放在代码中吧&＃xff0c;老铁干了这段代码&＃xff0c;先写递归的吧&＃xff0c;递归毕竟理解起来简单。

//测试方法&＃64;Testpublic void test() {int size &＃61; 50;int[] array &＃61; new int[size];for (int i &＃61; 0; i < size; i&＃43;&＃43;) {array[i] &＃61; (int) (Math.random() * 100);}heapify2(array);System.out.println(Arrays.toString(array));}//堆排public void heapify2(int[] array) {if (array &＃61;&＃61; null || array.length < 2) {return;}//最后一个节点的父节点int parentNode &＃61; (array.length - 2) / 2;//进行堆排for (int i &＃61; parentNode; i >&＃61; 0; i--) {sift2(array, i, array.length - 1);}//交换最后一个数和第一个数,交换后最大的数到最后&＃xff0c;下次堆排的时候&＃xff0c;最后一个数就不许算进去了for (int i &＃61; array.length - 1; i > 0 ; i--) {swap(array, 0, i);sift2(array, 0, i - 1);}}/*** &＃64;Description 递归写法*/public void sift2(int[] array, int currentNode, int length) {//左节点int left &＃61; currentNode * 2 &＃43; 1;//右节点int right &＃61; currentNode * 2 &＃43; 2;//如果左右节点有比当前节点要大的节点&＃xff0c;后面是需要以这个节点进行堆排的int max &＃61; currentNode;//左节点不能超过数组的最大索引if (left <&＃61; length && array[left] > array[max]) {max &＃61; left;}if (right <&＃61; length && array[right] > array[max]) {max &＃61; right;}//如果发生交换&＃xff0c;我们就需要进行堆排了if (max !&＃61; currentNode) {swap(array, max, currentNode);//由于max指向的索引是最大的&＃xff0c;和currentNode交换后&＃xff0c;max现在指向的值就是currentNode的值了sift2(array, max, length);}}


最主要的就是这个sift,通过不断交换&＃xff0c;来达到大根堆的效果&＃xff0c;接着就是非递归的写法&＃xff0c;其实和递归的思想一样&＃xff0c;我们交换后就以交换的节点来进行堆排

/*** &＃64;Description 非递归写法*/public void sift1(int[] array, int currentNode, int length) {//这个tmp就是当前需要堆排的节点&＃xff0c;如果交换了&＃xff0c;我们就让这个tmp等于交换的位置&＃xff0c;来达到往下移一层int tmp &＃61; currentNode;//左节点int j &＃61; currentNode * 2 &＃43; 1;while (j <&＃61; length) {//比较左右大小if (j &＃43; 1 <&＃61; length && array[j &＃43; 1] > array[j]) {j &＃61; j &＃43; 1;}//由于左右已经进行比较了&＃xff0c;所以我们只要于最大的比较if (array[tmp] < array[j]) {swap(array, tmp, j);//tmp往下移一层&＃xff0c;tmp变成下一次需要堆排的节点tmp &＃61; j;//j接着等于需要堆排的左节点j &＃61; tmp * 2 &＃43; 1;} else {break;}}}