C语言中的高效冒泡排序？

Question

我目前正在开展一个大学项目来练习指针和数组修改。为了获得项目的完整 4.0，我需要调整冒泡排序代码以提高效率。换句话说，我需要该函数在数组成功排序后停止运行排序迭代。说实话，我被打败了。我需要关于如何实现这一目标的所有建议。

我的代码如下：

int bubbleSortAscend(int *ary, int i, int l) {
    for (i = 0; i < l; i++) {
        if (*(ary + i) > *(ary + (i + 1))) {
            int temp = *(ary + (i + 1));
            *(ary + (i + 1)) = *(ary + i);
            *(ary + i) = temp;
        }
    }
}

提前谢谢您！

Answer 1

知道了！感谢 ShadowRanger 的建议。我接受了他的想法并加以改造。代码如下。从布尔值设置为 false 开始，如果无法进行更多排序，循环将中断然后打印。我确信有一种比我所做的更紧凑的方法（我是一个 C 菜鸟）。但这就是它背后的想法：P

编辑：这是以前不正确的。新代码：

int bubbleSortAscend(int *ary, int i, int l){
    char sorted = false;

    l -= 1;
    while(sorted == false) {
      sorted = true;
      for (i = 0; i < l; i++) {
        if(*(ary+i) > *(ary+(i+1))) {
          int temp = *(ary+(i+1));
          *(ary+(i+1)) = *(ary+i);
          *(ary+i) = temp;
          sorted = false;
          }
        }
      }
    printf("Your sorted array is: ");
    for(i = 0; i < (l + 1); i++)
      printf("%d ", *(ary+i));
    printf("\n");

将排序值更改为 true 现在发生在 for 循环之外，而不是在 else 语句中。再次感谢大家的帮助。

Answer 2

您的代码没有实现冒泡排序，因为您只对数组执行一次传递。此外，您访问数组末尾之外的元素，并且不需要第二个参数。

这是一个高效^(*)的修改版本，因为它在数组排序后立即停止：

int bubbleSortAscend(int *ary, int n) {
    for (;;) {
        int sorted = 1;
        for (int i = 0; i < n - 1; i++) {
            if (*(ary + i) > *(ary + (i + 1))) {
                int temp = *(ary + (i + 1));
                *(ary + (i + 1)) = *(ary + i);
                *(ary + i) = temp;
                sorted = 0;
            }
        }
        if (sorted)
            return;
    }
}

除非您需要使用指针语法，否则代码将是这样就更易读了：

int bubbleSortAscend(int *ary, int n) {
    for (;;) {
        int sorted = 1;
        for (int i = 0; i < n - 1; i++) {
            if (ary[i] > ary[i + 1]) {
                int temp = ary[i];
                ary[i] = ary[i + 1];
                ary[i + 1] = temp;
                sorted = 0;
            }
        }
        if (sorted)
            return;
    }
}

---

^{(*)高效冒泡排序是一个非常好的计算机科学矛盾修辞法。冒泡排序的平均时间复杂度为O(n2)，因此效率不高，但良好的实现在排序列表上具有线性复杂度：比标准归并排序和快速排序。事实上，快速排序的简单实现对于排序列表来说具有二次复杂度}