耐心排序

选一种语言就能看到代码

def patience_sort(a):
    piles = []
    for value in a:
        for pile in piles:
            if pile[-1] >= value:
                pile.append(value)
                break
        else:
            piles.append([value])
    for k in range(len(a)):
        best = min(range(len(piles)), key=lambda i: piles[i][-1])
        a[k] = piles[best].pop()
        if not piles[best]:
            piles.pop(best)

function patienceSort(a) {
  const piles = [];
  for (const value of a) {
    const pile = piles.find((p) => p.at(-1) >= value);
    if (pile === undefined) piles.push([value]);
    else pile.push(value);
  }
  for (let k = 0; k < a.length; k++) {
    let best = 0;
    for (let i = 1; i < piles.length; i++) {
      if (piles[i].at(-1) < piles[best].at(-1)) best = i;
    }
    a[k] = piles[best].pop();
    if (piles[best].length === 0) piles.splice(best, 1);
  }
}

void patience_sort(int a[], int n) {
    int* head = malloc(sizeof(int) * (n + 1));
    int* below = malloc(sizeof(int) * (n + 1));
    int* out = malloc(sizeof(int) * (n + 1));
    int piles = 0;
    for (int i = 0; i < n; i++) {
        int p = 0;
        while (p < piles && a[head[p]] < a[i]) p++;
        below[i] = p < piles ? head[p] : -1;
        if (p == piles) piles++;
        head[p] = i;
    }
    for (int k = 0; k < n; k++) {
        int best = 0;
        for (int p = 1; p < piles; p++) {
            if (a[head[p]] < a[head[best]]) best = p;
        }
        out[k] = a[head[best]];
        head[best] = below[head[best]];
        if (head[best] < 0) head[best] = head[--piles];
    }
    memcpy(a, out, sizeof(int) * n);
    free(head);
    free(below);
    free(out);
}

void patience_sort(std::vector<int>& a) {
    std::vector<std::vector<int>> piles;
    for (int value : a) {
        size_t p = 0;
        while (p < piles.size() && piles[p].back() < value) p++;
        if (p == piles.size()) piles.push_back({});
        piles[p].push_back(value);
    }
    for (size_t k = 0; k < a.size(); k++) {
        auto best = std::min_element(
            piles.begin(), piles.end(),
            [](const std::vector<int>& p, const std::vector<int>& q) {
                return p.back() < q.back();
            });
        a[k] = best->back();
        best->pop_back();
        if (best->empty()) piles.erase(best);
    }
}

static void PatienceSort(int[] a) {
    var piles = new List<Stack<int>>();
    foreach (int value in a) {
        int p = piles.FindIndex(pile => pile.Peek() >= value);
        if (p < 0) {
            piles.Add(new Stack<int>());
            p = piles.Count - 1;
        }
        piles[p].Push(value);
    }
    for (int k = 0; k < a.Length; k++) {
        int best = 0;
        for (int p = 1; p < piles.Count; p++) {
            if (piles[p].Peek() < piles[best].Peek()) best = p;
        }
        a[k] = piles[best].Pop();
        if (piles[best].Count == 0) piles.RemoveAt(best);
    }
}

static void patienceSort(int[] a) {
    List<Deque<Integer>> piles = new ArrayList<>();
    for (int value : a) {
        int p = 0;
        while (p < piles.size() && piles.get(p).peek() < value) p++;
        if (p == piles.size()) piles.add(new ArrayDeque<>());
        piles.get(p).push(value);
    }
    for (int k = 0; k < a.length; k++) {
        int best = 0;
        for (int p = 1; p < piles.size(); p++) {
            if (piles.get(p).peek() < piles.get(best).peek()) best = p;
        }
        a[k] = piles.get(best).pop();
        if (piles.get(best).isEmpty()) piles.remove(best);
    }
}