快速排序的一次划分算法（Partition算法）中，每交换一对元素需进行3次元素赋值操作，而实际上，在排序过程中对支点记录的赋值是多余的，可以进一步优化，因为只有在一次划分结束时low和high重叠的位置才是支点元素的最后位置。请写出优化后的Partition算法。

优化后的Partition算法如下：

int Partition(int a[], int low, int high) {
    int pivot = a[low];  // 取第一个元素为支点元素
    int i = low + 1, j = high;
    while (i <= j) {
        while (i <= j && a[i] <= pivot) i++;  // 左侧找到大于pivot的元素
        while (i <= j && a[j] > pivot) j--;   // 右侧找到小于等于pivot的元素
        if (i < j) {  // 交换左侧大于pivot的元素和右侧小于等于pivot的元素
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    // 将支点元素放入最终位置上
    a[low] = a[j];
    a[j] = pivot;
    return j;
}

在这个优化版本的Partition算法中，我们不再在每次交换时都将支点元素赋值给左侧大于pivot的元素。而是在最终确定支点元素的位置时，将支点元素赋值给j位置，此时j位置即为支点元素的最终位置。

相关问题

快速排序的一次划分算法（Partition算法）中，每交换一对元素需进行3次元素赋值操作，而实际上，在排序过程中对支点记录的赋值是多余的，可以进一步优化，因为只有在一次划分结束时low和high重叠的位置才是支点元素的最后位置。请写出优化后的Partition算法

好的，下面是优化后的Partition算法的伪代码：

partition(arr, low, high):
    pivot = arr[low]  # 选择第一个元素作为支点
    i = low + 1
    j = high
    while i <= j:
        while i <= j and arr[i] < pivot:
            i += 1
        while i <= j and arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    arr[low], arr[j] = arr[j], arr[low]  # 将支点元素放到正确的位置上
    return j

这里的优化就是避免了对支点元素的多余赋值操作，而是直接将支点元素放到最终的位置上。具体来讲，我们在交换arr[i]和arr[j]的时候，不需要再将pivot赋值给arr[j]，因为此时pivot的值还保存在arr[low]中，直接将arr[j]与arr[low]交换即可。这样就避免了对pivot的多余赋值操作。

各种排序算法比较c

### 不同排序算法在C语言中的实现效率与特点

#### 冒泡排序
冒泡排序是一种简单的交换类排序方法。该算法通过重复遍历要排序的列表，依次比较相邻元素并根据大小顺序交换它们的位置。这个过程会持续到整个序列变得有序为止。

对于长度为n的数据项序列，在最坏情况下（即逆序），需要进行大约\( \frac{n(n-1)}{2} \)次比较操作和几乎同样数量级的移动操作；而在最好情况（已经正向排列好的输入）下，则只需做一次完整的扫描而无需任何实际移位动作。因此其时间复杂度通常被认为是O(n²)[^1]。

void bubbleSort(int arr[], int n) {
    int i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = false;
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        // 如果某一轮没有发生交换说明数组已经是升序状态可以直接退出循环
        if (!swapped)
            break;
    }
}

#### 插入排序
插入排序也是一种简单直观的方法，它构建最终排序阵列的方式是一步步地将未处理部分的第一个元素插入已排序子表合适位置的过程完成。此法适合于小型或者基本有序的数据集合上应用。

当待排序文件接近完全有序时，插入排序表现良好，因为此时只需要很少甚至不需要额外的操作就能使新加入的记录找到正确的位置。然而，如果初始状态下所有关键字都是随机分布的话，那么平均而言仍需执行约 \( \frac{n^2}{4}\) 的比较次数以及相同比例级别的赋值指令数。所以总体来说它的渐近时间为Θ(n²)。

void insertionSort(int arr[], int n){
   int i,key,j;
   for(i=1;i<n;i++){
      key=arr[i];
      j=i-1;

      while(j>=0 && arr[j]>key){
         arr[j+1]=arr[j];
         j=j-1;
      }
      arr[j+1]=key;
   }
}

#### 选择排序
选择排序的工作原理是从剩余未排序区域选出最小(最大)的一个元素放到当前已知最小/大值所在处，并不断缩小无序区范围直到全部变成有序队列。每次迭代都会确定一个新的固定点，使得左边始终维持着一个增长型的部分有序区间。

尽管这种策略看起来很有效率——毕竟只涉及到了有限几次的关键字互换活动而已——但由于寻找极值本身就需要耗费线性级别的时间代价，故总耗时依旧保持在平方阶水平Ω(n²)。

void selectionSort(int arr[], int n) {
    int min_idx;
  
    for (int i = 0; i < n-1; i++) {    
        min_idx = i;
        for (int j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
   
        swap(&arr[min_idx], &arr[i]);
    }
}

#### 归并排序
归并排序采用分治思想来进行全局性的重新组合工作。具体做法是先递归地把原始序列分割成越来越短的小片段直至单个成员构成独立单元体之后再两两地配对合并起来形成新的更大规模的整体，期间按照一定规则调整各组内部相对秩序关系从而达到整体上的稳定性和高效能特性。由于每一次划分都能减少一半左右的目标对象数目，再加上后续连接环节也仅需线性时间内即可搞定，因而整套流程下来总共花费的是O(nlog₂n)量级运算资源开销[^3]。

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
    ...
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

#### 快速排序
快速排序同样是基于分治原则设计出来的经典排序技术之一。不同于前者自顶向下逐步拆解问题空间的做法，后者则是采取了一种更为激进的态度：选定某个特定参照物作为基准(pivot)，然后围绕着它展开一系列针对其他节点间相互作用模式的研究探讨，进而实现了局部最优解向全局最佳方案转化的目的。理论上讲，只要能够合理选取枢纽元并且保证分区过程中不会出现极端不平衡现象的发生，那么预期可以得到近乎理想化的性能指标T(n)=O(n㏒₂n)。不过需要注意的是，实际应用场景里可能会遇到某些特殊情形导致最差状况下的时间成本上升至O(n²)。

int partition (int arr[], int low, int high) {
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
 
    for (int j = low; j <= high- 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        /* pi is partitioning index, arr[p] is now at right place */
        int pi = partition(arr, low, high);

        // Separately sort elements before / after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}