1

问题描述

刚才我正在学习 C++ 编程语言，我决定通过编写代码来做到这一点。我尝试编写一个算法，它将数组中的项目从min值开始排序为max值，我得到一个像这样的整数数组

    int arrayToSort[] = {3,5,3,1,8,7,2,4};

并尝试编写一个对该数组进行排序的算法。下面你可以看到源代码

算法一

int arrayToSort[] = {3,5,3,1,8,7,2,4};
int arrayToSortSize = sizeof(arrayToSort)/sizeof(int);

for(int i=1; i<arrayToSortSize; ++i) {
    int* first = arrayToSort;
    int* end = arrayToSort + arrayToSortSize;

    for(first; first!=end-i; ++first) {
        if (*first > *(first+1)) {
            int temp = *first;
            *first = *(first+1);
            *(first+1) = temp;
        }   
    }
}

该算法工作正确，并对数组中的所有元素进行正确排序，1, 2, 3, 3, 4, 5, 7, 8但我想知道该算法是否正确进行此类排序，我的意思是在这种情况下，这是对所有元素进行排序的最短方法吗？

算法二

这里我实现了相同的算法，但这次我使用数组而不是指针，你可以在下面看到源代码：

int arrayToSortSize = sizeof(arrayToSort)/sizeof(int);

for(int i=1; i<arrayToSortSize; ++i) {
    int* first = arrayToSort;
    int* end = arrayToSort + arrayToSortSize;

    for(int j=0; j<arrayToSortSize-i; j++) {
        if (arrayToSort[j] > arrayToSort[j+1]) {
            int temp = arrayToSort[j];
            arrayToSort[j] = arrayToSort[j+1];
            arrayToSort[j+1] = temp;
        }   
    }
}

这个算法也很好用。它对所有项目进行了正确排序，但我想知道哪种算法更好用，可能是哪一种更快（如果其中一种是）？

问题

  • 哪种算法更好用？
  • 哪个算法更快？或者他们以相同的速度工作？
  • 算法 I或算法 II能以更好的方式实现吗？
  • 这个算法怎么叫？

排序示例图像

4

3 回答 3

3

您的两个“算法”是称为Bubble sort的同一算法的两个实现。

这是最简单的排序算法，但性能很差（二次复杂度）。

如果你想更深入地研究排序算法，这里有很多很棒的书，我特别喜欢这本。

如果您只想查看性能更快的算法，请查看quicksortor mergesort。它们都有优点和缺点，但您通常可以根据您的应用程序和数据大小选择其中之一。

更一般地说，std::sort在相关和可能的情况下，根据数据的大小，更喜欢哪个在定制所需的特定算法方面做得很好。只有当您发现自己有性能问题（或出于学习目的）时，您才能考虑实现自己的sort. 但是你真的必须知道你在做什么，因为很容易编写性能不佳的排序实现（即使是一个好的算法）。

编辑（精度）：在现实生活中，当数组足够小（比如，少于 20 个项目）时，使用insertion sort. 否则，quicksort如果您对数据没有更多假设，请继续。这个截止的原因是递归调用的成本可能会在少量数据上占太多开销，而不仅仅是使用快速insertion sort.

于 2013-03-05T20:46:13.583 回答
0

两者都不。

在大多数情况下，使用数组和指针之间的差异可以忽略不计。

算法 I 和 II 都是所谓的冒泡排序。在某些情况下，它是一种有效的排序，但很少是最快的排序。

于 2013-03-05T20:46:20.793 回答
0

两种算法都找到更大的值，然后是第二个等等......所以如果你有 N 个元素，循环的第一次运行将比较 N-1 个元素，循环中的第二行将匹配 N-2 等等。

它称为冒泡排序。它采用 (N-1)N / 2 比较操作的近似值。如果您使用二进制搜索的快速排序（例如），您将需要 O(N log N) 操作，这对于大量 N 至关重要。 来自 wiki的快速排序

于 2013-03-05T20:47:06.107 回答