在C语言中实现稳定的按长度排序

Question

我正在解决一个编码问题，需要按单词长度对字符串指针数组进行排序。我有一个使用索引操作的代码想法，但希望得到一些帮助来检查逻辑是否正确。以下是我的代码:

void len_sort(char** words, int num_words)
{
    int index=0;
    int isSorted=0;
    int string1_len;
    int string2_len;
    while(isSorted==0)
    {
        for(index=0;index<num_words;index++)
        {
            printf("%s\n", words[index]);
            string1_len=strlen(words[index]);
            if((index+1)==num_words)
                string2_len=strlen(words[index]);
            else
                string2_len=strlen(words[index+1]);

            if(string1_len<string2_len)
            {
                swap(words[index], words[index+1]);
            }
        }

        isSorted=1;

        for(index=0;index<num_words;index++)
        {
            string1_len=strlen(words[index]);
            if(index+1==num_words)
                string2_len=strlen(words[index]);
            else
                 string2_len=strlen(words[index+1]);
            if(string1_len>string2_len)
            {
                isSorted=0;
            }
        }

    }


}
void swap(char* word1, char* word2)
{

    char* temp;
    word1=word2;
    word2=temp;

}

我可以不按字母顺序排序，需要保持单词在数组中的顺序。例如：如果我有以下内容：

car
x
horse
a

我的输出应该像这样：

x
a
car
horse

保持x在数组中在a之前的事实是正确的。 是否有更好的方法来提高这种排序的效率？

- JustaRedShirt

---

你需要重新排序实际内存，还是可以使用指针来处理？ - Alexandre Cassagne

另外，您需要什么样的复杂度？ - Alexandre Cassagne

这段代码不正确，因为swap()函数几乎什么也没做。 - MikeCAT

我目前对时间复杂度并不挑剔。也许以后我会尝试重新设计为O(N)。我可以使用指针，保存单词的数组是一个指针数组（char**），或者说是一个指向字符串的指针数组？我想这就是我应该说的。 - JustaRedShirt

对于交换函数，您应该利用strcpy或memcpy将第一个单词传输到临时缓冲区中，然后将第二个单词传输到第一个单词中，然后将新的第二个单词设置为临时缓冲区的内容。您可以将这样的缓冲区定义为char []类型，并且可能需要将最大单词长度传递到交换函数中，以便可以分配正确数量的内存。 - Mike -- No longer here

Answer 1

这个交换函数没有实现任何有意义的操作。如果你想要交换两个指针，应该像这样：

void swap(char **word1, char **word2)
{
    char *temp;

    temp = *word1;
    *word1 = *word2;
    *word2 = temp;

}

现在，为了稳定排序，我们只能交换前一个元素比后一个元素长的情况。每次交换后，数组就会更加有序一步。我们从头开始排序。

void len_sort(char** words, int num_words)
{
    int i = 0; //start from the beginning.
    while(i < num_words-1) //till the last pair.
    {
        if(strlen(words[i]) > strlen(words[i+1])){//if a mismatch occur
            swap(&words[i], &words[i+1]);//fix it
            i = -1;//and start from the beginning 
        }
        i++;//so far sorted, try next pair
    }
}

测试:

int main()
{
    char d[][30] = {"car", "x", "horse", "a"};
    char *s[4];
    int i;

    //our function sort through pointer
    for(i=0; i<4; i++)
        s[i] = d[i];

    len_sort(s, 4);
    for(i=0; i<4; i++)
        printf("%s ", s[i]);
    puts("");

    return 0;
}

输出：

x a car horse

- Shakil Ahamed

Answer 2

我有一个建议。为什么不创建一对整数，第一个表示长度，第二个表示字符串的索引，然后再将它们排序呢。

下面是我的代码：

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

typedef struct {
  int first;
  int second;
} pair;

int cmp(pair a, pair b){
  return (a.first > b.first) || ((a.first == b.first) && (a.second > b.second));
}

// you can use your favorite sort algorithm
// Since in some condition, quick_sort runs in O(n^2)
void quick_sort (pair *a, int n) {
    int i, j;
    pair p, t;
    if (n < 2)
        return;
    p = a[n / 2];
    for (i = 0, j = n - 1;; i++, j--) {
        while (cmp(a[i],p))
            i++;
        while (cmp(p,a[j]))
            j--;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    quick_sort(a, i);
    quick_sort(a + i, n - i);
}

char** len_sort(char** words, int num_words){
  pair my_pairs[num_words];

  // iterate in O(n)
  for (int i = 0; i < num_words; ++i) {
    my_pairs[i].first = strlen(words[i]);
    my_pairs[i].second = i;
  }

  // sort in O(nlogn)
  quick_sort(my_pairs, num_words);

  // iterate through sorted and create ne wlist of words in O(n)
  char** new_word_list = (char**) malloc(num_words*sizeof(char*));
  for (int i = 0; i < num_words; ++i)
    new_word_list[i] = words[my_pairs[i].second];

  return new_word_list;
}

- ibrohimislam

---

如果我没记错的话，快速排序是 不 稳定的，就像这里所说的：https://dev59.com/lHI_5IYBdhLWcg3wHvQ5。你可以使用归并排序来实现。或者，你只是因为称它为“quick_sort”而感到困惑？ - Craig Estey

是的，您可以使用任何类型的排序算法，我只想强调解决它们的逻辑。只需将其替换为归并排序或任何类型的排序即可。 - ibrohimislam

Answer 3

您可以使用组合合成键进行排序，例如：

uint32_t key = (strlen(s) << 16) | line_no;

- olegarch