非原地分区

  1. function sortArray(nums) {
  2.   if (nums.length <= 1) {
  3.     return nums;
  4.   }
  6.   var pivot = Math.floor(nums.length / 2);
  8.   var left = [];
  9.   var right = [];
  11.   for (var i = 0; i < nums.length; i++) {
  12.     if (i === pivot) {
  13.       continue;
  14.     }
  16.     if (nums[i] < nums[pivot]) {
  17.       left.push(nums[i]);
  18.     } else {
  19.       right.push(nums[i]);
  20.     }
  21.   }
  23.   return sortArray(left).concat([nums[pivot]], sortArray(right));
  24. }

原地分区

  1. function swap(nums, x, y) {
  2.   var temp = nums[x];
  3.   nums[x] = nums[y];
  4.   nums[y] = temp;
  5. }
  7. function partition(nums, start, end) {
  8.   var pivot = start + Math.floor(Math.random() * (end - start + 1));
  9.   swap(nums, pivot, end);
  11.   for (var i = start; i < end; i++) {
  12.     if (nums[i] <= nums[end]) {
  13.       swap(nums, start++, i);
  14.     }
  15.   }
  16.   swap(nums, start, end);
  18.   return start;
  19. }
  21. function quickSort(nums, start, end) {
  22.   if (start >= end) {
  23.     return;
  24.   }
  26.   var pivot = partition(nums, start, end);
  27.   quickSort(nums, start, pivot - 1);
  28.   quickSort(nums, pivot + 1, end);
  29. }
  31. function sortArray(nums) {
  32.   quickSort(nums, 0, nums.length - 1);
  33.   return nums;
  34. }

总结

  • 原理：分而治之
  • 时间复杂度：O(nlogn)