performance - 排序算法效率/性能

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

Answer 1

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

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

一旦认识到这一点，就很容易看出为什么选择排序往往比其他两个具有常数因子优势:其内部循环的每次通过都进行所需的最少交换次数(即最后一次交换) ).相比之下，冒泡排序和您的排序可能最终会在内部循环的每次迭代中进行一次交换...

不过，渐近地，所有三种排序都将花费 O(N^2) 时间——具体来说，将会有 N*(N-1)/2内循环的迭代。