在C语言中对整数数组进行排序和去重。

Question

我正在学习C语言，遇到了排序的话题。我写了一个comp()函数，并使用qsort对一个int数组进行排序。现在，下一步任务是需要从数组中删除重复项。
是否可能同时进行排序和删除重复项？

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>    
int indexes[10] = { 0, 98, 45, 65, 45, 98, 78, 56, 65, 45 };

int comp(const void * elem1, const void * elem2) {

    int f = *((int*) elem1);
    int s = *((int*) elem2);

    if (f > s) {    
        return 1;
    }    
    if (f < s) {    
        return -1;
    }    
    return 0;
}

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

int main() {    
    qsort(indexes, sizeof(indexes) / sizeof(int), sizeof(int), comp);    
    printIndexArray();    
    return 0;
}

- user2800463

---

你正在使用内置函数进行排序，请编写自己的函数。 - Grijesh Chauhan

Answer 1

由于您的数字已经排序，因此删除重复项很容易。在C++中，甚至内置了std::unique来实现：

http://en.cppreference.com/w/cpp/algorithm/unique

假设您想自己完成，可以按照与unique相同的方式进行：

int* unique (int* first, int* last)
{
  if (first==last) return last;

  int* result = first;
  while (++first != last)
  {
    if (!(*result == *first)) 
      *(++result)=*first;
  }
  return ++result;
}

- StilesCrisis

---

我该如何使用上述方法？我刚开始学习，因此我的指针并不好。您能帮助将这个独特的函数整合到我的代码中吗？ - user2800463

只需调用 unique(indexes, indexes + (sizeof(indexes) / sizeof(int)));。 - StilesCrisis

顺便说一句，我建议创建一个宏或类似的东西来获取数组大小。例如 #define arrsize(x) (sizeof(x) / sizeof(x[0]))。 - StilesCrisis

如果你有这样的宏，它将是 unique(indexes, indexes + arrsize(indexes));。 - StilesCrisis

Answer 2

这是使用合并排序算法去重的代码。以下代码段实现了去重功能：

else if(a[p1] == a[p2])
{
    merged[p] = a[p1];
    p1++;
    p2++;
}

那是迭代归并排序，而递归版本会更容易。

#include <stdio.h>
#include <stdlib.h>

#define min(a,b) (((a) < (b)) ? (a) : (b))

int indexes[10] = { 0, 98, 45, 65, 45, 98, 78, 56, 65, 45 };

void merge(int *a, int s, int m, int e)
{
    int p1 = s;
    int p2 = m + 1;
    int * merged = (int*)malloc(sizeof(int) * (e - s + 1));
    int p = 0;
    while(p1 < m + 1 && p2 < e + 1)
    {
        if(a[p1] > a[p2])
        {
            merged[p] = a[p2];
            p2++;
        }
        else if(a[p1] == a[p2])
        {
            merged[p] = a[p1];
            p1++;
            p2++;
        }
        else
        {
            merged[p] = a[p1];
            p1++;
        }
        p++;
    }

    while(p1 < m + 1)
    {
        merged[p++] = a[p1++];
    }

    while(p2 < e + 1)
        merged[p++] = a[p2++];

    int i;
    for(i = 0;i < (e -s+1); i++)
    {
        a[s + i] = merged[i];
    }

    free(merged);
}

void merge_sort(int *a, int n)
{
    int width;
    for(width = 1; width < n; width = 2 * width)
    {
        int i;
        for(i = 0; i < n; i = i + 2 * width)
        {
            merge(a, i, min(i + width - 1, n - 1), min(i + 2 * width - 1, n - 1) );
        }
    }
}

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

int main()
{
    merge_sort(indexes, sizeof(indexes) / sizeof(int) );
    printIndexArray();
    return 0;
}

- jfly

Answer 3

#include <stdio.h>
#include <stdlib.h>

int indexes[10] = { 0, 98, 45, 65, 45, 98, 78, 56, 65, 45 };

size_t undup(int array[], size_t len)
{
size_t src,dst;

if (!len) return 0;
for (src=dst=1; src < len; src++) {
        if (array[dst-1] == array[src]) continue;
        array[dst++] = array[src];
        }
return dst;
}

int comp(const void * elem1, const void * elem2) {

    int f = *((int*) elem1);
    int s = *((int*) elem2);

    if (f > s)     return 1;
    if (f < s)     return -1;

    return 0;
}

void printIndexArray(size_t len) {
    size_t i = 0;
    for (i = 0; i < len; i++) {
        printf("array[%zu] is %d\n", i, indexes[i]);
    }
}

int main() {
    size_t len = 10;
    printf("Before sort\n" );
    printIndexArray(len);

    qsort(indexes, sizeof indexes / sizeof indexes[0], sizeof indexes[0], comp);
    printf("After sort\n" );
    printIndexArray(len);

    len = undup(indexes,10);
    printf("After undup\n" );
    printIndexArray(len);

    return 0;
}

- wildplasser

Answer 4

是的

这可以通过归并排序来实现。如果左右两边相同，只需合并一个值即可。

- Ed Heal

Answer 5

简短的回答是：是的。

长的回答是：总是有可能的，但实现的复杂度取决于你使用的算法。

像快速排序、慢速排序、桶排序和直接基数排序这样更复杂的算法不适合这种增强，因为它们依赖于数据在连续数组中，可以隐式地分成子数组。因此，当你检测到重复时，你不能轻易地将其删除。虽然这是可能的，但对于初学者来说肯定不是一个问题。

较简单的原地排序算法，如冒泡排序、插入排序和希尔排序，使得这个过程相对容易：你只需用一个比所有合法值都大的哨兵值替换掉你检测到的重复项之一，让它上升到顶部。之后，你只需要取出哨兵值的精华就行了。

真正适合去除重复项的算法是那些在过程中使用中间数组进行增长/缩小的算法；在这些情况下，当你检测到重复项时，你可以缩小或跳过其中一个中间数组。候选算法是归并排序和堆排序。

请注意，更明智的做法是先对数组进行排序，然后在第二个独立步骤中消除重复项。为什么呢？因为消除重复项会增加排序算法内部循环的复杂度，在大多数相关情况下，其时间复杂度为O(n*log(n))。但是，从已排序的数组中消除重复项是一个O(n)操作，使得分裂操作比融合操作更快。

- cmaster - reinstate monica