Faits :
A.
A.a. A._, né en 1966, est entré dans le corps de la police cantonale valaisanne en 1989. Il a été nommé chef de la section "B._", avec le grade d'adjudant, à compter du 1 er février 2004, puis a été promu premier-lieutenant en 2010. A ce titre, A._ faisait partie de l'état-major de la police cantonale dont il était le porte-parole.
A.b. Le 20 octobre 2016, à la suite d'une interview accordée par A._ et de la parution d'articles de presse, le Commandant de la police cantonale a rendu une décision formelle, dans laquelle il attirait l'attention de l'intéressé sur son devoir de fidélité, de réserve et de loyauté envers son employeur et le mettait en garde "sur le respect des limites de sa liberté d'expression". Il lui a également rappelé que si des griefs devaient être soulevés à l'encontre des autorités, seule la voie de la hiérarchie devait être utilisée.
Par communiqué de presse du 21 décembre 2016, le C._ a annoncé sa création et la désignation de A._ comme candidat à l'élection du Conseil d'Etat du Valais du 5 mars 2017. En raison de cette candidature, le Conseil d'Etat alors en place a déchargé le prénommé de ses fonctions pour la période du 24 décembre 2016 au 5 ou au 17 mars 2017 (décision du 22 décembre 2016).
Dans le contexte de sa campagne, A._ a mis en ligne des messages vidéo sur son compte Facebook. Dans une lettre du 6 février 2017, le Commandant de la police cantonale lui a enjoint, derechef, de respecter son devoir de réserve, jugeant en particulier inadmissibles les déclarations laissant entendre que les Conseillers d'Etat feraient campagne sur leur temps de travail.
Lors d'une conférence de presse du 14 février 2017, A._ a annoncé le classement d'une procédure pénale dont il faisait l'objet en raison d'une dénonciation de la juge du Tribunal de Martigny et St-Maurice, pour abus d'autorité ou instigation à faux témoignage. Des articles de presse du D._ et du E._ se sont fait l'écho des propos tenus à cette occasion par A._ à l'égard de la juge de district et, de manière générale, de la justice. Le même jour, répondant à la sollicitation des médias, le Ministère public a communiqué que l'instruction pénale était toujours en cours. A._ a alors précisé ses propos et s'est encore déterminé sur cette affaire à plusieurs reprises (communiqué aux médias et messages vidéo des 14, 15 et 16 février 2017).
Enfin, dans une vidéo publiée le 26 février 2017, il a exprimé son point de vue sur le programme Via Sicura.
A._ n'a pas été élu au Conseil d'Etat.
A.c. Dans une lettre du 14 mars 2017, le Procureur général du Ministère public a fait savoir au Commandant de la police cantonale que les récentes prises de position publiques de A._ avait créé un profond malaise au sein des autorités judiciaires et de l'institution en particulier. Il demandait à ce que le Ministère public soit informé des dispositions qui seront prises pour garantir une communication objective et sereine de la police cantonale sur les affaires pénales et remerciait de l'attention qui sera portée à leurs craintes dans la collaboration future avec ce membre de l'état-major "dont les propos défiants avaient, pour le moins, ébranlé le rapport de confiance qui doit exister entre les procureurs et le responsable de la communication du premier maillon de la chaîne pénale". Une copie de la lettre était transmise par e-mail au Tribunal cantonal. A réception du courriel, la commission administrative du Tribunal cantonal s'est adressée à son tour au Commandant de la police cantonale en indiquant que les autorités judiciaires partageaient les mêmes préoccupations que le Ministère public. De manière générale, les récentes prises de position publiques de A._ avaient suscité une réaction d'indignation de la part des juges de première instance. La confiance de l'autorité judiciaire envers l'intéressé, dans son activité de porte-parole officiel de la police cantonale, avait été fortement ébranlée.
Le Commandant de la police cantonale s'est déterminé sur le contenu de ces deux écritures dans une lettre adressée le même jour au Conseiller d'Etat, chef du département de la formation et de la sécurité. Il concluait que A._ ne pouvait plus assurer la fonction de chef "B._", en raison de la rupture du rapport de confiance entre l'intéressé et les partenaires principaux de la police cantonale, ainsi que d'une incompatibilité entre la fonction d'officier d'état-major et une activité dirigeante au sein d'une formation politique.
A.d. Le 15 mars 2017, le Conseil d'Etat a informé A._ qu'il envisageait de résilier les rapports de service et lui a imparti un délai non prolongeable au 7 avril 2017 pour déposer d'éventuelles observations. Il le libérait en outre, avec effet immédiat, de son obligation de travailler. A._ s'est déterminé par lettre du 5 avril 2017, à la suite de quoi le Conseil d'Etat a résilié les rapports de service, motif pris de la violation des devoirs de réserve, de dignité et de fidélité, en retirant l'effet suspensif à un éventuel recours (décision du 12 avril 2017).
B.
A._ a recouru contre cette décision devant le Tribunal cantonal dont il demandait la récusation in corpore. Sur le fond, il concluait à l'annulation de la décision de résiliation des rapports de service, à sa réintégration dans sa fonction ou, subsidiairement, au versement d'une indemnité équivalent à une année de traitement.
Par décision du 31 mai 2017, confirmée sur recours par le Tribunal fédéral (arrêt 8C_476/2017 du 14 novembre 2017), la Cour de droit public du Tribunal cantonal a rejeté la demande de récusation.
Statuant le 5 septembre 2018, la Cour de droit public a rejeté le recours.
C.
A._ forme un recours en matière de droit public contre ce jugement dont il requiert l'annulation. Il conclut principalement à ce qu'il soit constaté que la résiliation des rapports de service est juridiquement non fondée et au renvoi de la cause au Conseil d'Etat pour examiner sa réintégration. Subsidiairement, il demande le paiement d'un montant équivalent à une année de traitement.
Le Conseil d'Etat conclut à l'irrecevabilité du recours, respectivement à son rejet. La juridiction cantonale a renoncé à se déterminer.
Le recourant a répliqué puis a déposé une écriture complémentaire (lettres des 14 janvier et 21 mars 2019).

