识别此排序算法

Question

在浏览我在大学一年级写的旧代码时，我发现以下代码段标记为"冒泡排序"。(这里n是数组的大小；例如，对于10个元素的数组，n＝10(。

for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++) {
if(arr[i] > arr[j]) {
int temp  = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

现在，我可以看出，这当然不是冒泡排序，但可能是一个非常糟糕的实现。事实上，它有效，我很好奇这是一个已经存在的算法，还是我自己提出的算法，尽管它非常低效。

Answer 1

这是一个糟糕的选择排序实现

for (j = 0; j < n-1; j++) {
int iMin = j;
for (i = j+1; i < n; i++) {
if (a[i] < a[iMin]) {
iMin = i;
}
}
if (iMin != j) {
swap(a[j], a[iMin]);
}
}

你的狙击手不是在未排序的部分中找到最小值，然后用交换把它放在排序的部分的末尾，而是在每次找到"潜在最小值"时交换，即一个小于排序部分末尾的值的值。这是低效的，因为互换的成本远远高于指数分配。