Faits:
A.
X._, ressortissant kosovar, né en 1967, a travaillé en Suisse comme saisonnier de 1990 à 1998, puis a déposé une demande d'asile rejetée par l'Office fédéral des réfugiés le 12 octobre 1999. Dans son pays d'origine, X._ a eu trois enfants, nés en 1994, 1997 et 2000, avec son ex-épouse, dont il a divorcé le 11 mars 2004.
Le 26 octobre 2006, X._ s'est marié dans le canton de Neuchâtel avec une ressortissante suisse, Y._, née en 1964, et a obtenu une autorisation de séjour, régulièrement renouvelée jusqu'au 26 octobre 2009. Avisé que le couple vivait séparé depuis mi-septembre 2008 et que le divorce des époux avait été prononcé le 7 septembre 2010, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a refusé de prolonger l'autorisation de séjour de X._, par décision du 13 décembre 2011.
Saisi d'un recours de l'intéressé contre cette décision, le Département de l'économie du canton de Neuchâtel (ci-après: le Département) l'a rejeté, par prononcé du 3 octobre 2012. Il a retenu en bref que l'union conjugale ayant duré moins de trois ans, le recourant ne pouvait bénéficier d'une autorisation de séjour sur la base de l'art. 50 al. 1 let. a de la loi fédérale sur les étrangers (LEtr; RS 142.20) et qu'il ne remplissait pas davantage les conditions du cas de rigueur au sens de l'art. 50 al. 1 let. b et al. 2 LEtr. Divorcé de son épouse suisse avec laquelle il n'avait pas eu d'enfant, il ne pouvait pas non plus se prévaloir de l'art. 8 § 1 CEDH.
B.
X._ a recouru contre ce prononcé auprès de la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal), en faisant valoir que les conditions de l'art. 50 al. 1 let. a et b et al. 2 étaient réunies et qu'il pouvait se prévaloir de l'art. 8 § 1 CEDH en raison de la relation qu'il entretenait depuis quatre ans avec son amie suisse.
Par arrêt du 22 mai 2013, le Tribunal cantonal a rejeté le recours. Il a retenu que seul le refus de la prolongation de l'autorisation de séjour en application de l'art. 50 al. 1 let. b et al. 2 LEtr pouvait faire l'objet du recours, dès lors que, devant le Département, le recourant s'était uniquement attaché à démontrer que des raisons personnelles majeures justifiaient la poursuite de son séjour en Suisse, mais que les conditions pour obtenir une autorisation de séjour à ce titre n'étaient pas remplies. Comme le recourant n'avait pas invoqué l'art. 50 al. 1 let. a LEtr ni l'art. 8 CEDH devant le Département, il n'avait pas à examiner ces aspects qui sortaient de l'objet du litige.
C.
Agissant par la voie du recours en matière de droit public, subsidiairement du recours constitutionnel subsidiaire, X._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 22 mai 2013 et demande au Tribunal fédéral de prolonger son autorisation de séjour.
Le Tribunal cantonal se réfère à son arrêt et conclut au rejet du recours, de même que le Service des migrations, sous suite de frais. Le Département a répondu tardivement qu'il n'avait pas d'observations à formuler. L'Office fédéral des migrations propose le rejet du recours.
D.
Par ordonnance présidentielle du 27 juin 2013, la demande d'effet suspensif présentée par le recourant a été admise.

