|
20 | 20 |
|
21 | 21 | #### [10.LRU算法](#LRU算法) |
22 | 22 |
|
23 | | -#### [11.###【面试算法题】阿拉伯数字转化为中文读法](#【面试算法题】阿拉伯数字转化为中文读法) |
| 23 | +#### [11.【面试算法题】阿拉伯数字转化为中文读法](#[面试算法题]阿拉伯数字转化为中文读法) |
24 | 24 |
|
25 | 25 | ### 常见的排序算法 |
26 | 26 |
|
@@ -108,12 +108,12 @@ int[] sorted3(int[] array) { |
108 | 108 |
|
109 | 109 | ```java |
110 | 110 | void sort(int[] array) { |
| 111 | + if (array==null||array.length==0) { return; } |
111 | 112 | //临时数组主要用于归并过程中的临时存放排序数组 |
112 | 113 | int[] tempArray = new int[array.length]; |
113 | 114 | mergeSort(array,0,array.length-1,tempArray); |
114 | 115 | } |
115 | 116 | void mergeSort(int[] array, int start, int end,int[] tempArray) { |
116 | | - if (array==null||array.length==0) { return; } |
117 | 117 | if (start>=end) { return; } |
118 | 118 | //进行分组，一直分到只有两个元素，在小组内进行归并 |
119 | 119 | int middle = start + (end - start)/2; |
@@ -228,30 +228,20 @@ int[] quickSorted(int [] array, int start,int end) { |
228 | 228 | //调整大顶堆，需要调整节点i， |
229 | 229 | //使节点i与它的子节点都满足大顶堆的性质(就是父节点>左节点和右节点) |
230 | 230 | void adjustHeap(int[] array,int i,int length) { |
231 | | - //循环结束的条数是节点i存在左节点 |
232 | | - while (2*i+1<length) { |
233 | | - int left = 2*i+1;//左节点下标 |
234 | | - int right = 2*i+2;//右节点下标，可能会越界，所以下面会判断 |
235 | | - if (right<length) {//节点i存在右节点 |
236 | | - //父节点，左节点，右节点三者中最大值的数组下标 |
237 | | - int maxIndex = array[right] > array[left] ? right : left; |
238 | | - maxIndex = array[i] > array[maxIndex] ? i : maxIndex; |
239 | | - if (maxIndex == i) {//三者最大值就是父节点 |
240 | | - break; |
241 | | - } else if (maxIndex == left) {//三者最大值就是左节点 |
242 | | - swap(array,i,left); |
243 | | - i = left; |
244 | | - } else if (maxIndex == right) {//最大的节点是右节点 |
245 | | - swap(array,i,right); |
246 | | - i = right; |
247 | | - } |
248 | | - } else {//节点i只有左节点 |
249 | | - if (array[left] > array[i]) {//左节点比父节点大 |
250 | | - swap(array,i,left); |
251 | | - i = left; |
252 | | - } else { |
253 | | - break; |
254 | | - } |
| 231 | + //循环结束的条数是节点i存在左节点 |
| 232 | + while (2*i+1<length) {//左节点存在 |
| 233 | + int left = 2*i+1; |
| 234 | + int right = 2*i+2; |
| 235 | + //max就是i left right 三个节点中的最大值的下标 |
| 236 | + int max = array[i] > array[left] ? i : left; |
| 237 | + if (right<length && array[right] > array[max]) {//右节点存在，并且还比最大值大 |
| 238 | + max = right; |
| 239 | + } |
| 240 | + if (max == i) {//当前已经是最大值 |
| 241 | + break; |
| 242 | + } else {//左节点或者右节点是最大值，那么就将当前节点与最大的节点交换 |
| 243 | + swap(array,i,max); |
| 244 | + i = max; |
255 | 245 | } |
256 | 246 | } |
257 | 247 | } |
|
0 commit comments