ALDS1_6_C 2018-2-24

本文主要是介绍ALDS1_6_C 2018-2-24，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<cstdio>
using namespace std;const int MAX = 100000;
const int maxnum = 1000000010;
struct Card {char suit;int value;
};Card L[MAX / 2 + 2], R[MAX / 2 + 2];// 排序和合并
void merge(Card A[], int n,int left, int mid, int right) {int n1 = mid - left;int n2 = right - mid;for (int i = 0; i < n1; i++) {L[i].suit = A[left + i].suit;L[i].value = A[left + i].value;}for (int i = 0; i < n2; i++) {R[i].suit = A[mid + i].suit;R[i].value = A[mid + i].value;}// 两个局部数组最后添加一个比较大的数L[n1].value = R[n2].value = maxnum;int i = 0, j = 0;// 合并for (int k = left; k < right; k++) {if (L[i].value <= R[j].value)A[k] = L[i++];elseA[k] = R[j++];}
}
// 分割
void mergeSort(Card A[], int n, int left, int right) {if (left + 1 < right) {int mid = (left + right) / 2;mergeSort(A, n ,left, mid);mergeSort(A, n, mid, right);merge(A, n, left, mid, right);}
}// 分割
int partition(Card A[],int p, int r) {Card x = A[r];int i = p - 1;for (int j = p; j < r; j++) {if (A[j].value <= x.value) {i++;swap(A[i], A[j]);}}swap(A[i + 1], A[r]);return i + 1;
}// 快速排序
void quickSort(Card A[], int p, int r) {int q;if (p < r) {q = partition(A, p, r);quickSort(A, p, q - 1);quickSort(A, q + 1, r);}
}// 归并排序法是稳定排序，快速排序后的花色和其比较则可得知排序是否稳定的
bool isStable(struct Card C1[], struct Card C2[], int n) {for (int i = 0; i < n; i++) {if (C1[i].suit != C2[i].suit)return false;}return true;
}
Card C1[MAX], C2[MAX];
int main() {int n;scanf("%d", &n);getchar();for (int i = 0; i < n; i++) {scanf("%c %d", &C1[i].suit, &C1[i].value);getchar();C2[i] = C1[i];}// 对于C1数列进行归并排序，对C2数列进行快速排序，然后比较两者排序后的花色// 则可得知快速排序是否稳定mergeSort(C1, n, 0 ,n);quickSort(C2, 0, n -1);if (isStable(C1, C2, n))printf("Stable\n");elseprintf("Not stable\n");for (int i = 0; i < n; i++)printf("%c %d\n", C2[i].suit, C2[i].value);return 0;
}

这篇关于ALDS1_6_C 2018-2-24的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---