912. 排序数组

题目

给你一个整数数组 nums，请你将该数组升序排列。

题解

选择排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  selectionSort(nums);
  return nums;
};

function selectionSort(arr) {
  let minIndex;
  for (let i = 0; i < arr.length; ++i) {
    minIndex = i;
    for (let j = i + 1; j < arr.length; ++j) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    let t = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = t;
  }
}

插入排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  insertSort(nums);
  return nums;
};

function insertSort(arr) {
  for (let i = 1; i < arr.length; ++i) {
    let cur = arr[i]; // 要插入的牌
    let j = i - 1;

    // 如果要插入的比当前小，就把当前的往后移
    while (j >= 0 && cur < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = cur;
  }
}

希尔排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  shellSort(nums);
  return nums;
};

function shellSort(arr) {
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
    // 分组
    for (let i = gap; i < arr.length; ++i) {
      let cur = arr[i];
      let preIndex = i - gap;
      while (preIndex >= 0 && cur < arr[preIndex]) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = cur;
    }
  }
}

堆排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  heapSort(nums);
  return nums;
};

function heapSort(arr) {
  // 构建最大堆
  buildMaxHeap(arr);
  for (let i = arr.length - 1; i >= 0; i--) {
    let t = arr[0];
    arr[0] = arr[i];
    arr[i] = t;
    maxHeapify(arr, 0, i);
  }
}

function buildMaxHeap(arr) {
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    maxHeapify(arr, i, arr.length);
  }
}

function maxHeapify(arr, i, heapSize) {
  let l = 2 * i + 1;
  let r = l + 1;

  let largest = i;

  if (l < heapSize && arr[l] > arr[largest]) {
    largest = l;
  }
  if (r < heapSize && arr[r] > arr[largest]) {
    largest = r;
  }

  if (largest != i) {
    let t = arr[i];
    arr[i] = arr[largest];
    arr[largest] = t;
    maxHeapify(arr, largest, heapSize);
  }
}

快速排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};

function quickSort(A, p, r) {
  if (p < r) {
    let q = Partition(A, p, r);
    quickSort(A, p, q - 1);
    quickSort(A, q + 1, r);
  }
}

function Partition(A, p, r) {
  let x = A[r];
  let i = p - 1;
  for (let j = p; j < r; j++) {
    if (A[j] <= x) {
      i++;
      [A[i], A[j]] = [A[j], A[i]];
    }
  }
  [A[i + 1], A[r]] = [A[r], A[i + 1]];
  return i + 1;
}