常用排序算法（三）

本篇介绍的两种算法是笔试面试过程中最常考到的两种排序算法，分别是快速排序和堆排序。尤其是快速排序经常会被问及，一方面是其思想比较好理解，另一方面在代码实现上快速排序也不难。堆排序是比较难理解的一种排序，实现起来也比较复杂，如果被问到很容易GG。但堆排序是常用排序算法中平均性能最好的算法，其时间复杂度O(nlogn) ，无论任何情况均是如此，空间复杂度O(1)。前篇所讲的归并排序与之时间复杂度相同，但空间复杂度为O(n)，所以综合而言还是堆排序更胜一筹。

快速排序

快速排序同样运用到了分治的思想，大体分为如下步骤：

①寻找一个元素作为基准，比它大的放在右边，小的放在左边（一般选用当前部分的首元素作为基准）
②通过比较将比基准元素大的放在其右边，小的放在左边
③将基准元素左右两边的元素分别视作两个数组，重复上述排序过程

先给出核心代码：

while(start < end){
  while(nums[end] > key && start < end){
    end--;
  }
  if(start < end){
    int temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
    start++;
  }
  while(nums[start] < key && start < end){
    start++;
  }
  if(start < end){
    int temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
    end--;
  }
}

以序列：50 10 90 30 70 40 80 60 20 为例进行一趟排序推演。
记基准值为key，设定两个下标start、end，初始为本段数组首元素下标和尾元素下标。

key = 50
 50  10  90  30  70  40  80  60  20
start                            end
发现num[end] < num[start]，交换，并start++
 20  10  90  30  70  40  80  60  50
    start                        end
num[start]=10小于num[end]=50，start++
 20  10  90  30  70  40  80  60  50
        start                    end
num[start]=90 > num[end]，交换，end--
 20  10  50  30  70  40  80  60  90
        start                end
num[start]=50 < num[end]=60，end--
 20  10  50  30  70  40  80  60  90
        start            end
num[start]=50 < num[end]=80，end--
 20  10  50  30  70  40  80  60  90
        start        end
num[start]=50 > num[end]=40，交换，start++
 20  10  40  30  70  50  80  60  90
            start    end
num[start]=30 < num[end]=50,start++
 20  10  40  30  70   50  80  60  90
                start end
num[start]=70 > num[end]=50,交换，end--
 20  10  40  30  70   50  80  60  90
                start end
 20  10  40  30  50   70  80  60  90
                start 
                 end
不满足start<end，退出while循环，之后的排序将对'50'两边的元素分别进行排序。

完整代码：

public static void quickSort(int[] nums, int start, int end){
  if(start == end){
    return ;
  }
  int low = start;
  int high = end;
  int key = nums[start];
  while(start < end){
    while(nums[end] > key && start < end){
      end--;
    }
    if(start < end){
      int temp = nums[end];
      nums[end] = nums[start];
      nums[start] = temp;
      start++;
    }
    while(nums[start] < key && start < end){
      start++;
    }
    if(start < end){
      int temp = nums[end];
      nums[end] = nums[start];
      nums[start] = temp;
      end--;
    }
  }
  //分别对基准值两边元素排序
  if(low < start){
    quickSort(nums, low, start - 1);
   }
  if(start < high){
    quickSort(nums, start + 1, high);
  }
}

堆排序

堆排序就是一个构建堆的过程，当按照升序排序时，构建大根堆，降序排序时，构建小根堆。所谓堆就是一个二叉树，大根堆就是让当前数组中最大的元素在堆顶也就是作为根节点，对于每个有左右子节点的节点而言，其左右子节点的值也都小于其自身的值。小根堆则正好与大根堆相反。
还是以序列：50 10 90 30 70 40 80 60 20为例。其构建的初始堆如图：

初始堆

根据二叉树的性质，有n个节点的完全二叉树，其含有子节点的节点个数是n/2个，故从9/2=4的节点也就是30对应的节点开始构建大顶堆。
30的子节点60和20,60>30，交换操作，堆结构变化为：

第一次改变
接下来看第三个，也就是90对应的节点，其值大于子节点的值，不发生改变。
之后是10对应的节点，10<60 && 10<70，选子节点中的大者进行交换，如下图：
第二次改变

最后是根节点50，其小于左右子节点，调大者进行交换

第三次改变（1）
注意，此时并没有结束，90就位了，但50还需要进行比较，发现其小于 右子节点80，还需要再次调整。
生成大根堆
生成大根堆之后怎么办？因为是升序排序，所以最大值需要和堆末尾元素交换，得到如图：
交换堆顶元素
之后的排序，完全可以忽略末尾元素，因为已经就位了，剩下的元素排序过程同上，也是先构建堆然后交换堆顶，直到剩下最后一个元素为止。
代码实现：

//初始化堆，进行n-1次排序
public static void heapSort(int[] nums){
  for(int i = (nums.length - 1) / 2; i >= 0; i--){
    heapAdjust(nums, i, nums.length - 1);
  }
  for(int i = nums.length - 1; i > 0; i--){
    int temp = nums[0];
    nums[0] = nums[i];
    nums[i] = temp;
    heapAdjust(nums, 0, i - 1);
    }
}
//构建大顶堆
public static void heapAdjust(int[] nums, int s, int m){
  int temp = nums[s];
  for(int i = 2 * s + 1; i <= m; i *= 2){
    if((i + 1) <= m && nums[i] < nums[i + 1]){
      i++;
    }
    if(temp >= nums[i]){
      break;
    }
    nums[s] = nums[i];
    s = i;
  }
  nums[s] = temp;
}

排序专题结束，本篇两种方法是重中之重，快拍一定要回，堆排序就算不会写也要能讲清楚思想。