有人让我对数组进行排序，我按如下方式进行了排序。现在我们正在争论这是哪种排序技术。在向我解释了他所知道的不同排序技术后，他将其归类为气泡，但我认为不是！但它确实有点！
C代码：
void sort(void){
int a[9]={4,2,1,3,5,7,5,6,8};
int i,j,temp;
for(i=0;i<9;i++)
{
for(j=0;j<i;j++)
{
if(a[j] > a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
for(i=0;i<9;i++)
{
printf("n%d",a[i]);
}
}
这是泡沫，根据我的说法，他同意，但也将前者归类为相同的。我的意思是一定要有一个名字！
for(i=0;i<9;i++)
{
for(j=0;j<8;j++)
{
if(a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
它与冒泡排序最相似。点击此处了解更多信息：http://en.wikipedia.org/wiki/Bubble_sort.
您的循环不同，但它仍然有效，因为您在每次循环中都从j迭代到i，而不是在整个集合上迭代。
例如：
第一次迭代：i=0。第二个循环不执行。
{4,2,1,3,5,7,5,6,8}
第二次迭代：i=1。第二个循环命令4和2，切换它们。
{2,4,1,3,5,7,5,6,8}
第三次迭代：i=2。第二个循环比较2和1，切换。比较4和1，进行切换。
{1,2,4,3,5,7,5,6,8}
第四次迭代：i=3。第二个循环比较1和3，没有切换。比较2和3，无开关。比较4和3，切换。
{1,2,3,4,5,7,5,6,8}
第五次迭代：i=4。第二个循环比较1和5，没有切换。比较2和5、3和5、4和5，没有开关。
{1,2,3,4,5,7,5,6,8}
第六次迭代：i=5。比较1和7、2和7、3和7、4和7、5和7，没有开关。
{1,2,3,4,5,7,5,6,8}
第七次迭代：i=6。比较1和5、2和5、3和5、4和5、5和5，没有开关。比较7和5，切换。
{1,2,3,4,5,5,7,6,8}
第八次迭代：i=7。比较1和6、2和6、3和6、4和6、5和6、五和6，没有开关。比较7和6，切换。
{1,2,3,4,5,5,6,7,8}
第九次迭代：i=8。比较1和8、2和8、3和8、4和8、5和8、6和8、7和8，没有开关。排序完成。
{1,2,3,4,5,5,6,7,8}
因此，您的循环与冒泡排序的不同之处在于，它将当前项与集合的最后一项进行比较，但该技术仍然有效。干得好，我以前从未见过这种变体，在测试之前也不认为它会正确排序。
对我来说，它更像是插入排序的变体。事实上，关键是要注意，在外循环的每一步之后，数组的开头（直到索引i-1）都会进行排序。然后，内部循环将只进行比较，直到j到达第一个索引k，其中a[k]>a[i]是要插入a[i]的位置。之后，您将始终（如果有重复的元素，则并非总是）交换值，因为a[k]<=a[k+1]<=...<=a[i-1]，有效地将元素移动到插入点之后的右侧，就像在规范插入排序中一样。下面的代码包含形式化推理的注释，以便可以通过Frama-C工具进行证明（注意：断言只是为了帮助工具完成证明，真正重要的是loop invariant）。
/*@ predicate sorted{L}(int* a, int n) =
forall integer i,j; 0<=i<=j<n ==> a[i]<=a[j];
*/
/*@ requires valid(a+(0..n-1));
requires n > 0;
assigns a[0..n-1];
ensures sorted(a,n);
*/
void sort(int* a, int n) {
int i,j,temp;
/*@ loop invariant sorted(a,i);
loop invariant 0<=i<=n;
loop assigns i,j,temp,a[0..n-1];
loop variant n-i;
*/
for(i=0;i<n;i++)
{
/*@ loop invariant sorted(a,i);
loop invariant 0<=j<=i;
loop invariant forall integer k; 0<=k<j ==> a[k] <= a[i];
loop assigns j,temp,a[0..j-1],a[i];
loop variant i-j;
*/
for(j=0;j<i;j++)
{
if(a[j] > a[i])
{
//@ assert forall integer k; 0<=k<j ==> a[k]<=a[i];
//@ assert forall integer k; j<=k<i ==> a[i]<a[k];
temp = a[i];
a[i] = a[j];
a[j] = temp;
//@ assert forall integer k; 0<=k<j ==> a[k]<=a[j];
//@ assert forall integer k; j<=k<=i ==> a[j]<=a[k];
//@ assert forall integer k,l; 0<=k<=l<j ==> a[k]<=a[l];
//@ assert forall integer k,l; j<k<=l<i ==> a[k]<=a[l];
}
}
}
}
我认为这不是冒泡排序。对我来说，冒泡排序的一个定义特征是交换相邻的条目。你的算法不能做到这一点。
话虽如此，我不确定它叫什么。注意，它类似于O（n^2）的冒泡排序，尽管它的平均迭代次数应该是冒泡排序的1/2。所以我想说，你已经开发了一种新的O（n^2）排序算法，它的工作量是冒泡排序的一半。我们称之为"Robery"算法。不幸的是，现在没有人对O（n^2）排序算法印象深刻，所以不要指望维基百科页面很快就会出现。。。
确实如此，但通常我们会像这个一样
for(int i = 0;i < 9; i ++ )
for (int j = i +1 ; j < 9 ;j++)
{
if(a[i] >a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
但还是一样。原谅我的英语。
冒泡排序只比较相邻的元素，所以这不是冒泡排序的变体。
我同意@Virgile的观点：这是插入排序的一个变体。每次迭代的外循环都取a[i]和之前排序的子数组，并按排序顺序留下子数组a[0..i]：这就是插入排序不变量。
这与插入排序的典型实现之间的区别在于，一旦找到了a[i]的正确位置，如何在内部循环中使用索引i。通过用索引i重复交换每个索引，将阵列的向右的部分向右移动一个位置；换句话说，CCD_ 21被用作临时存储器。一个典型的实现会使用一个局部变量，但这也同样有效。