Faits :
A.
A.a. Après avoir tenu, le 23 avril 2012, une séance d'information intitulée " Paysage hospitalier cantonal / Options et place de X._ ", la direction de X._ a dénoncé, le 28 juin 2012, avec effet au 31 décembre 2012, la convention collective de travail Santé 21 (CCT Santé 21) à laquelle elle était soumise, au double motif que le passage de quatre à deux des " membres de la partie employeur " (consécutif à des restructurations) avait créé un déséquilibre, d'une part, et que l'Etat avait décidé de ne pas reconnaître la Fondation de X._ comme étant d'utilité publique, d'autre part.
Le 19 juillet 2012, 129 salariés de l'Hôpital se sont réunis en assemblée générale. Ils ont adopté une " résolution " exprimant leur crainte d'une péjoration des conditions de travail et de l'externalisation de certains services, alors que l'Hôpital était en train de négocier son rattachement au groupe de cliniques privées Y._. Ils ont également pris la décision de mandater les syndicats Z1._ et Z2._ - parties à la CCT Santé 21 - pour mener des négociations, précisant que si celles-ci et tous les moyens usuels de dialogue social devaient échouer, le personnel recourrait alors " aux moyens de lutte prévus par la Constitution fédérale ".
Le 20 juillet 2012, les syndicats Z1._ et Z2._ ont formellement demandé à l'Hôpital l'ouverture de négociations tendant au maintien de la CCT pour tout le personnel.
Le 29 août 2012, une réunion a eu lieu entre les syndicats et la direction de l'Hôpital.
Le 14 septembre 2012, l'Hôpital a demandé à l'office cantonal de conciliation de convoquer d'urgence les parties pour une audience de conciliation, au motif que le personnel avait indiqué par voie de presse qu'il entendait faire grève le 18 septembre 2012. Malgré l'envoi d'un courrier de l'office de conciliation aux deux syndicats, la journée de débrayage a eu lieu à cette date, durant une demi-journée.
Le 6 novembre 2012, la direction de l'Hôpital a notamment informé son personnel que la CCT resterait en vigueur jusqu'au 31 décembre 2012 et que la paix du travail devait être respectée. Elle a averti les collaborateurs qui participeraient à un mouvement de grève pendant leurs heures de travail qu'ils se rendraient coupables d'un abandon de poste.
A.b. Des séances d'information se sont ensuite déroulées au sujet de la reprise des activités opérationnelles de l'Hôpital par Y._, cette dernière subordonnant l'entrée de l'Hôpital dans son groupe au soutien du personnel.
Un vote a été organisé en novembre 2012 et, sur les 335 collaborateurs de l'Hôpital, 280 y ont participé, 202 se sont prononcés en faveur de la reprise de l'Hôpital par Y._, 63 contre et 15 se sont abstenus.
Les négociations qui étaient alors menées avec le Conseil d'Etat ont échoué, de même que celles qui étaient supervisées par l'office de conciliation.
La grève a démarré le 26 novembre 2012.
Par lettre circulaire du 17 décembre 2012, l'Hôpital a annoncé à l'ensemble de ses collaborateurs que l'accord de reprise d'activité de X._ par le réseau de cliniques Y._ avait été signé, suite au vote de novembre 2012 par lequel 85% du personnel s'était exprimé à bulletin secret et 76% des votants avaient soutenu le projet, que les conditions de la CCT seraient encore appliquées jusqu'au 31 décembre 2013, que des nouvelles conditions de travail s'appliqueront dès 2014 et que Y._ s'était engagé à compenser au 1er janvier 2014, pour chaque employé de l'Hôpital, l'éventuelle perte liée aux indemnités ou aux allocations par une augmentation de salaire correspondante, protégeant ainsi les employés contre toute perte pécuniaire liée au changement des conditions de travail.
Fin décembre 2012, le Conseil d'Etat a annoncé, d'une part, qu'il maintiendrait l'Hôpital sur la liste hospitalière du canton jusqu'en 2016, une dérogation étant prévue en ce qui concerne l'application de la CCT pour les années 2014 à 2016 et, d'autre part, qu'il avait négocié des conditions de travail favorables aux employés avec le nouvel employeur Y._.
Le 3 janvier 2013, le syndicat Z1._ a informé la direction de l'Hôpital que la " majorité du personnel " demandait le maintien à long terme de la CCT Santé 21, la conservation de tous les postes de travail et l'absence d'externalisation de services tels que nettoyage, lingerie ou hôtellerie. Il précisait que les grévistes, qui avaient commencé la grève le 26 novembre 2012, étaient prêts à reprendre leurs postes si toutes ces demandes étaient satisfaites.
A.c. Le 23 janvier 2013, le Conseil d'Etat a écrit aux syndicats que Y._ garantissait effectivement l'emploi à tout le personnel de l'Hôpital, qu'en cas d'externalisation d'un service, Y._ veillera à ce que tous les employés concernés soient repris par le nouvel employeur, que Y._ renonçait à toute sanction vis-à-vis des grévistes et que les conditions de la CCT seraient respectées jusqu'au 31 décembre 2013, qu'au-delà de cette date Y._ s'était " formellement engagé à une adaptation à la hausse des salaires du personnel en place, dès 2014, de manière à compenser l'augmentation du temps de travail annoncée, la baisse de certaines indemnités (week-end, jours fériés, piquet), la diminution des périodes considérées comme travail de nuit et la perte progressive des allocations complémentaires pour enfants ", que, sur la base de ces engagements, le gouvernement avait confirmé à Y._ que X._ serait maintenu sur la liste hospitalière du canton de Neuchâtel jusqu'au 31 décembre 2016. Le Conseil d'Etat invitait dès lors les grévistes à profiter de cet engagement et à reprendre le travail et il encourageait vivement les partenaires sociaux à se mettre autour de la table courant 2013. Le même jour, le Conseil d'Etat a communiqué publiquement ces informations.
Le 23 janvier toujours, la direction de l'Hôpital a informé ses employés qu'elle était d'accord de tirer un trait sur le passé et de maintenir à leur poste les employés qui participaient à la grève, pour autant que ceux-ci reprennent le travail d'ici au 31 janvier 2013, ce pour apaiser le climat social. Le même jour, elle a adressé un courrier de mise en demeure formelle aux 26 employés encore en grève, en indiquant que celle-ci était disproportionnée, qu'elle allait à l'encontre de la volonté de la grande majorité du personnel de l'Hôpital et que sa durée excédait largement ce qui était admissible. Chaque gréviste était invité à communiquer, d'ici au 28 janvier 2013 à 12 heures s'il entendait ou non reprendre le travail et la direction a ajouté qu'elle envisageait, à défaut de reprise du travail, de procéder à la résiliation avec effet immédiat du contrat de travail. Des entretiens individuels seraient organisés fin janvier 2013 pour entendre les intéressés avant de prendre les décisions de licenciement.
Par courrier du 28 janvier 2013, 25 employés ont répondu par l'intermédiaire d'un même avocat que leurs revendications concernaient le maintien de la CCT, l'absence d'externalisation des services et l'absence de licenciements. Ils ont ajouté que les conditions de travail de Y._ étaient très largement inférieures à celles prévues dans le contrat collectif, que la proportionnalité de la grève n'était pas une condition prévue à l'art. 28 Cst. et que les menaces de licenciement étaient inadmissibles et pourraient s'apparenter à une tentative de contrainte.
Le 30 janvier 2013, Z1._ et 25 employés de l'Hôpital ont demandé au Tribunal civil du Littoral et du Val-de-Travers de faire interdiction à l'Hôpital de licencier les employés en question, à titre superprovisionnel et provisionnel. Le même jour, le juge civil a déclaré irrecevable la demande en tant qu'elle émanait du syndicat et l'a rejetée en tant qu'elle était formée par les employés, au motif que le maintien des rapports de travail contre l'éventuelle volonté de l'employeur n'était consacré par aucune norme de droit matériel.
Le 31 janvier 2013, l'Hôpital, assisté de son avocat, a entendu les employés, accompagnés par leur avocat. Deux d'entre eux ont manifesté leur volonté de réintégrer leur place de travail dès le 1er février 2013. L'Hôpital leur a confirmé qu'il n'entendait pas les licencier suite à la grève, mais faciliter leur retour grâce à la présence d'un médiateur.
A.d. Par courriers recommandés du 4 février 2013, l'Hôpital a licencié avec effet immédiat chacun des 22 employés ayant finalement refusé de reprendre le travail.
Entre les 5 et 11 février 2013, des négociations ont encore été tentées entre le Conseil d'Etat (à l'initiative de celui-ci), l'Hôpital et Z1._, afin de mettre sur pied une nouvelle CCT (différente de la CCT Santé 21) qui serait acceptable aussi bien pour les employés que pour les employeurs. Le gouvernement cantonal proposait préalablement la suspension immédiate de la grève et des licenciements annoncés. L'Hôpital a consenti à la démarche, mais pas le syndicat. Six rounds de négociations ont été menés, l'Hôpital acceptant à chaque round les conditions préalables fixées, mais le syndicat les refusant, en exigeant que les négociations portent sur la CCT Santé 21 et non sur une nouvelle convention collective.
B.
Le 16 août 2013, les 22 ex-employés de la Fondation de X._ ont introduit contre celle-ci une demande en paiement de salaires, d'indemnités pour licenciement abusif et licenciement immédiat injustifié et d'indemnités pour atteinte à la personnalité. Ils ont conclu à ce que la Fondation verse à chacun d'entre eux un montant déterminé en vertu de l'<ref-law> (entre 11'520 fr. et 35'164 fr.), un montant déterminé en vertu de l'<ref-law> (entre 17'280 fr. et 52'746 fr.), et 3'000 fr. à chaque employé en application de l'<ref-law>, intérêts en sus sur chacun des montants réclamés.
Par réponse du 30 janvier 2014, la Fondation a conclu au rejet des demandes, le cas échéant après compensation du salaire ayant été versé en trop à chacun des demandeurs.
Par jugement du 6 juin 2017, le Tribunal civil du Littoral et du Val-de-Travers a rejeté la demande dans toutes ses conclusions.
Par arrêt du 12 décembre 2017, la Cour d'appel civile du Tribunal cantonal neuchâtelois a rejeté l'appel formé par les 22 demandeurs.
C.
20 demandeurs (sur les 22 ayant participé à la procédure cantonale) exercent un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 12 décembre 2017. Chacun d'eux conclut, personnellement, à son annulation et à sa réforme en ce sens que la défenderesse soit condamnée à verser à chaque demandeur un montant déterminé en vertu de l'<ref-law> (idem conclusions première instance), un montant déterminé en application de l'<ref-law> (idem conclusions première instance) et, en vertu de l'<ref-law>, une indemnité de 3'000 fr. pour chaque demandeur. Les recourants invoquent une violation des art. 5, 9 et 28 Cst., de l'art. 11 CEDH, des art. 27 et 33 de la Constitution de la République et Canton de Neuchâtel (Cst. NE; RSN 101) et ils soutiennent que l'arrêt cantonal transgresse l'<ref-law>, les art. 337 et 337c CO, ainsi que l'<ref-law>.
L'intimée conclut au rejet du recours dans la mesure de sa recevabilité.
Les recourants ont encore déposé des observations.

