排序算法的效率/性能

Question

我是一个编程初学者，只是在尝试排序并创建了这个算法。它类似于冒泡排序，但它不是比较相邻的一对，而是比较像：第一和第二，第一和第三....第二和第三，第二和第四等等的一对。请问这个算法的性能/效率如何，与冒泡排序相比如何？或至少给我提供一些自己解决问题的建议。我很想知道冒泡排序比这个好多少。谢谢。

void sortArray(int a[]) {

int q, x, temp;

for ( q = 0; q < SIZE - 1; q++ ) {
    for ( x = q + 1; x < SIZE; x++ ) {
        if (a[q] < a[x]) {
            temp = a[q];
            a[q] = a[x];
            a[x] = temp;
        }
    }
}

}

- user2211796

---

你测试过你的算法了吗？它真的可以排序吗？ - n. m.

你需要问自己的问题是：“平均会进行多少次比较”。例如，在从左到右搜索数组中的最大数时，检查的平均次数将是列表长度的一半。 - keyser

听起来有点像选择排序。在外部循环的第n次迭代中，列表的前n个元素处于正确的位置。不过你的算法执行了更多的交换操作。在选择排序中，每次外部循环迭代只执行一次交换操作。 - Kevin

Answer 1

你的排序算法类似于经典的冒泡排序，并且性能基本相同。你的排序和冒泡排序都可以看作选择排序的低效版本。对于这三种算法，每次内部循环迭代遍历数组的未排序区域，找到最小/最大元素，并将其留在最终位置上。这些算法并不完全相同，因为它们对未排序区域执行不同的排列——然而，这种差异在算法的操作中并没有功能上的贡献。

一旦你认识到这一点，就很容易看出为什么选择排序往往比其他两种算法具有常数优势：其内部循环的每次迭代都只需要进行最少数量的交换（即在末尾进行一次）。相比之下，冒泡排序和你的排序可能会在内部循环的每次迭代中进行多达一个交换...

从渐近意义上讲，这三种排序算法都需要O(N^2)时间——具体来说，内部循环将迭代N*(N-1)/2次。

- comingstorm

---

为什么不阅读Wikipedia:Sorting algorithms或下载Knuth的《基本算法》中相关的章节呢？ - TerryE

Answer 2

简短回答 - 您的算法复杂度为O(n²)，就像冒泡排序一样，即两种算法的复杂度基本相同。

- Alex Shesterov

Answer 3

@Kevin说得对，当外部循环进行到第n次迭代时，前n个元素已经处于正确的位置。传统的冒泡排序（比较并交换相邻元素）也是这样做的，但它的优点在于它在进行排序的同时也部分地对列表中的其他项目进行了排序，从而增加了在所有迭代完成之前列表被排序的机会（当在外部循环迭代期间未检测到任何交换时，排序可以结束）。

- Young Bob