气泡排序算法实现

Question

问题描述

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

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

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

算法I

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 )，但是我想知道这个算法是否正确地进行了这样的排序，我的意思是在这种情况下，这是对所有元素排序的最短方式吗?

算法II

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

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可以用更好的方式实现吗？
• 这个算法叫什么？

​

​

Answer 1

您的两个“算法”是相同算法的两个实现，称为气泡排序。

这是最简单的排序算法，但性能较差(二次复杂度)。

如果您想更深入地研究排序算法，那么就有很棒的书籍可供阅读，我特别喜欢这一个。

如果您只想查看执行速度更快的算法，请查看quicksort或mergesort。它们都有优点和缺点，但您通常可以根据应用程序和数据大小选择其中的一个。

更广泛地说，更喜欢std::sort，它在泰勒做了很好的工作，根据相关和可能时数据的大小，对所需的特定算法进行处理。只有当您看到您有性能问题(或者是为了学习目的)时，您才可以考虑实现您自己的sort。但是，您必须知道自己在做什么，因为编写执行不好的排序实现很容易(即使对于一个好的算法也是如此)。

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

Answer 2

都不是。

在大多数情况下，使用数组和指针之间的区别是疏忽的。

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

Answer 3

这两种算法都能找到更大的值，然后再找出第二种算法。因此，如果你有N个元素，循环的第一次运行将比较N1元素，循环中的第二行将比较N-2等等。

它叫泡泡分类。它采用(N-1)N /2比较运算的近似。如果您使用快速排序(例如)，这是二进制搜索，您将需要O(N日志N)操作，这对于大量N. 从wiki中快速排序至关重要。