排序

排序算法

快速排序

快速排序是一种常见的排序算法，其核心思想是分治法。下面是快速排序的步骤：

1. 选取一个基准数（pivot）
2. 将序列中比基准数大的元素放在基准数的右边，比基准数小的元素放在基准数的左边。
3. 递归地对基准数左右两边的序列进行排序，直到序列长度为1或0。

快速排序中最重要的就是第2步，也就是partation阶段。快速排序有很多不同的实现方式，每次选择最右侧的数作为pivot进行partation。

int partation(vector<int> &nums, int left, int right)
{
   int pvoit = nums[right];     // 选择最右侧的数作为pivot
   int i = left - 1;
   for(int j = left; j <= right; ++j)
   {
      if(nums[j] <= pvoit)
          swap(nums[++i], nums[j]);

   }
   return i;
}

通过上面的代码我们可以看出，每次partation必然会将一个数放到最终的位置，然后再递归处理pivot左右两侧的区间，那么最好的情况就是每次partation都将数组两等分，而最坏的情况是每次partation划分出的区间都在pivot的一侧。

那么如何避免最坏情况的发生呢？这里可以每次选择一个随机数作为pivot然后进行划分：

int randomPartation(vector<int> &nums, int left, int right)
{
   int p = rand() % (right - left + 1) + left;
   swap(nums[p], nums[right]);      // 将随机选出的数与最右侧数交换
   return partation(nums, left, right); 
}

int partation(vector<int> &nums, int left, int right)
{
  int pvoit = nums[right];
  int i = left - 1;
  for(int j = left; j <= right; ++j)
  {
      if(nums[j] <= pvoit)
      {
          ++i;
          swap(nums[i], nums[j]);
      }
  }
  return i;
}

完整的代码如下：

// 快速排序
vector<int> sortArray(vector<int>& nums) 
{
   srand((unsigned)time(NULL));
   randomQuickSort(nums, 0, (int)nums.size() - 1);
   return nums;
}

void randomQuickSort(vector<int> &nums, int left, int right)
{
   if(left >= right)
      return ;
   int p = randomPartation(nums, left, right);
   randomQuickSort(nums, left, p - 1);
   randomQuickSort(nums, p + 1, right);
}

int randomPartation(vector<int> &nums, int left, int right)
{
   int p = rand() % (right - left + 1) + left;
   swap(nums[p], nums[right]);      // 将随机选出的数与最右侧数交换
   return partation(nums, left, right); 
}

int partation(vector<int> &nums, int left, int right)
{
  int pvoit = nums[right];
  int i = left - 1;
  for(int j = left; j <= right; ++j)
  {
      if(nums[j] <= pvoit)
      {
          ++i;
          swap(nums[i], nums[j]);
      }
  }
  return i;
}

归并排序

#include <iostream>
#include <vector>

// 归并操作，将两个有序数组合并为一个有序数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组来存储左右两部分的元素
    std::vector<int> L(n1), R(n2);

    // 拷贝数据到临时数组 L 和 R
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];
    }

    // 合并临时数组到原数组 arr
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            ++i;
        } else {
            arr[k] = R[j];
            ++j;
        }
        ++k;
    }

    // 拷贝 L 和 R 中剩余的元素（如果有）
    while (i < n1) {
        arr[k] = L[i];
        ++i;
        ++k;
    }
    while (j < n2) {
        arr[k] = R[j];
        ++j;
        ++k;
    }
}

// 归并排序递归函数
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 分别对左右两部分进行递归排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的两部分
        merge(arr, left, mid, right);
    }
}

// 归并排序函数
void mergeSort(std::vector<int>& arr) {
    int n = arr.size();
    if (n > 1) {
        mergeSort(arr, 0, n - 1);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    
    // 调用归并排序函数
    mergeSort(arr);

    // 输出排序后的数组
    std::cout << "Sorted array is: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}