排序算法的评价指标

时间效率：排序算法的时间复杂度
空间效率：排序算法需要的辅助内存
稳定性：相等元素在完成排序后的相对顺序是否发生改变
自适应性：排序算法能否利用输入数据的已有顺序来减少计算量

选择排序

从未排序区间选择最下小的元素，将其放到已排序区间的末尾。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$，不稳定排序。

void selectionSort(vector<int>& nums) {
  int n = nums.size();
  for (int i = 0; i < n - 1; ++i) {
    int k = i;
    for (int j = i + 1; j < n; ++j) {
      if (nums[j] < nums[k]) {
        k = j;
      }
    }
    
    swap(nums[k], nums[i]);
  }
}

冒泡排序

遍历数组，每次将最大的元素移动到最右端。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$，稳定排序。

void bubbleSort(vecotr<int>& nums) {
  for (int i = nums.size() - 1; i > 0; --i) {
    bool flag = false;
    for (int j = 0; j < i; ++j) {
      if (nums[j] > nums[j + 1]) {
        swap(nums[j], nums[j + 1]);
        flag = true;
      }
    }
    
    if (!flag) {
      break;
    }
  }
}

插入排序

在未排序区间选择一个基准元素（一般选最左侧），将元素与左侧排序区间的元素比较，并将其排序到指定位置。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$，稳定排序。

void insertionSort(vecotr<int>& nums) {
  for (int i = 1; i < nums.size(); ++i) {
    int base = nums[i], j = i - 1;
    while ( j >= 0 && nums[j] > base) {
      nums[j + 1] = nums[j];
      --j;
    }
    
    nums[j + 1] = base;
  }
}

快速排序

选取数组最左侧元素作为哨兵，i和j分别从两端向中间靠拢，将大数移到右边，小数移到左边，循环直到 i j相遇。时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$，非稳定排序。

int partition(vector<int>& nums, int left, int right) {
  int i = left, j = right;
  while(i < j) {
    while ( i < j && nums[i] >= nums[left]) --j;
    while ( i < j && nums[i] <= nums[left]) ++i;
    swap(nums[i], nums[j]);
  }
  return i;
}

void quickSort(vector<int>& nums, int left, int right) {
  if (left >= right) return;
  int pivot = partition(nums, left, right);
  quickSort(nums, left, pivot - 1);
  quickSort(nums, pivot + 1, right);
}

归并排序

计算数组中点mid，递归划分子数组，直到子数组长度为1，然后自底向顶将子数组合并。时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$，稳定排序。

void merge(vector<int>& nums, int left, int mid, int right) {
  vector<int> tmp(right - left + 1);
  int i = left, j = mid + 1, k = 0;
  while (i <= mid && j <= right) {
    if (nums[i] <= nums[j])
      tmp[k++] = nums[i++];
    else
      tmp[k++] = nums[j++];
  }
  
  while (i <= mid) tmp[k++] = nums[i++];
  while (j <= right) tmp[k++] = nums[j++];
  
  for (k = 0; k < tmp.size(); ++k) {
    nums[left + k] = tmp[k];
  }
}

void mergeSort(vector<int>& nums, int left, int right) {
  if (left >= right) return;
  
  int mid = left + (right - left)/2;
  mergeSort(nums, left, mid);
  mergeSort(nums, mid + 1, right);
  
  merge(nums, left, mid, right);
}

排序