字符串排序

解题思路

就是普通排序的变体，把key值换成了字符串
可以用简单排序暴力破解。
或者用桶排序处理。
各有各的应用场景

暴力简单排序

段错误的原因有很多。数组超出长度是其一。这里数组长度要设置为101。
可变长数组不能初始化。

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

int InsertSort(char str[][101], int n) 
{    
    int size = n - 1;
    int temp = n - 1;
    int i ;
    char c[101] ="";


    for (i = 0; i < size; i++) {
        if (strcmp(str[i],str[temp]) > 0) {
            strcpy(c, str[temp]);
            temp =  i;
            break;
        }
    }

    for (i = size; i > temp; i--) {
        strcpy(str[i], str[i - 1]);
    }

   if (temp != n - 1) { 
       strcpy(str[i], c);
   }

    return 0;
}

int main()
{
    int n;

    while (scanf("%d", &n) != EOF) {
        char str[n][101];
        memset(str, 0, sizeof(str));
        for (int i = 0; i < n; i++) {
            scanf("%s", str[i]);
            InsertSort(str, i + 1);
        }

        for (int i = 0; i < n; i++) {
            printf("%s\n", str[i]);
        }
    }
    return 0;
}

桶排序

桶排序和hashmap好像啊。hashmap里面加上排序就可以变成桶排序了。
不过两者的思想不一样。桶排序是在不同段里面进行排序，hash是映射进行查找。
下面的代码算是结合了桶排序结合了hash关系。
eg:
断点调试是个好东西呀，害！
传出指针要用指针的指针。

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

#define MAX_SIZE 101
#define DAXIE    65
#define XIAOXIE  97

typedef struct _StrNode {
    struct _StrNode *next;
    char str[];
}StrNode;

typedef struct _StrBucket {
    int bucketCount;
    StrNode *bucketNum[];
}StrBucket;

int BucketRelation(int key)
{
    return ((key >= XIAOXIE) ? (key - XIAOXIE + 26) : (key - DAXIE));
}

int InitBucket(StrBucket **bucket, int bucketSize)
{
    StrBucket *bucketTemp = (StrBucket *)malloc(sizeof(StrBucket) + bucketSize * sizeof(StrNode));
    bucketTemp->bucketCount = bucketSize;

    while (bucketSize--) {
        bucketTemp->bucketNum[bucketSize] = (StrNode *)malloc(sizeof(StrNode) + sizeof(char));
        bucketTemp->bucketNum[bucketSize]->next = 0;
        bucketTemp->bucketNum[bucketSize]->str[0] = 0;
    }

    *bucket = bucketTemp;

    return 0;
}

int BucketSort(StrBucket *bucket, char *str)
{
    int site = BucketRelation(str[0]);
    StrNode *node = (StrNode *)malloc(sizeof(StrNode) + strlen(str));
    StrNode *point = bucket->bucketNum[site];

    node->next = 0;
    strcpy(node->str, str);

    if (!(point->next)) {
        point->next = node;
    } else {
        while (point->next) {
            if (strcmp(node->str, point->next->str) > 0) {
                point = point->next;
            } else {
                break;
            }
        }

        node->next = point->next;
        point->next = node;
    }

    return 0;
}

int OutputBucket(StrBucket *bucket)
{
    int i;
    StrNode *point;

    for (i = 0; i < bucket->bucketCount; i++) {
        point = bucket->bucketNum[i]->next;
        while(point) {
            printf("%s\n", point->str);
            point = point->next;
        }
    }
    return 0;
}

int FreeBucket(StrBucket *bucket)
{
    int i;
    StrNode *point, *temp;

    for (i = 0; i < bucket->bucketCount; i++) {
        point = bucket->bucketNum[i];
        while(point) {
            temp = point->next;
            point->next = 0;
            free(point);
            point = temp;
        }
    }

    free(bucket);

    return 0;
}

int main()
{
    int n;
    char str[MAX_SIZE] = "";
    StrBucket *bucket;

    while (scanf("%d", &n) != EOF) {
        bucket = 0;
        InitBucket(&bucket, 52);

        while(n--) {
            memset(str, 0 , sizeof(str));
            scanf("%s", str);
            BucketSort(bucket, str);
        }

        OutputBucket(bucket);
        FreeBucket(bucket);
    }
    return 0;
}