Considérant en droit :
1.
Le jugement entrepris a été rendu dans une cause en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF. Dans la mesure où la contestation porte sur la résiliation des rapports de service, il s'agit d'une contestation de nature pécuniaire, de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. La valeur litigieuse atteint par ailleurs le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public en ce domaine (art. 51 al. 2 et 85 al. 1 let. a LTF).
2.
Aux termes de l'<ref-law>, aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente. Par conséquent, l'article de presse du 8 mars 2019, que le recourant a produit avec son écriture du 21 mars 2019, ne peut être pris en considération par le Tribunal fédéral.
3.
3.1. Par un premier grief d'ordre formel, le recourant se plaint de la violation de son droit d'être entendu (art. 29 al. 2 Cst.) en lien avec le refus de la juridiction cantonale de donner suite à ses offres de preuves tendant à l'audition des Conseillers d'Etat en place au moment du licenciement, du Commandant de la police cantonale, de F._ (un fonctionnaire également candidat à l'élection au Conseil d'Etat), du journaliste G._ et d'une dénommée "H._", laquelle aurait accompli des recherches sur les réseaux sociaux pour le compte de l'intimé.
3.2.
3.2.1. Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou, à tout le moins, de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 4.1 p. 72; <ref-ruling> consid. 3.1 p. 564 et les arrêts cités). L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 3.1.3 p. 435; <ref-ruling> consid. 3.3 p. 64).
3.2.2. Cela étant, la cour cantonale a considéré qu'il n'était pas nécessaire d'administrer les offres de preuves du recourant. Elle a indiqué en particulier qu'il n'importait pas à la solution du litige de savoir si F._ avait été empêché d'accéder à son lieu de travail et à ses bases de données et s'il avait mené campagne avec un véhicule de fonction sur son temps de service. En effet, la contestation ne portait pas sur la régularité de la campagne et de l'élection mais concernait le licenciement du recourant. De même, l'audition du Commandant de la police cantonale était requise au regard de faits non déterminants pour le litige. Il n'y avait pas non plus lieu d'investiguer sur l'utilisatrice de Facebook dénommée "H._" dès lors que la réalité des vidéos diffusées par le recourant et des commentaires qu'elles ont suscités ne prêtait pas à discussion. L'audition des Conseillers d'Etat était refusée puisque la juridiction cantonale pouvait d'emblée exclure qu'ils avaient violé les garanties de procédure dont se plaignait le recourant. Enfin l'audition du journaliste était requise en relation avec un grief tiré de la violation des règles en matière de récusation, lequel était largement tardif.
3.2.3. A l'appui de son grief, le recourant se contente d'énumérer les moyens de preuve dont il a requis la mise en oeuvre en mentionnant les diverses violations du droit que ces preuves auraient été à même de démontrer. Ce faisant - et comme le fait valoir l'intimé dans sa réponse - il ne prend pas position sur les explications susmentionnées des premiers juges. En l'absence d'une motivation topique (<ref-law>), il n'y a pas lieu d'examiner si l'appréciation anticipée des preuves à laquelle a procédé la cour cantonale se révèle arbitraire. Au demeurant, savoir si une offre de preuve ou un élément porté à la connaissance de l'autorité est pertinent, de sorte que l'autorité en n'y donnant pas suite, a violé le droit d'être entendu, se confond avec le grief d'arbitraire dans l'appréciation des preuves (cf. arrêt 8D_4/2017 du 26 avril 2018 consid. 4.2). Les éléments que le recourant entendait démontrer par le biais des auditions, seront donc examinés avec le fond du litige, pour autant que ses griefs dirigés contre l'établissement des faits et l'appréciation des preuves soient recevables au vu des exigences découlant du principe d'allégation (infra consid. 6).
4.
L'art. 58 de la loi du 19 novembre 2010 sur le personnel de l'Etat du Valais (LcPers; RS/VS 172.2) prévoit ceci sous le titre "Résiliation ordinaire par l'employeur d'un engagement de durée indéterminée":
1 Après le temps d'essai, l'autorité compétente peut résilier un engagement de durée indéterminée moyennant le respect d'un délai de trois mois pour la fin d'un mois, et l'existence d'un motif de résiliation.
2 Un tel motif existe notamment dans les cas suivants:
a) manquements répétés ou persistants dans les prestations et/ou dans le comportement;
b) aptitudes ou capacités insuffisantes à accomplir les tâches liées à la fonction;
c) disparition de l'une des conditions d'engagement fixées dans la loi ou dans la décision d'engagement.
[...]
5.
5.1. La cour cantonale a admis l'existence d'un motif de résiliation au sens de l'art. 58 al. 1 LcPers, en raison de la violation par le recourant de ses devoirs de loyauté, de fidélité et de réserve, sous plusieurs aspects et à réitérées reprises. Elle a souligné qu'en tant que policier, officier membre d'état-major, chef de la section "B._" et surtout porte-parole de la police cantonale, le recourant était soumis à des exigences accrues.
5.2.
5.2.1. S'agissant des manquements reprochés, les premiers juges ont d'abord relevé les propos et l'attitude du recourant envers le Ministère public, se référant aux vidéos des 15 et 16 février 2017. Ils en ont inféré que le recourant avait mis en cause l'intégrité du Ministère public en lui reprochant de lui réserver un traitement particulier. En outre, même s'il était en droit de s'exprimer sur les procédures pénales le concernant, le recourant ne s'était pas contenté d'une mise au point objective. En effet, de manière réfléchie et planifiée, en dehors d'un débat électoral et sans être interpellé à ce propos, il avait critiqué le prétendu zèle du Ministère public dans le traitement de son cas au regard de l'inaction de cette autorité de poursuite dans d'autres affaires, laissant entendre qu'il s'agissait d'une différence de traitement délibérée ("on me déroule le tapis rouge" alors qu'en parallèle [dans l'affaire I._] "on freine des deux pieds apparemment"). Ses déclarations jetaient le discrédit sur le Ministère public et la justice en général. En outre, l'invitation à réagir, lancée au public, s'apparentait à un appel public à la défiance envers la justice pénale. La violence des très nombreux commentaires qui s'en étaient suivis était prévisible et le recourant n'avait pas jugé utile de recadrer la discussion ni de tempérer les virulentes interventions que son message avait suscitées.
5.2.2. La juridiction précédente a ensuite tenu compte des déclarations faites lors de la conférence de presse. Elle a relevé en particulier que le recourant ne contestait pas avoir parlé d'attitude "répugnante" de la juge de district. Il prétendait n'avoir pas validé ces propos au terme de la conférence mais il n'avait demandé aucune rectification à la suite de la parution de l'article du D._. En outre, de l'avis des premiers juges, compte tenu de sa fonction et de sa notoriété, il n'était pas admissible de la part du recourant de prétendre que "la justice avait failli", alors qu'aucune décision n'avait encore été rendue, ni de se plaindre publiquement d'une "dénonciation abusive d'une juge qui est une ancienne élue" ou encore de clamer que "ce n'est pas pour cette justice-là que je suis devenu policier et c'est le Valais que je n'aime pas". Enfin, les affirmations telles que "Cela commence à m'agacer grave d'être pris à partie de manière gratuite tous les quatre ans en période électorale. J'ai droit à chaque fois à un traitement VIP de la part de la justice" mettaient en cause, sans raison objective apparente, l'intégrité de l'institution judiciaire et portaient atteinte à la confiance que le public devait pouvoir placer en l'Etat.
5.2.3. Enfin, la cour cantonale a jugé que les déclarations du recourant au sujet du programme Via Sicura étaient préjudiciables à l'exercice de sa charge, dans la mesure où il est l'un des principaux porte-paroles du corps de police chargé d'appliquer le programme. Selon elle, le recourant ne pourrait défendre avec sérieux et cohérence cette politique publique alors qu'il reprochait publiquement au programme de conduire certaines personnes au suicide. Son attitude revenait en outre à inciter les chauffards à prendre à la légère les règles très strictes du programme et à compliquer la tâche de ses collègues policiers chargés, sur le terrain, de les mettre en oeuvre.
6.
Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.1 p. 503) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Le Tribunal fédéral n'entre en matière sur les moyens fondés sur la violation de droits fondamentaux, dont l'interdiction de l'arbitraire, que s'ils ont été invoqués et motivés conformément au principe d'allégation (<ref-law>), à savoir expressément soulevés et exposés de manière claire et détaillée (<ref-ruling> consid. 2.4 p. 368 et les références). Par conséquent, le recourant doit exposer, de manière détaillée et pièces à l'appui, que les faits retenus l'ont été d'une manière absolument inadmissible, et non seulement discutable ou critiquable. Il ne saurait se borner à plaider à nouveau sa cause, contester les faits retenus ou rediscuter la manière dont ils ont été établis comme s'il s'adressait à une juridiction d'appel (<ref-ruling> consid. 3 p. 352). Le Tribunal fédéral n'entre ainsi pas en matière sur des critiques appellatoires portant sur l'appréciation des preuves ou l'établissement des faits par l'autorité précédente (<ref-ruling> consid. 1.3 p. 30).
D'autre part, sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c, d et e LTF), on ne peut invoquer la violation du droit cantonal ou communal en tant que tel devant le Tribunal fédéral (<ref-law> a contrario). Il est néanmoins possible de faire valoir que son application consacre une violation du droit fédéral, comme la protection contre l'arbitraire (art. 9 Cst.) ou la garantie d'autres droits constitutionnels.
7.
7.1. Se plaignant d'une constatation incomplète des faits et d'une mauvaise appréciation des preuves, le recourant émet de nombreuses critiques, formulées dans un ordre aléatoire, dont il déduit, dans un moyen subséquent, la violation de plusieurs droits constitutionnels (égalité de traitement [art. 8 Cst.], protection contre l'arbitraire et la protection de la bonne foi [art. 9 Cst.], proportionnalité [art. 5 Cst.], liberté d'opinion et d'expression [art. 16 Cst.], droit à un procès équitable [art. 29 Cst.] et droits politiques [art. 34 Cst.]).
Une lecture d'ensemble de l'écriture permet de regrouper les critiques sous les griefs suivants:
7.2.
7.2.1. Le recourant fait valoir que si l'autorité précédente avait retenu qu'il avait cofondé le C._, dont les thèmes politiques étaient notamment la réforme de la justice et Via Sicura, elle aurait vu sous un tout autre angle les propos tenus durant la campagne. Il conteste en particulier avoir utilisé les termes "attitude répugnante" en faisant valoir qu'il a toujours indiqué ne pas s'en souvenir. Il persiste en outre à prétendre faire l'objet d'un traitement particulier de la part du Ministère public et explique qu'il a qualifié la dénonciation d'abusive en raison du classement de la procédure pénale. Le recourant soutient que puisque les critiques qu'il a formulées étaient fondées (dénonciation abusive, traitement VIP), on ne pouvait les lui reprocher sous peine de violer sa liberté d'opinion. A propos de Via Sicura, le recourant conteste qu'il n'a pas eu l'aval du Commandant de la police cantonale pour critiquer le programme. De son avis, l'autoriser à participer à la campagne, pendant laquelle il allait défendre les valeurs connues du C._, tout en lui refusant le droit de s'exprimer, revient à lui refuser tout simplement le droit de mener campagne et à lui supprimer un aspect de ses droits politiques.
7.2.2. L'argumentation développée sur ces différents points est largement appellatoire et ne permet pas de démontrer que les faits établis par la juridiction précédente l'auraient été de manière arbitraire. En particulier, lorsqu'il nie avoir utilisé les termes "attitude répugnante", le recourant se contente de substituer sa version des faits à l'appréciation de la cour cantonale. En outre, il ne peut rien tirer en sa faveur du classement de la procédure pénale dans la mesure où, selon les constatations du jugement attaqué, l'instruction était encore en cours au moment des déclarations. Dans tous les cas, le classement de la procédure ne signifie pas encore que la dénonciation à son origine était abusive. Quant à la médiatisation de l'affaire - également invoquée - elle ne saurait justifier les propos tenus par le recourant, d'autant moins qu'il est un professionnel de la communication comme l'ont souligné les premiers juges. C'est également de manière tout à fait appellatoire que le recourant affirme que la juge de district a mentionné la dénonciation à la presse ou qu'il a eu le consentement de son supérieur pour mettre en cause le programme Via Sicura. Contrairement à ce que le recourant soutient à ce dernier propos, il ne s'agit pas d'un fait négatif. On ne voit pas non plus que seule l'audition du Commandant de la police cantonale aurait permis d'établir cet élément de fait. Le Tribunal fédéral s'en tiendra donc aux constatations de l'instance précédente (<ref-law>).
Cela étant, si l'on doit admettre que des critiques à l'égard de l'ordre établi et des autorités publiques ont leur place dans le contexte d'une campagne électorale, cela ne signifie pas pour autant qu'elles soient compatibles avec le devoir de réserve et de fidélité des agents publics. Ces devoirs peuvent, sous certaines conditions, imposer des limites à l'exercice de la liberté de parole ou d'opinion (cf. <ref-ruling> consid. 3.2 p. 335 ss; ANDREAS KLEY/ESTHER TOPHINKE, in Die schweizerische Bundesverfassung, St. Galler Kommentar, 3 e éd. 2014, n° 21 s. ad art. 16 Cst.). Des restrictions se justifient en particulier à l'égard des membres des corps de police, parce qu'ils incarnent l'autorité de l'Etat (cf. arrêts 8C_252/2018 du 29 janvier 2019 consid. 5.4.3; 8C_194/2018 du 5 juillet 2018 consid. 7.3; 8C_146/2014 du 26 juin 2014 consid. 5.5; 2P.273/2000 du 11 avril 2001 consid. 3b/bb; voir aussi PASCAL MAHON/FANNY MATTHEY, La liberté d'expression et la liberté syndicale des fonctionnaires, notamment de police, en particulier sous l'angle du droit à la critique, in Droit public de l'organisation - responsabilité des collectivités publiques - fonction publique, annuaire 2008, p. 205 ss, plus spécialement p. 217 et 226). Le recourant ne démontre pas, en l'espèce, que les conditions de restrictions des droits constitutionnels qu'il invoque ne seraient pas remplies. Dans tous les cas, les premiers juges n'ont pas versé dans l'arbitraire en considérant qu'en sa qualité de porte-parole de la police cantonale, le recourant avait violé ses devoirs de service en tenant publiquement des propos irrespectueux à l'encontre d'une juge de district et surtout en mettant en cause l'intégrité du Ministère public, avec lequel la police entretient des liens étroits et doit collaborer.
7.3.
7.3.1. Le recourant reproche aux premiers juges de n'avoir pas, ou pas suffisamment, tenu compte de ses excellents états de service, de la durée des relations de travail et de la possibilité de "solutions de rocades" au sein de la police cantonale. Ces éléments auraient dû les amener à admettre la violation du principe de la proportionnalité et à considérer le licenciement comme étant arbitraire.
7.3.2. En l'occurrence, les juges cantonaux ont exposé qu'en cas de procédure de résiliation des rapports de service au sens de l'art. 58 LcPers, la législation ne conférait aucun droit à être déplacé dans un autre poste à la place du renvoi. Le recourant ne dit rien à ce sujet mais se contente d'affirmer, de manière péremptoire, qu'il existait des possibilités de reclassement. Cela ne suffit pas pour démontrer que la décision de résilier les rapports de service était disproportionnée ou arbitraire. Dans la mesure où, en dépit des mises en garde de son supérieur, le recourant a persisté dans son attitude réprobatrice, notamment en multipliant les déclarations de nature à discréditer le Ministère public, il a clairement manifesté sa volonté de ne pas se plier aux injonctions. Malgré ses années de service et la qualité du travail fourni jusque-là, un tel comportement ne pouvait que ruiner définitivement le lien de confiance avec l'employeur et ne laissait pas la place à une mesure moins incisive.
7.4.
7.4.1. Se plaignant d'inégalités de traitement, le recourant fait valoir que d'autres fonctionnaires, candidats à une élection ou à la tête d'une formation politique, ont tenu des propos vifs à l'encontre de leur supérieur hiérarchique sans qu'ils ne soient inquiétés. En outre, le Conseiller d'Etat, chef du département, des associations de fonctionnaires de police et des procureurs auraient également critiqué le programme Via Sicura. En relation avec les inégalités de traitement alléguées, le recourant reproche aux premiers juges de n'avoir pas examiné certains arguments en raison de leur caractère appellatoire, le privant ainsi d'une instance judiciaire revoyant les faits librement.
7.4.2. L'argumentation est mal fondée. Premièrement, il n'apparaît pas que les employés concernés exerçaient des activités comparables à celle du recourant. Or, c'est précisément au regard de sa fonction de porte-parole de la police cantonale que les déclarations du recourant ont été jugées inadmissibles. Ensuite, en ce qui concerne le Conseiller d'Etat, chef du département, quel que fussent ses prises de position, elles ne pouvaient conduire à son licenciement dans la mesure où (contrairement au recourant) il a été élu au Conseil d'Etat. Son statut lui conférait en outre une liberté de parole qui va au-delà de celle reconnue aux employés publics. Quant au Commandant de la police cantonale, le recourant n'explique pas quels sont les propos qu'il aurait tenus en violation de son devoir de réserve. Pour finir, les premiers juges ont répondu de manière circonstanciée au reproche d'inégalité de traitement en tant qu'il visait un ancien chef du service de l'enseignement (cf. consid. 8.3.1 du jugement attaqué). En ce qui concerne les autres fonctionnaires et présidents de partis politiques valaisans, ils ont relevé que le recourant se contentait d'affirmations toutes générales et n'entreprenait pas de montrer en quoi les situations qu'ils dénonçaient pourraient être valablement comparées à la sienne. Pareilles critiques, articulées sur un mode appellatoire, ne répondaient pas aux exigences des art. 48 al. 2 et 80 al. 1 let. c de la loi cantonale du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA; RS/VS 172.6). Aussi les premiers juges ont-ils rejeté les griefs sans plus ample examen. Ces considérations se fondent sur du droit cantonal dont le recourant ne dénonce pas l'application arbitraire ou contraire à un autre droit constitutionnel. Il ne soutient pas non plus qu'il aurait dûment allégué, devant la juridiction précédente, les faits permettant d'apprécier la similitude des situations invoquées.
7.5.
7.5.1. Sous l'angle du droit à un traitement équitable et du droit d'être entendu, le recourant fait notamment valoir qu'il n'a pas été autorisé à reprendre sa place de travail au lendemain du premier tour. Il reproche en outre à l'intimé d'avoir agi trop rapidement en prononçant le licenciement le 12 avril 2017, soit deux jours seulement après avoir reçu sa détermination. Se référant aux lettres du 14 mars 2017, le recourant se plaint de la rapide coordination du Ministère public, du Tribunal cantonal et du Commandant de la police cantonale, dans le but de le licencier avant la nouvelle composition du Conseil d'Etat. Il reproche enfin à l'intimé d'avoir laissé entendre qu'un accord amiable pouvait être trouvé pendant le délai qui lui avait été imparti pour faire valoir ses observations.
7.5.2. En l'occurrence, on peine à saisir la portée d'une telle argumentation. En effet, dans la mesure où le recourant a disposé de suffisamment de temps pour s'expliquer avant que la décision ne soit prise à son détriment (cf. arrêt 8C_541/2017 du 14 mai 2018 consid. 2.2 et les références), on ne saurait reprocher à l'intimé d'avoir prononcé le licenciement deux jours après avoir reçu la détermination en question. Au demeurant, l'intimé fait valoir qu'il a reçu celle-ci le 7 avril et non pas le 10 avril 2017 comme le prétend le recourant. On ne peut pas non plus reprocher à l'intimé d'avoir attendu les résultats de l'élection avant de rendre sa décision puisque la question du renvoi ne se serait pas posée en cas d'élection. Enfin, le recourant ne prétend pas qu'il était au bénéfice d'un acte ou d'une promesse lui garantissant d'être maintenu à son poste. Pour le reste, le recourant se limite à exposer son point de vue - les nouveaux Conseillers d'Etat n'auraient peut-être pas rendu la même décision; des contacts auraient été pris entre les divers pouvoirs en vue de l'exclure - d'une manière qui ne satisfait pas aux exigences de motivation qualifiées prévues à l'<ref-law> (supra consid. 6).
8.
Il s'ensuit que le recours est en tous points mal fondé et doit être rejeté.
Succombant, le recourant supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et à la Cour de droit public du Tribunal cantonal du canton du Valais.
Lucerne, le 11 juillet 2019
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
La Greffière : Castella