Considérant en droit:
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. En l'espèce, la vie conjugale du recourant avec une ressortissante suisse ayant cessé d'exister, celui-ci ne peut pas déduire un droit à une autorisation de séjour de l'art. 42 al. 1 LEtr ni de l'art. 49 LEtr. Reste l'art. 50 al. 1 LEtr qui subordonne la prolongation de son autorisation de séjour à certaines conditions dont se prévaut le recourant. En pareilles circonstances, il y a lieu d'admettre un droit de recourir sous l'angle de l'art. 83 let. c ch. 2 LTF, car le point de savoir si les conditions posées par cette disposition sont effectivement réunies en l'espèce relève de l'examen au fond (cf. arrêt 2C_460/2009 du 4 novembre 2009, consid. 2.1.1 non publié aux <ref-ruling>).
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>, le présent recours est donc en principe recevable comme recours en matière de droit public. Partant, le recours constitutionnel subsidiaire (<ref-law>) déposé par le recourant est irrecevable.
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, y compris la violation des droits fondamentaux (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation de l'<ref-law>. En outre, le Tribunal fédéral fonde son raisonnement juridique sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou incomplète - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 7.1 p. 51) - ou encore en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (cf. <ref-ruling>01 consid. 3 p. 104; arrêt 2C_990/2012 du 7 mai 2013 consid. 3.2).
3.
Invoquant les art. 29 et 9 Cst., le recourant reproche au Tribunal cantonal d'avoir violé son droit d'être entendu et commis un déni de justice en refusant arbitrairement de se prononcer sur l'ensemble des griefs qu'il avait soulevés, alors même que le Département avait examiné lui-même si la prolongation de son autorisation de séjour pouvait être accordée en vertu de l'art. 50 al. 1 let. a LEtr et s'il pouvait se prévaloir de l'art. 8 CEDH.
3.1. Le Tribunal cantonal a estimé que l'art. 43 al. 1 de la loi cantonale sur la procédure et la juridiction administratives (LPJA; RSNE 152.30), prévoyant que l'autorité de recours n'est pas liée par les motifs invoqués à l'appui du recours, n'impliquait pas un contrôle de la décision attaquée sous tous ses aspects, mais uniquement un examen des points effectivement litigieux. Il en a déduit que, dans la mesure où le recourant s'était uniquement attaché, devant le Département, à démontrer que des raisons personnelles majeures justifiaient la poursuite de son séjour en Suisse en application de l'art. 50 al. 1 let. b et al. 2 LEtr, il avait sciemment réduit l'objet du litige à cette question qui seule pouvait être examinée devant lui.
3.2. La jurisprudence a déduit du droit d'être entendu (art. 29 al. 2 Cst.) le devoir pour le juge de motiver sa décision, afin que le justiciable puisse la comprendre, la contester utilement s'il y a lieu et exercer son droit de recours à bon escient. Pour répondre à ces exigences, le juge doit mentionner, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. Il n'a toutefois pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 2.2 p. 84; <ref-ruling> consid. 5.1 p. 237 et les arrêts cités). Dès lors que l'on peut discerner les motifs qui ont guidé la décision de l'autorité, le droit à une décision motivée est respecté même si la motivation présentée est erronée. La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (arrêts 2C_23/2009 du 25 mai 2009 consid. 3.1, in RDAF 2009 II p. 434; 1C_246/2013 du 4 juin 2013 consid. 2.1). Une autorité se rend coupable d'une violation du droit d'être entendu si elle omet de se prononcer sur des griefs qui présentent une certaine pertinence ou de prendre en considération des allégués et arguments importants pour la décision à rendre (<ref-ruling> consid. 5.2 p. 248; <ref-ruling> consid. 2b p. 102 ss).
En l'espèce, le Tribunal cantonal n'a pas omis de se prononcer sur la non-prolongation de l'autorisation de séjour du recourant en vertu des art. 50 al. 1 let. a LEtr et 8 § 1 CEDH, mais a considéré que ces griefs ne pouvaient plus être soulevés devant lui, puisque le recourant ne s'en était pas prévalu devant le Département. Ce faisant, il n'a pas violé le droit d'être entendu du recourant, mais a expliqué pourquoi il ne revoyait pas d'office la décision de l'autorité inférieure sur ces deux points. Reste à déterminer si son argumentation est ou non fondée au regard du grief d'arbitraire invoqué par le recourant.
3.3. Une décision est arbitraire lorsqu'elle contredit clairement la situation de fait, lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 7.1 p. 51 et les arrêts cités).
3.4. L'art. 43 LPJA dispose que:
" 1. L'autorité de recours n'est pas liée par les motifs invoqués à l'appui du
recours.
2. Les constatations de fait ne lient pas l'autorité de recours.
3. L'autorité de recours n'est pas liée par les conclusions des parties; elle
peut réformer, au détriment du recourant, la décision attaquée ou
accorder plus que le recourant n'avait demandé; elle doit cependant
donner aux parties l'occasion de se prononcer ou de retirer les recours. "
Il ressort expressément de cette disposition que les autorités de recours ne sont pas liées par les motifs, ni par les conclusions des parties, contrairement à la procédure devant le Tribunal fédéral où les conclusions des parties déterminent, avec la décision attaquée, l'objet de la contestation (cf. <ref-law>; arrêt 2C_649/2013 du 16 juillet 2013 consid. 4 et les arrêts cités). C'est sans doute pourquoi le Département a examiné, certes sommairement, mais d'office, si l'autorisation de séjour du recourant pouvait être prolongée en vertu des art. 50 al. 1 let. a LEtr ou 8 § 1 CEDH, quand bien même le recourant n'avait pas fondé l'argumentation de son recours devant lui sur ces deux dispositions. On ne voit donc pas que le Tribunal cantonal ait pu, sous peine de tomber dans l'arbitraire, refuser d'entrer en matière sur ces deux points, en se référant seulement aux décisions des autorités inférieures, alors que le recourant les contestait devant lui. Sa position est d'autant plus insoutenable que son rôle, en tant qu'autorité de recours, est précisément de vérifier si la décision attaquée devant lui est ou non fondée et que le recours dont il était saisi était motivé conformément aux exigences de l'art. 35 LPJA par rapport aux points traités dans cette décision.
Dans ces circonstances, c'est arbitrairement que le Tribunal cantonal a refusé d'examiner les griefs du recourant concernant l'application des art. 50 al. 1 let. a LEtr et 8 § 1 CEDH et n'a pas établi les faits en relation avec ces dispositions. Cette approche aboutit aussi à un résultat arbitraire, dès lors que l'arrêt attaqué a pour effet de confirmer la non-prolongation de l'autorisation de séjour du recourant, sans que les éléments déterminants et les griefs de l'intéressé en lien avec ces deux dispositions n'aient été examinés. Il appartient partant aux juges cantonaux de se prononcer sur ces aspects.
3.5. A cela s'ajoute que, selon l'<ref-law>, l'autorité qui précède immédiatement le Tribunal fédéral doit pouvoir examiner au moins les griefs visés aux art. 95 à 98 LTF, soit notamment la violation de l'un des droits inclus à l'art. 95 let. a et b LTF, dont font partie les art. 50 al. 1 let. a LEtr et 8 CEDH invoqués par le recourant devant le Tribunal cantonal. La limitation du pouvoir d'examen que s'est imposée le Tribunal cantonal est donc également contraire à l'<ref-law>.
4.
Au vu de ce qui précède, le recours doit être admis et l'arrêt attaqué annulé, sans qu'il soit nécessaire d'examiner encore les autres griefs soulevés par le recourant, en particulier ceux ayant trait à l'art. 50 al. 1 let. b LEtr, disposition subsidiaire par rapport à l'art. 50 al. 1 let. a LEtr. La cause sera ainsi renvoyée au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
Le présent arrêt est rendu sans frais (<ref-law>). Le canton de Neuchâtel devra verser au mandataire du recourant une indemnité à titre de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours en matière de droit public est admis dans la mesure où il est recevable et l'arrêt attaqué est annulé.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
L'affaire est renvoyée au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
4.
Il n'est pas perçu de frais judiciaires.
5.
Le canton de Neuchâtel versera au mandataire du recourant une indemnité de 2'000 fr. à titre de dépens.
6.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations et au Département de l'économie du canton de Neuchâtel, au Tribunal cantonal de la République et canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 20 novembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat