题解 | #字符串排序#

#include<stdio.h>
#include<string.h>
#define MaxSize 105
int partition(int* len, int* tag, int low, int high) {
    int pivot = len[low];
    int pivotpos = tag[low];
    while (low < high) {
        while (low < high && len[high] >= pivot)high--;
        len[low] = len[high];
        tag[low] = tag[high];
        while (low < high && len[low] <= pivot)low++;
        len[high] = len[low];
        tag[high] = tag[low];
    }
    len[low] = pivot;
    tag[low] = pivotpos;
    return low;
}
void quickSort(int* len, int* tag, int low, int high) {
    if (low < high) {
        int pivotpos = partition(len, tag, low, high);
        quickSort(len, tag, low, pivotpos - 1);
        quickSort(len, tag, pivotpos + 1, high);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    getchar();//此处极易出错
    char S[n][MaxSize];
    int len[n], tag[n], i, j;
    for (i = 0; i < n; i++) {
        gets(S[i]);
        if (strcmp(S[i], "stop") == 0)break;
        len[i] = strlen(S[i]);
        tag[i] = i;
    }
    n = i;
    quickSort(len, tag, 0, n - 1);
    for (i = 0; i < n; i++)
        puts(S[tag[i]]);
    return 0;

}