1

所以，我必须对一个整数数组进行排序，以便每个小于某个scanf整数的数字都在左边，这个集合变量在中间，每个更大的数字在右边。我已经覆盖了左右部分，但我不确定如何制作它，所以变量在中间..有什么想法吗？

#include <stdio.h>
int main()
{
    int y, i, k, temp;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    i=0;
    k=1;
    while(i<10)
    {
        while(x[i]>y&&k<10)
        {
            temp=x[k];
            x[k]=x[i];
            x[i]=temp;
            k++;
        }    

        i++;
        k=i+1;
    }


    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }
}

示例输入/输出：

input: x[i]={5,2,1,6,7,3,2,4,5,6}    y=5
output: x[i]={2,1,4,3,2,5,5,7,6,6}
4

4 回答 4

2

您可以使用两个数组来降低代码复杂性，而不是使用一个数组。

搜索小于 y的数字，然后将它们存储在数组中。假设A[ ]
再次搜索大于 y的数字，然后将它们存储在另一个数组中，B[ ]
就像这样..

现在你已经拥有了所有这些。您可以将它们存储在另一个可以称为排序数组的数组中。或者，如果您只想打印它们，那么

  1. 打印第一个数组的所有元素A[ ]
  2. 然后打印y
  3. 最后打印第二个数组的元素B[ ]

就这样。希望这个想法能帮助你快速编码和解决这个问题。

于 2013-10-27T19:23:44.960 回答
1

简单的算法，如果您想自己解决这个问题：

  1. 将整个数组分区为[min..y][y+1..max]，并记下拆分的位置。
  2. 仅将第一部分重新分区为[min..y-1][y..y].

现在应该对数组进行分区[min..y-1][y..y][y+1..max]。

最简单的是有一个 partition_helper 函数来进行分区并返回拆分的位置。然后主分区函数调用此函数两次，并使用正确的参数。

您也可以以另一种方式分区，[min..y-1][y..max]首先将最后一部分重新分区为[y..y][y+1..max]，最终结果应该是相同的。

于 2013-10-27T20:52:40.870 回答
1

您正在寻找类似于快速排序算法中的“分区”的算法。这个想法是有 2 个索引i，jwherei用于遍历数组，而j第一个项目的索引大于或等于y.

在第一个循环之后，您将获得小于y左侧的数字和右侧的其他数字。但是，您实际上希望将等于的值分组，并且只有右侧y的数字大于。y所以我建议在区间 [j,n] 上做同样的事情，但现在当它相等时我也在移动。

// Function to exchange the values of 2 integer variables.
void swap(int *a, int *b) {
    int buf = *a;
    *a = *b;
    *b = buf;
}

// Do the job, in place.
void partition(int *tab, int n, int y) {
    // This first part will move every values strictly lesser than y on the left. But the right part could be "6 7 5 8" with y=5. On the right side, numbers are greater or equal to `y`.
    int j = 0; // j is the index of the position of the first item greater or equal to y.
    int i;
    for (i = 0; i < n; i++) {
        if (tab[i] < y) {
        // We found a number lesser than y, we swap it with the first item that is greater or equal to `y`.
            swap(&tab[i], &tab[j]);
            j++; // Now the position of the first value greater or equal to y is the next one.
        }
    }

    // Basically the same idea on the right part of the array.
    for (i = j; i < n; i++) {
        if (tab[i] <= y) {
            swap(&tab[i], &tab[j]);
            j++;
        }
    }
}

int main() {
    int y;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    partition(x, 10, y);

    int i;
    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }

    return 0;
}

这段代码给出了x = {5,2,1,6,7,3,2,4,5,6};和y = 5：

x[0]=2
x[1]=1
x[2]=3
x[3]=2
x[4]=4
x[5]=5
x[6]=5
x[7]=7
x[8]=6
x[9]=6

前 5 个元素小于 5，其他元素大于或等于 5。

于 2013-10-27T19:07:35.980 回答
1

这是通过分区将数组 x 排序到另一个数组 y 的简单、直接的方法。数字在左侧按 <= 分区排序，在右侧按 > 分区排序：

[编辑]根据 OP 说明说明方法：
如果数组有 2 个等于 p 的元素，则应按如下方式排列：xxxxxppyyyy 其中 xp 和 p 不能与 x 或 y 混合。
除了示例： xxxxxppyyy对于数组来说太长了，所以我假设您的意思是xxxppxxxx（10 个元素，而不是 11 个）。 

int * partitionArr(int *z, int p);

int main(void)
{
    int i, x[10] = {5,8,9,4,2,3,2,4,5,6};
    //int i, x[10] = {3,3,3,3,3,8,8,8,8,8};
    int *y;
    int partition;

    printf("enter a number from 0 to 10\n");
    scanf("%d", &partition);

    y = malloc(sizeof(int) * sizeof(x)/sizeof(x[0])+1); //+1 for inserting partition
    y = partitionArr(x, partition);

    printf("Partition is: %d\n\n", partition);  
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        printf("y[%d] == %d\n", i, y[i]);   
    }
    getchar();
    getchar();

    return 0;
}

int * partitionArr(int *z, int p)
{
    int i=0,j=0;
    int x[10];

    //load y with x
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) x[i] = z[i];

    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]<p) 
        {
            z[j] = x[i];
            j++;
        }
    }   
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]==p) 
        {
            z[j] = x[i];
            j++;
        }
    }   
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]>p) 
        {
            z[j] = x[i];
            j++;
        }
    }
    return z;
}

以下条件的输出： x < P；x== P; x< p（确保 P 在中间的唯一方法）

在此处输入图像描述

于 2013-10-27T19:24:51.947 回答