性能对比

排序算法性能对比.png

LeetCode

912. 排序数组

快速排序

  1. 快速排序参数有三个，分别是源数组、左边界和右边界。采用的是闭区间写法。

  2. 可将整个排序算法细分成四部分：

    1. 边界判断：if (lo >= hi) return。
    2. partition：定位元素 nums[lo] 所在的位置。不断比较即可。
    3. 对左半部分进行排序。

    4. 对右半部分进行排序。

      1. class Solution {
      2. public int[] sortArray(int[] nums) {
      3.   if (nums == null || nums.length == 0) return new int[0];
      4.   int len = nums.length;
      5.   quickSort(nums, 0, len - 1);
      6.   return nums;
      7. }
      9. private void quickSort(int[] nums, int lo, int hi) {
      10.   if (lo >= hi) return;
      12.   // 定义两个指针，用于元素交换。
      13.   // 这一步的目的就是确定 nums[l] 所在的位置
      14.   // 遇到比 
      15.   int l = lo, cur = lo + 1;
      16.   while (cur <= hi) {
      17.       // 当前元素小于的时候才会被交换
      18.       if (nums[cur] <= nums[lo]) {
      19.           swap(nums, l + 1, cur);
      20.           l++;
      21.       }
      22.       cur++;
      23.   }
      24.   // 位置 l 就是 lo 的确切地点了
      25.   swap(nums, l, lo);
      27.   quickSort(nums, lo, l - 1);
      28.   quickSort(nums, l + 1, hi);
      29. }
      31. private void swap(int[] nums, int i, int j) {
      32.   int temp = nums[i];
      33.   nums[i] = nums[j];
      34.   nums[j] = temp;
      35. }
      36. }

      归并排序

      1. class Solution {
      2. public int[] sortArray(int[] nums) {
      3.   if (nums == null || nums.length == 0) return new int[0];
      4.   int len = nums.length;
      5.   int[] temp = new int[len];
      6.   mergeSort(nums, 0, len - 1, temp);
      7.   return nums;
      8. }
      10. private void mergeSort(int[] nums, int lo, int hi, int[] temp) {
      11.   if (lo >= hi) return;
      12.   int mid = lo + (hi - lo) / 2;
      13.   mergeSort(nums, lo, mid, temp);
      14.   mergeSort(nums, mid + 1, hi, temp);
      15.   mergeTowSortedArray(nums, lo, mid, hi, temp);
      16. }
      18. private void mergeTowSortedArray(int[] nums, int lo, int mid, int hi, int[] temp) {
      19.   System.arraycopy(nums, lo, temp, lo, hi - lo + 1);
      21.   int i = lo, j = mid + 1;
      23.   for (int k = lo; k <= hi; k++) {
      24.       if      (i > mid) nums[k] = temp[j++];
      25.       else if (j > hi)  nums[k] = temp[i++];
      26.       else if (temp[i] > temp[j]) nums[k] = temp[j++];
      27.       else                        nums[k] = temp[i++];
      28.   }
      29. }
      30. }