3

我是编程的初学者，只是在玩排序并制作了这个算法。它类似于气泡，但它不是比较相邻的对，而是比较像：第一和第二，第一和第三......第二和第三，第二和第四等等。你能告诉我算法的性能/效率是什么，或者将它与气泡进行比较吗？或者至少建议我如何自己解决问题。我感兴趣的是有多少泡沫比这个更好。谢谢你。

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;
        }
    }
}

}

4

3 回答 3

2

您的排序类似于经典冒泡排序，并且应该具有基本相同的性能。

您的排序和冒泡排序都可以被视为选择排序的低效版本。对于所有三种算法，内部循环的每次遍历都会遍历数组的未排序区域，找到最小/最大元素，并将其留在最终位置。这些算法并不相同，因为它们在未排序的区域上执行不同的排列——但是，这种差异在功能上对算法的操作没有贡献。

一旦你认识到这一点，就很容易理解为什么选择排序比其他两种排序具有常数因子优势：其内部循环的每一次通过都需要最少的交换次数（即，最后一次）。相比之下，冒泡排序和你的排序最终可能会在每次内部循环迭代中进行一次交换......

然而，渐近地，所有三种类型都将花费 O(N^2) 时间——具体来说，将有N*(N-1)/2内部循环的迭代。

于 2013-03-27T19:08:33.940 回答
1

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

于 2013-03-27T19:13:54.480 回答
0

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

于 2013-03-27T19:08:04.387 回答