Considérant en droit :
1.
Formé en temps utile (art. 100 al. 1 et 45 al. 1 LTF), dirigé contre une décision finale (<ref-law>), rendue sur appel des demandeurs par le tribunal supérieur du canton (<ref-law>) dans une affaire relevant du droit du travail (<ref-law>), dont la valeur litigieuse excède 15'000 fr. (<ref-law>), le recours en matière civile est recevable au regard de ces dispositions.
2.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2; <ref-ruling> consid. 5.1) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>).
Concernant l'appréciation des preuves, le Tribunal fédéral n'intervient, du chef de l'art. 9 Cst., que si le juge du fait n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans raisons objectives de tenir compte des preuves pertinentes ou a effectué, sur la base des éléments recueillis, des déductions insoutenables (<ref-ruling> consid. 4.2; <ref-ruling> consid. 4.2; <ref-ruling> consid. 4.3; <ref-ruling> consid. 1.4.3; <ref-ruling> consid. 2.1).
La critique de l'état de fait retenu est soumise au principe strict de l'allégation énoncé par l'<ref-law> (<ref-ruling> consid. 2.3 p. 266 et les références). La partie qui entend attaquer les faits constatés par l'autorité précédente doit expliquer clairement et de manière circonstanciée en quoi ces conditions seraient réalisées (<ref-ruling> consid. 1.3.1 p. 18 et les références). Si la critique ne satisfait pas à ces exigences, les allégations relatives à un état de fait qui s'écarterait de celui de la décision attaquée ne pourront pas être prises en considération (<ref-ruling> consid. 1.3.1 p. 18). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 1.3 p. 261 s.). Les faits nouveaux sont irrecevables devant le Tribunal fédéral (<ref-law>).
2.2. Sous réserve de la violation des droits constitutionnels (<ref-law>), le Tribunal fédéral applique le droit d'office (<ref-law>) à l'état de fait constaté dans l'arrêt cantonal ou, cas échéant, à l'état de fait qu'il aura rectifié. Il n'est toutefois lié ni par les motifs invoqués par les parties, ni par l'argumentation juridique retenue par l'autorité cantonale; il peut donc admettre le recours pour d'autres motifs que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 1.4 et l'arrêt cité).
3.
3.1. La cour cantonale a examiné si les conditions auxquelles l'exercice du droit de grève (art. 28 Cst.) est subordonné étaient réalisées.
Elle juge la grève illicite au (premier) motif que les demandeurs n'ont pas allégué ni prouvé que la décision de la démarrer, tout comme celle de la poursuivre durant les 71 jours qui ont suivi, auraient été prises conformément aux règles du droit civil (<ref-law>) régissant les syndicats Z1._ et Z2._, ni qu'elles auraient été approuvées par la majorité des votants, ou à tout le moins par une partie représentative des travailleurs concernés.
L'autorité précédente retient également (deuxième motif) que, malgré les garanties importantes que les employés ont reçues le 23 janvier 2013 (notamment la prolongation de la CCT jusqu'au 31 décembre 2013), les syndicats ont refusé de négocier une nouvelle CCT. Elle observe que la grève ne se rapportait alors plus de manière prépondérante à la relation de travail, mais qu'elle visait essentiellement des objectifs étrangers à un tel but, notamment la personne du repreneur de l'Hôpital.
Troisièmement, les juges cantonaux, examinant la proportionnalité de la mesure prise (la grève), considèrent que, dès lors que les conditions de la CCT Santé 21 étaient maintenues jusqu'au 31 décembre 2013 et que les acquis salariaux étaient préservés, une grève en janvier 2013 était prématurée et contraire à l'obligation de préserver la paix du travail.
Après avoir qualifié la grève d'illicite, les magistrats cantonaux ont admis l'existence d'un juste motif permettant le licenciement avec effet immédiat, tout en relevant qu'aucun autre argument ne permettait, sous l'angle de l'<ref-law>, de douter de la validité de ce licenciement.
3.2. Les recourants estiment que la grève (soit la décision de la mener et celle de la poursuivre) était licite et que la cour cantonale est arrivée à la conclusion inverse en subordonnant la légitimité de la grève à des conditions (nouvelles) qui ne trouvent, selon elle, aucun fondement à l'art. 28 Cst. (liberté syndicale) (cf. infra consid. 4 et 5).
Partant de leur prémisse (la grève était licite), ils considèrent que l'intimée ne pouvait se prévaloir d'aucun juste motif au sens de l'<ref-law> pour procéder au licenciement immédiat des grévistes (cf. infra consid. 6).
4.
Il s'agit, dans un premier temps, de déterminer le caractère licite ou illicite de la grève menée à partir du 26 novembre 2012 et qui s'est soldée par le licenciement des demandeurs, le 4 février 2013.
4.1. Jusqu'à l'entrée en vigueur, le 1er janvier 2000, de la nouvelle Constitution fédérale du 18 avril 1999, le droit des mesures collectives de combat avait été laissé en jachère par le législateur. Le moyen de lutte en tant que tel n'a d'ailleurs fait l'objet d'aucune disposition du Code des obligations. S'agissant du droit de grève, le Tribunal fédéral avait laissé indécise la question de savoir s'il était fondé sur un droit constitutionnel non écrit. Il avait toutefois soumis la licéité d'une grève à quatre conditions cumulatives: elle doit être appuyée par une organisation ayant la capacité de négocier une convention collective de travail; elle doit poursuivre des buts susceptibles d'être réglementés par une convention collective; elle ne doit pas violer l'obligation de maintenir la paix du travail; elle doit respecter le principe de la proportionnalité (<ref-ruling> consid. 4c p. 245 s.).
Puis, dans un arrêt rendu deux mois après l'adoption de la nouvelle Constitution fédérale, soit six mois avant son entrée en vigueur, le Tribunal fédéral, constatant que le droit suisse ne contenait aucune réglementation explicite du droit de grève, a affirmé l'existence d'une lacune du droit privé et conféré un effet horizontal au droit de grève, reconnaissant formellement l'existence d'un tel droit dans l'ordre juridique suisse (<ref-ruling> consid. 2). Dans ce même arrêt, le Tribunal fédéral a consacré à nouveau les quatre conditions cumulatives précitées dont dépendait la licéité d'une grève, en en déduisant qu'étaient interdites les grèves " sauvages " de travailleurs individuels, les grèves " politiques " n'ayant aucun rapport avec la relation de travail ainsi que les mesures de combat portant sur des objets qui sont déjà réglés dans une convention collective (<ref-ruling> consid. 3b).
La situation s'est encore éclaircie après l'entrée en vigueur de l'art. 28 Cst. La garantie constitutionnelle ancrée dans cette disposition déploie un effet horizontal indirect ( indirekte Drittwirkung) sur les relations de travail dans le secteur privé (<ref-ruling> consid. 4.4.1 et les nombreux auteurs cités). Dès lors, le juge, qui est appelé à se prononcer sur la licéité d'un moyen de combat en droit collectif du travail, est tenu de prendre en compte les garanties constitutionnelles en cause.
S'agissant du contenu de la disposition constitutionnelle, l'art. 28 al. 1 Cst. garantit la liberté syndicale ou liberté de coalition ( Koalitionsfreiheit), qui est un cas spécial de la liberté générale d'association instaurée par l'art. 23 Cst. L'art. 28 al. 2 Cst. dispose que les conflits sont, autant que possible ( nach Möglichkeit), réglés par la négociation ou la médiation. Selon l'art. 28 al. 3 Cst., la grève et le lock-out sont licites quand ils se rapportent aux relations de travail et sont conformes aux obligations de préserver la paix du travail ou de recourir à une conciliation. En vertu de l'art. 28 al. 4 Cst., la loi peut interdire à certaines catégories de personnes de faire grève.
4.2. La grève est le refus collectif de la prestation de travail due, dans le but d'obtenir des conditions de travail déterminées de la part d'un employeur (<ref-ruling> consid. 5.1.1 p. 223; <ref-ruling> consid. 4.3 p. 131; <ref-ruling> consid. 3a p. 283). Concrètement, l'exercice du droit à la grève ne touche pas le rapport contractuel en tant que tel, mais il consiste en une suspension de la prestation de travail par le travailleur, à laquelle répond une suspension du versement de la rémunération par l'employeur (AURÉLIEN WITZIG, Droit du travail, 2018, n. 2078 p. 673; KIENER/ KÄLIN/ WYTTENBACH, Grundrechte, 3e éd. 2018, p. 405 et 408; AUER/ MALINVERNI/ HOTTELIER, Droit constitutionnel suisse, 3e éd. 2013, p. 722).
Il résulte de cette définition que, même si elles représentent des travailleurs syndiqués d'une entreprise déterminée, les personnes extérieures à celle-ci ne sauraient être considérées comme des grévistes, puisqu'elles n'ont aucune obligation de fournir un travail à l'égard de ladite entreprise (<ref-ruling> consid. 4.3 p. 131).
Dans le même arrêt publié, la Cour de céans a toutefois reconnu que, selon les circonstances, un syndicat pouvait mener, sans le concours des travailleurs de l'entreprise visée, une action autonome (<ref-ruling> consid. 4.3 p. 131 s.). Bien qu'il ne s'agisse formellement pas d'une grève (dans le sens strict de la définition qui précède), cette action entre néanmoins dans la catégorie des " moyens de combat relevant du droit collectif du travail " [ Arbeitskampf]) qui doit répondre aux mêmes conditions que celles auxquelles est soumise la grève (<ref-ruling> consid. 4.3 p. 131 s.; cf. toutefois l'arrêt non publié 6B_758/2011 du 24 septembre 2012 qui laisse entendre que les actions autonomes menées par le syndicat ne peuvent pas être appréciées selon les critères régissant la grève licite; sur l'ensemble de la question, cf. WYLER/HEINZER, Droit du travail, 3e éd. 2014, p. 807 ss). Il n'y a en l'espèce pas lieu d'examiner de manière plus approfondie cette problématique, puisque, comme on le verra, la question litigieuse peut être résolue sous un angle distinct.
4.3. Comme on vient de le voir, la licéité de la grève est subordonnée à l'existence de quatre conditions. En tant que " conditions inhérentes " à l'exercice du droit de grève ancré à l'art. 28 al. 3 Cst., elles ne constituent pas une atteinte à la liberté syndicale (qui comprend les mesures destinées à défendre cette liberté) qui emporterait l'obligation de respecter les exigences de l'art. 36 Cst. (cf. <ref-ruling> consid. 5.2.2 p. 264).
Les conditions, dont la réalisation doit être alléguée et prouvée par les employés, sont cumulatives (pour l'énumération des conditions, cf. récemment l'arrêt 8C_80/2018 du 9 octobre 2018 consid. 4.3.1, destiné à la publication) :
4.3.1. La grève doit se rapporter aux relations de travail (condition no 1). Plus précisément, elle doit porter sur une question susceptible d'être réglée par une convention collective de travail (cf. <ref-ruling> consid. 3b; KIENER/ KÄLIN/ WYTTENBACH, op. cit., p. 407; HANS-PETER TSCHUDI, Der Arbeitsfrieden Ziel des Arbeitsrechts, in Mélanges en l'honneur de Jean-Louis Duc, 2001 p. 388). Sont ainsi exclues les " grèves politiques " (au sens large, dans le sens qu'elles n'ont plus de rapport avec la relation de travail) qui tendent à faire pression sur les autorités ou des grèves poursuivant des objectifs corporatistes, extérieurs à l'entreprise ou à la branche (<ref-ruling> consid. 4.4.2 et les références citées; AUER/ MALINVERNI/ HOTTELIER, op. cit., p. 723; WITZIG, op. cit., p. 675).
4.3.2. La grève doit être conforme aux obligations de préserver la paix du travail ou de recourir à une conciliation (condition no 2). L'obligation de maintenir la paix du travail résulte de l'<ref-law>, qui prévoit que les parties à une convention collective de travail sont tenues en particulier de s'abstenir de tout moyen de combat quant aux matières réglées dans la convention. Il s'agit là de l'obligation de paix relative, laquelle doit être distinguée de l'obligation de paix absolue, qui étend l'obligation aux matières qui ne sont pas réglées dans la convention et qui n'existe que si la convention collective l'impose expressément (<ref-ruling> ibidem).
L'obligation de maintenir la paix du travail - tant relative qu'absolue - est liée à l'existence d'une convention collective. Elle prend donc fin de manière automatique à l'échéance de celle-ci ou lorsqu'une partie résilie la convention collective sans proposer de nouvelles négociations sérieuses. Cela ne signifie pas pour autant que la grève est alors immédiatement possible puisque, en vertu du principe de l' ultima ratio (cf. infra consid. 4.3.3), la grève suppose que tous les moyens de négociation et de conciliation aient été tentés et aient échoué (DUNAND/ MAHON/ MATTHEY/ RUSSO, Etude du 11 avril 2016 sur la protection en cas de grève licite établie sur mandat du SECO et de l'OFJ, p. 54 s. [disponible sur le site internet de l'OFJ]).
4.3.3. La grève doit respecter le principe de la proportionnalité (condition no 3). Ce principe découle de l'invitation adressée aux parties à l'art. 28 al. 2 Cst. de régler les conflits " autant que possible " par la négociation ou la médiation (<ref-ruling> consid. 3b). La notion de " proportionnalité " est ici employée non pas pour limiter les restrictions que l'Etat peut apporter à l'exercice d'une liberté (cf. art. 36 al. 3 Cst.; KIENER/ KÄLIN/ WYTTENBACH, op. cit., p. 408), mais comme condition à l'exercice d'un droit par des particuliers (cf. déjà supra consid. 4.3). Dans cette perspective, elle doit être comprise comme renvoyant au critère de la nécessité : la grève ne doit pas être plus incisive qu'il n'est nécessaire pour atteindre le but visé (<ref-ruling> consid. 4.5.4.1 p. 137; cf. GEISER/MÜLLER, Arbeitsrecht in der Schweiz, 3e éd. 2015, n. 909 p. 359); les mesures collectives de combat ne sont licites qu'au titre d' ultima ratio (<ref-ruling> consid. 4.5.4.1 p. 137; cf. Message du 20 novembre 1996 relatif à une nouvelle constitution fédérale, FF 1997 I 1 ch. 212 p. 180). A ce propos, la doctrine moderne écrit que vaut en la matière le principe de la conduite du combat loyal ( faire Kampfführung) (<ref-ruling> ibidem; GEISER/MÜLLER, op. cit., n. 909 p. 359).
Il incombe en principe au juge civil de déterminer si la grève est licite ou illicite, puisqu'il s'agit de l'un des motifs à prendre en considération pour pouvoir statuer sur la validité d'un licenciement ou sur le bien-fondé d'une demande d'indemnité (AUER/ MALINVERNI/ HOTTELIER, op. cit., p. 724). Ainsi, contrairement à ce que tentent de suggérer les recourants, il appartient à ce juge de contrôler si la mesure de combat choisie (la grève) constitue bien une ultima ratio.
4.3.4. Enfin, la grève doit être appuyée par une organisation de travailleurs ( von einer Arbeitnehmervereinigung getragen werden) ayant la capacité de conclure une convention collective de travail (cf. <ref-law>; <ref-ruling> consid. 5.1.1 p. 223; <ref-ruling> consid. 4.4; <ref-ruling> consid. 3b) (condition no 4). Le message du Conseil fédéral relève explicitement qu'il s'agit d'un " acte d'association " (au sens large) et que " la décision [de] recourir [à la grève] doit être prise conformément aux règles topiques du Code civil (<ref-law>) " (message précité, FF 1997 I 1 ch. 212 p. 181; cf. AUER/MALINVERNI/HOTTELIER, op. cit., p. 723).
Contrairement à ce que semblent suggérer les recourants, on ne saurait d'emblée conclure, du seul fait qu'un syndicat décide de mener de façon autonome (cf. supra consid. 4.2) une grève qu'il considère comme licite, que ses actions respectent les conditions posées par l'art. 28 al. 3 Cst. et, partant, qu'elles sont licites. Il incombe au juge de vérifier si la mesure prise est bien un moyen relevant du combat syndical et si elle est " proportionnée " (<ref-ruling> consid. 5.1.2).
5.
C'est à la lumière de ces quatre conditions qu'il faut vérifier si le moyen de combat mis en action par les demandeurs contre la défenderesse le 26 novembre 2012 (début de la grève de 71 jours) était licite.
La Cour de céans procédera à l'examen de ces conditions en reprenant l'ordre établi par l'autorité précédente, étant précisé que la deuxième condition (cf. supra consid. 4.3.2), dont la réalisation n'est pas discutée par les parties, ne sera pas reprise.
5.1. S'agissant de la quatrième condition (appui d'un syndicat; cf. supra consid. 4.3.4) - examinée par elle en lien avec l'exigence de la représentativité des grévistes -, la cour cantonale a jugé que celle-ci n'était pas remplie, au moins depuis la fin du mois de janvier 2013, au (double) motif que les grévistes (26 employés) n'étaient pas représentatifs de l'ensemble du personnel de l'Hôpital (335 employés, soit moins de 8% du personnel), et que les demandeurs n'ont pas indiqué comment la décision de faire grève et celle visant à la poursuivre au cours des 71 jours qui ont suivi ont été prises (résultats des votations au sein des syndicats), ni même si de telles décisions ont effectivement été prises.
Les recourants considèrent que l'exigence de la représentativité des grévistes (vis-à-vis du personnel de l'entreprise), de même que celle de la votation, nécessairement relatée dans un procès-verbal, des membres des syndicats n'ont aucun fondement à l'art. 28 Cst. et que la cour cantonale a violé le droit en soumettant la licéité de la grève à la réalisation de ces conditions (acte de recours p. 11 ss, où les recourants parlent de " double quorum ").
Ces questions, qui appelleraient nécessairement un examen approfondi de la quatrième condition, peuvent toutefois rester ouvertes puisque, comme on va le voir, les critiques soulevées par les recourants en lien avec les conditions nos 1 et 3, sont, d'une manière plus évidente, impropres à remettre en cause la décision de la cour cantonale qualifiant la grève d'illicite (cf. infra consid. 5.2 et 5.3).
5.2. S'agissant de la première condition (selon laquelle la grève doit se rapporter aux relations de travail), la cour cantonale a constaté que si la grève visait initialement le maintien de la CCT Santé 21 (que l'intimée avait dénoncé avec effet au 31 décembre 2012), des garanties importantes ont été fournies aux employés à partir du 23 janvier 2013 et que les syndicats ont refusé de négocier une nouvelle CCT. Les juges cantonaux ont indiqué qu'au-delà de cette date, ils " [peinaient] (...) à comprendre pour quelles raisons certains employés poursuivaient la grève ", que tant les déclarations des témoins entendus en audience que la lecture des 24 procès-verbaux d'entretien du 31 janvier 2013 ne leur fournissaient aucun élément susceptible d'établir la nécessité de poursuivre la grève et que celle-ci poursuivait essentiellement des objectifs ne visant plus la relation de travail, mais la personne du repreneur de l'Hôpital.
5.2.1. Les recourants ne remettent pas en cause ces constats, et en particulier celui visant le motif réel établi par la cour précédente (la reprise de l'Hôpital) sous-tendant la poursuite de la grève, en se pliant aux exigences strictes posées par les art. 97 al. 1 et 106 al. 2 LTF.
Même si l'on admettait (par hypothèse) la recevabilité des critiques soulevées par les recourants (en réalité de simples affirmations), ces critiques devraient quoi qu'il en soit être déclarées infondées. En particulier, c'est en vain que les recourants affirment que les rounds de négociation menés entre les syndicats et le Conseil d'Etat, qui se sont déroulés alors que Y._ avait déjà repris l'Hôpital, démontreraient que les grévistes et les syndicats n'avaient pas pour objectif d'empêcher la reprise de l'entreprise (acte de recours p. 23). Ils omettent en effet de signaler que, selon les constatations cantonales, les syndicats ont expressément refusé les conditions préalables à la négociation (posées par le Conseil d'Etat) consistant en l'approbation de la reprise de l'Hôpital par Y._, ce qui contredit les allégations contenues aujourd'hui dans leur mémoire de recours.
5.2.2. Selon les constatations cantonales, qui lient le Tribunal fédéral (<ref-law>), la grève n'était plus motivée par un désaccord sur des revendications touchant les relations de travail. Elle tendait au contraire à éviter la reprise par Y._ de l'établissement hospitalier, ce qui représente une revendication ne pouvant pas être réglée par une convention collective de travail.
Cela étant, les grévistes ont fait valoir, au moins depuis le 23 janvier 2013, une revendication politique (au sens large). Il en résulte que la première condition n'était pas remplie et que la grève était, à tout le moins depuis le 23 janvier 2013, illicite.
5.3. L'examen de la troisième condition (respect du principe de la proportionnalité) confirme également le caractère illicite de la grève.
5.3.1. On ne saurait retenir la réalisation de cette condition du seul fait que l'employeuse aurait, en dénonçant la CCT Santé 21 le 28 juin 2012 (avec effet au 31 décembre 2012), refusé de poursuivre la collaboration et qu'elle se trouverait ainsi à l'origine du conflit collectif de travail (cf. supra consid. 4.3.2). S'il est vrai que l'employeuse a dénoncé la CCT Santé 21, il est établi que, le 23 janvier 2013, son personnel a obtenu l'assurance de la prolongation de la convention jusqu'au 31 décembre 2013. Partant, au début de l'année 2013, les grévistes ne pouvaient raisonnablement justifier, à l'aune du principe de la proportionnalité, la poursuite de la grève au (seul) motif que l'employeuse aurait elle-même dénoncé la CCT Santé 21 le 28 juin 2012.
5.3.2. Force est de constater qu'en tout cas après le 23 janvier 2013 -si ce n'est avant déjà -, la grève avait perdu son caractère d' ultima ratio, puisqu'à ce moment-là, l'application des conditions de la CCT Santé 21 était garantie pour les 11 mois à venir. Il est d'ailleurs frappant de constater que les recourants eux-mêmes reconnaissent que le maintien des conditions de travail de la CCT Santé 21 jusqu'à la fin de l'année 2013 constitue une réelle concession du repreneur de l'établissement hospitalier. Les recourants refusent toutefois d'en tirer la conclusion qui s'impose (absence de nécessité de poursuivre la grève) au motif que cette concession " est (...) éloignée des revendications des grévistes " qui réclamaient le maintien de la CCT Santé 21 pour une durée indéterminée. Au motif de n'avoir pas obtenu entièrement gain de cause sur leurs revendications, les recourants refusent donc de suspendre la grève. Ce faisant, ils se focalisent exclusivement sur le but poursuivi par le maintien de la grève (qui sera atteint, selon eux, lorsqu'ils obtiendront la totale reconnaissance de leurs revendications) en oubliant que la licéité de ce moyen de lutte (la grève) est subordonnée à la réalisation des conditions tirées de l'art. 28 Cst. Or, le maintien de la CCT Santé 21 jusqu'à la fin de l'année 2013 accordait aux employés un instant de répit qui leur permettait de faire valoir leurs revendications par une mesure moins incisive que la poursuite de la grève. Ils ne pouvaient alors plus refuser de reprendre le travail en justifiant leur position par la perte d'un moyen de pression indispensable pour amener à la reprise des négociations sur une (nouvelle) CCT, puisque l'Hôpital avait accepté cette reprise, contrairement aux grévistes.
A cela s'ajoute que le nouvel employeur s'était engagé à maintenir le niveau des salaires au-delà du 31 décembre 2013 et que, début février 2013, l'intimée avait accepté les conditions préalables à la négociation du Conseil d'Etat consistant en la réintégration de tous les grévistes licenciés, la garantie des emplois et l'égalité des niveaux de salaire sans limite dans le temps, de même que la conclusion d'une nouvelle CCT, soit des points de fait que les recourants ne contestent pas en respectant les exigences strictes des art. 97 al. 1 et 106 al. 2 LTF.
La recherche de solutions consensuelles prévalant lors d'un conflit de travail, il incombait aux grévistes de reprendre le travail comme d'ailleurs aux syndicats de reprendre les négociations.
La critique des recourants se révèle dès lors infondée.
5.3.3. Les arguments qu'ils exposent ne remettent pas en cause cette conclusion.
5.3.3.1. Les recourants laissent entendre qu'en subordonnant la licéité de la grève au respect du principe de la proportionnalité, la cour cantonale a ajouté une condition supplémentaire non prévue par la jurisprudence du Tribunal fédéral. L'argument - qui n'est pas exempt de contradictions puisque les recourants reconnaissent eux-mêmes, dans d'autres passages, l'existence de cette condition - est sans consistance puisque cette condition de validité a toujours été reconnue par la jurisprudence (<ref-ruling> consid. 5.1.1; <ref-ruling> consid. 4.5.4.1; <ref-ruling> consid. 3b).
5.3.3.2. Les recourants sont d'avis que l'arrêt entrepris, qui permet au juge de contrôler la proportionnalité de la mesure de combat mise en oeuvre, instaure un véritable contrôle judiciaire a posteriori de la nécessité de conclure une convention collective et de mettre un terme au conflit social et que la position des juges cantonaux a pour conséquence de permettre à l'employeur d'imposer aux employés et aux syndicats d'accepter de nouvelles conditions de travail qui ne correspondraient pas à toutes leurs revendications.
On ne peut suivre les recourants lorsqu'ils suggèrent de laisser aux seuls partenaires sociaux le soin de déterminer si les mesures de combat prises respectent les règles posées par le législateur. En particulier, on ne saurait considérer qu'une action syndicale serait d'emblée conforme à la Constitution, du seul fait qu'elle a été décidée et menée par un syndicat (cf. supra consid. 4.3.4).
Si le contrôle judiciaire est nécessaire, il ne s'agit en aucun cas pour le juge de favoriser l'une ou l'autre des parties, ni même de restreindre la marge de manoeuvre qui est accordée aux partenaires sociaux. Contrairement à l'opinion professée par les recourants, il ne s'agit pas pour le juge de contrôler a posteriori si les grévistes ont apprécié correctement toutes les circonstances concrètes à la base de leur décision de mener (ou de poursuivre) la grève. Il lui appartient par contre de vérifier la réalisation des conditions posées par le législateur et de contrôler si la mesure de combat choisie (la grève) constitue bien une ultima ratio (cf. supra consid. 4.3.3). Or, en l'espèce, la CCT Santé 21 ayant été prolongée jusqu'à la fin de l'année 2013, la grève ne pouvait plus être considérée comme l' ultima ratio, puisque les parties disposaient à nouveau du temps nécessaire pour rechercher ensemble une solution. On observera en ce sens qu'il résulte de la pratique du Comité de la liberté syndicale de l'OIT - qui, en fonction des circonstances, peut servir à l'interprétation du droit suisse (cf. arrêt 2C_499/2015 du 6 septembre 2017 consid. 5.3.3.1 et 5.3.3.2) - qu'" en règle générale, une décision de suspendre une grève pour une période raisonnable de façon à permettre aux parties de rechercher une solution négociée grâce à des efforts de médiation ou de conciliation ne constitue pas une violation de la liberté syndicale " (BUREAU INTERNATIONAL DU TRAVAIL, La liberté syndicale, Compilation des décisions du Comité de la liberté syndicale, 6e éd. 2018, n. 794 p. 150 [disponible sur le site internet de l'OIT]).
5.3.3.3. Les critiques des recourants visant la (prétendue) violation de diverses règles de droit international, national et cantonal sont, pour autant qu'elles soient recevables, infondées.
C'est en vain que les recourants font référence à la notion de proportionnalité ancrée à l'art. 36 Cst. (cf. supra consid. 4.3.3), qui est une notion distincte de celle utilisée en rapport avec l'art. 28 Cst. et qui n'a aucune incidence sur la situation ici examinée. L'évocation de l'art. 33 de la Constitution neuchâteloise - qui, à l'instar de l'art. 36 Cst., prévoit des cautèles en cas de restrictions aux droits fondamentaux - appelle la même réfutation.
En l'espèce, la condition de proportionnalité découle, comme on l'a vu, de l'art. 28 al. 2 Cst. On ne saurait donc suivre les recourants lorsqu'ils affirment que l'application du principe de la proportionnalité (dans le sens défini supra au consid. 4.3.3) à l'exercice de la liberté syndicale ne repose sur aucune base légale suffisante et, partant, qu'elle viole le principe de la légalité (art. 5 Cst.).
5.3.3.4. S'agissant spécifiquement de l'art. 11 CEDH, celui-ci contient (implicitement) la reconnaissance du droit de grève, en tant qu'élément inhérent à la liberté syndicale. En soi, on ne voit pas en quoi l'art. 11 CEDH plaiderait en faveur de la thèse des recourants puisque, si cette règle conventionnelle reconnaît le droit de grève, elle n'en laisse pas moins en principe une grande liberté aux Etats pour décider des modalités d'exercice du droit syndical, dont le droit d'action collective (grève) (arrêt de la Grande Chambre, cause Demir et Baykara c. Turquie du 12 novembre 2008, requête no 34503/97). Les recourants n'indiquent pas en quoi le principe de la proportionnalité, tel qu'il a été appliqué en l'espèce, irait au-delà de la marge d'appréciation conférée aux Etats. Si les recourants affirment que l'interprétation de l'art. 11 CEDH devrait être faite à la lumière des recommandations de l'OIT, ils n'indiquent toutefois pas expressément à quelles règles ou pratiques ils font référence, de sorte que la Cour de céans ne peut entrer en matière à ce sujet.
5.3.3.5. Les recourants se méprennent lorsqu'ils affirment que la garantie, donnée par l'employeuse le 23 janvier 2013, de ne pas sanctionner les grévistes n'est en réalité pas une concession de l'employeuse puisque celle-ci est tenue de respecter le droit de grève ancré à l'art. 28 Cst. Cette affirmation n'a de sens qu'en cas de grève licite. Or, en l'espèce, l'employeuse a offert cette garantie alors même que, (au moins) depuis cette date, la grève était illicite. Partant, il s'agissait bien d'une concession de l'employeuse, qui renonçait - en cas de suspension de la grève - à prendre des sanctions contre les grévistes.
5.3.3.6. Enfin, les recourants soutiennent, en se référant à l'<ref-ruling> (consid. 4.5.4.1 p. 137) que l'application du principe de la proportionnalité fixe une limite aux actions menées par les grévistes qui correspondrait au cadre dressé par le droit pénal. Concrètement, pour eux, la limite n'est dépassée que lorsque les employés en lutte utilisent des moyens de combat en faisant usage de violence ou en portant atteinte aux biens.
Leur argumentation ne convainc pas. D'une part, les recourants eux-mêmes reconnaissent que la limite ne saurait être fixée par la seule législation pénale, mais qu'elle devra parfois être restreinte, en particulier, indépendamment de celle-ci, " dans les circonstances extrêmes où des grévistes mèneraient leur combat dans le but d'anéantir l'adversaire ".
D'autre part, les recourants font une interprétation trop restrictive des considérations contenues dans l'<ref-ruling> (consid. 4.5.4.1 p. 137). Dans cet arrêt, le Tribunal fédéral, se référant aux mesures collectives de combat, a évoqué l'usage de la violence ou l'atteinte aux biens de l'entreprise à titre d'exemples (" Sont donc par exemple disproportionnés...). Il a toutefois rappelé le principe (critère de nécessité), qui est indépendant de la commission d'infractions pénales et appelle une définition du droit de grève plus étendue que celle qui est aujourd'hui plaidée par les recourants (cf. supra consid. 4.3.3).
5.3.4. La troisième condition n'étant pas remplie, les recourants ne sauraient, pour ce motif également, reprocher à la cour cantonale d'avoir qualifié la grève d'illicite.
Le moyen tiré de la violation de l'art. 28 Cst. se révèle infondé, de même que celui visant la transgression de l'art. 27 Cst./NE, les recourants ne prétendant pas que cette dernière disposition aurait une portée différente de celle résultant de l'art. 28 Cst.
Quant au grief tiré de la violation de l'<ref-law> (disposition qui présuppose l'atteinte illicite à la personnalité), il tombe dès lors à faux.
Enfin, pour autant que les griefs soient recevables au regard de l'<ref-law>, on ne trouve nulle trace d'une violation de l'<ref-law> et de l'<ref-law>.
6.
Les recourants reviennent enfin sur le licenciement prononcé avec effet immédiat.
6.1. Leur argumentation n'est pas exempte de contradictions puisque, même s'ils soutiennent que, dans les circonstances de l'espèce, " la notion de juste motif est une question de droit qui se recoupe (...) avec celle de licéité de la grève " (ce qui implique que, la question de la licéité de la grève étant tranchée, celle du licenciement immédiat l'est aussi), ils contestent néanmoins le raisonnement tenu par la cour cantonale sur ce dernier point. Leur argument central consiste à contester la validité des licenciements pour justes motifs au motif que l'intimée leur a proposé de les réintégrer à leur poste de travail (en cas d'accord avec les syndicats), ce qui démontrerait qu'elle était disposée à travailler à nouveau avec eux et, partant, que le rapport de confiance n'était pas rompu.
6.2. D'emblée, on précisera que, lorsque la grève est illicite, cela ne signifie pas encore automatiquement que les travailleurs qui y ont participé puissent être licenciés avec effet immédiat (cf. <ref-ruling> consid. p. 259). Le juge demeure tenu d'examiner l'ensemble des circonstances qui ont conduit au licenciement abrupt.
En l'occurrence, il n'est toutefois pas douteux que la cour cantonale a procédé à un examen complet. Il résulte notamment des constatations cantonales, qui lient le Tribunal fédéral (<ref-law>), que les grévistes savaient que la grève était illicite ou, à tout le moins, qu'ils devaient douter très sérieusement de sa licéité (et donc se renseigner auprès d'un homme de loi). Le 23 janvier 2013, l'employeuse a communiqué à chacun des grévistes que, de son point de vue, la grève était illicite et que sa poursuite justifiait un licenciement immédiat et cette position a été rappelée lors de chacun des entretiens individuels du 31 janvier 2013. Cela étant, face à des employés qui ne voulaient pas cesser la grève, alors même qu'ils avaient obtenu la garantie que la CCT Santé 21 continuerait à s'appliquer jusqu'au 31 décembre 2013 (alors qu'elle devait initialement cesser de s'appliquer au 31 décembre 2012), l'employeuse pouvait raisonnablement considérer le rapport de confiance comme rompu (cf. <ref-ruling> consid. 3c p. 285), ce d'autant plus qu'un avertissement clair avait été donné aux grévistes au préalable, que des entretiens ont eu lieu avec les employés, assistés de leur avocat, avant la notification du licenciement et qu'à six reprises, en février 2013, les employés auraient eu la possibilité d'être réintégrés s'ils avaient accepté de suspendre immédiatement la grève.
Les recourants usent d'un raccourci lorsqu'ils considèrent que la proposition de réintégration démontre que le rapport de confiance n'était pas rompu. En effet, ils omettent de préciser que cette proposition était subordonnée à l'arrêt immédiat de la grève (illicite) (cf. aussi supra consid. 5.3.4.5). Les recourants n'ayant pas obtempéré, ils ont eux-même écarté cette proposition et ils ne sauraient aujourd'hui s'en prévaloir (comme s'ils l'avaient acceptée) pour en tirer un quelconque argument.
Le moyen tiré de la violation des art. 337 et 337c CO est infondé.
7.
Il résulte des considérations qui précèdent que le recours en matière civile est rejeté dans la mesure où il est recevable.
Les frais et dépens sont mis à la charge des recourants, débiteurs solidaires, qui succombent (art. 66 al. 1, 5 et 68 al. 1, 2 et 4 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière civile est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 16'000 fr., sont mis solidairement à la charge des recourants.
3.
Les recourants, débiteurs solidaires, verseront à l'intimée une indemnité de dépens de 18'000 fr. à titre de dépens.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Neuchâtel, Cour d'appel civile.
Lausanne, le 17 décembre 2018
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente : Kiss
Le Greffier : Piaget