2

有人让我对数组进行排序，我做了如下。现在我们正在争论这是哪种分类技术。在向我解释了他所知道的不同分类技术后，他将其归类为气泡，但我认为不是！但它确实排序！

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

}
4

5 回答 5

8

它与冒泡排序最相似。在此处阅读更多信息：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、5 和 6，没有开关。比较 7 和 6，开关。

{1,2,3,4,5,5,6,7,8}

第九次迭代：i = 8。比较 1 和 8、2 和 8、3 和 8、4 和 8、5 和 8、5 和 8、6 和 8、7 和 8，没有开关。排序完成。

{1,2,3,4,5,5,6,7,8}

因此，您的循环与冒泡排序的不同之处在于它将当前项与集合的最后一项进行比较，但该技术仍然有效。干得好，我以前从未见过这种变化，并且在测试之前认为它不会正确排序。

于 2013-08-09T12:48:13.760 回答
4

在我看来，它更像是插入排序的一种变体。实际上，关键是要注意，在外循环的每一步之后，对数组的开头（直到索引 i-1）进行排序。然后，内部循环只会进行比较，直到j到达第一个索引kwhere 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];
       }
    }

}
}
于 2013-08-09T14:11:54.607 回答
1

我会说这不是冒泡排序。对我来说，冒泡排序的定义特征之一是交换相邻条目。你的算法不会那样做。

话虽如此，我不确定它叫什么。请注意，它像冒泡排序一样 O(n^2)，尽管它的平均迭代次数应该是冒泡排序的 1/2。所以我想说你开发了一种新的 O(n^2) 排序算法，它的工作量只有冒泡排序的一半。我们将其称为“Robery”算法。不幸的是，这些天没有人对 O(n^2) 排序算法印象深刻，所以不要指望维基百科页面很快就会出现......

于 2013-08-09T13:48:11.863 回答
0

是的，但我们通常是这样排序的

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;

       }
 }

但它是一样的。原谅我的英语。

于 2013-08-09T13:06:43.193 回答
0

冒泡排序仅比较相邻元素，因此这不是冒泡排序的变体。

我同意@Virgile：这是插入排序的一种变体。每次迭代的外循环都取a[i]它之前的排序子数组，并以排序顺序离开子数组a[0..i]：这是插入排序不变量。

这与插入排序的典型实现之间的区别在于，i一旦找到了正确的位置，索引如何在内部循环中使用a[i]。通过将每个索引与 index 重复交换，数组右侧的部分向右移动了一个位置i；换句话说a[i]，用作临时存储。一个典型的实现会使用一个局部变量，但这也同样有效。

于 2013-08-09T18:55:53.280 回答