数组排序系列

评论

数组的排序应该是基本中的基本了。

 冒泡排序

冒泡排序的思想是，通过一次遍历，通过比较，将一个最大的元素，调整到数组的末尾，进行 n 次之后，数组就有序了。
因此时间复杂度是 O(n^2)

1
2
3
4
5
6
7
8
9
10
function sortArray(nums: number[]): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
      }
    }
  }
  return nums;
}

插入排序

插入排序的思想是，将数组分成两部分，左半部分是有序的，右半部分是无序的，每次从右半部分取出第一个元素，插入到左半部分。
插入的过程是，把待插入元素和左半部分的元素比较，如果小于就交换，如果大于等于就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
function sortArray(nums: number[]): number[] {
  // nums[i] 是待插入的元素
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j > 0; j--) {
      if (nums[j] < nums[j - 1]) {
        swap(nums, j - 1, j);
      } else {
        break;
      }
    }
  }
  return nums;
}

快速排序

快速排序的思想是，每次将数组分为左右两部分，左半部分的所有值都小于右半部分，然后对左右部分再进行这样的操作。最终整个数组有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function partition(nums: number[], left: number, right: number): number {
  if (left >= right) return right;
  const pvoit = nums[left];
  const start = left;
  left = left + 1;
  while (left <= right) {
    if (nums[left] > pvoit && nums[right] < pvoit) {
      swap(nums, left++, right--);
    } else if (nums[left] <= pvoit) {
      left++;
    } else {
      right--;
    }
  }
  swap(nums, start, right);
  return right;
}

function quickSort(nums: number[], left: number, right: number): number[] {
  if (left >= right) return nums;

  const p = partition(nums, left, right);
  quickSort(nums, left, p - 1);
  quickSort(nums, p + 1, right);

  return nums;
}

function sortArray(nums: number[]): number[] {
  return quickSort(nums, 0, nums.length - 1);
}