Faits :
A.
A._ a travaillé en qualité de serveur au restaurant B._, à U._, depuis le 1 er septembre 2011. À ce titre, il était assuré obligatoirement contre le risque d'accident auprès de Bâloise Assurances SA (ci-après: la Bâloise). Le 25 octobre 2011, il a glissé et est tombé sur le sol pendant son service. La chute a provoqué une contusion à l'épaule et l'hémithorax droits, nécessitant un traitement sous la forme de séances de physiothérapie. La Bâloise a pris en charge le cas. A partir du 13 février 2012, l'assuré a subi une incapacité totale de travail. Une IRM du 27 mars 2012 a mis en évidence notamment une déchirure sans évidence d'un aspect transfixiant du tendon du sus-épineux.
Par décision du 23 mai 2012, la Bâloise a mis un terme à son obligation de prester avec effet au 31 décembre 2011, date à laquelle elle a fixé le statu quo sine. Saisie d'une opposition, elle a ordonné la mise en oeuvre d'une expertise médicale, laquelle a été confiée au docteur C._, spécialiste en chirurgie orthopédique. Dans son rapport d'expertise du 10 avril 2013, ce médecin a diagnostiqué un status après sévère contusion de l'épaule droite avec rupture du sus-épineux suturée en juillet 2012, "re-rupture" du sus-épineux et épaule partiellement gelée, et a conclu à une origine traumatique des lésions.
Par lettre du 21 mai 2013, la Bâloise a informé l'assuré qu'elle annulait sa décision du 23 mai 2012 et a confirmé la prise en charge des suites de l'accident. En 2014, elle a mandaté le docteur D._, spécialiste en chirurgie orthopédique, pour une nouvelle expertise. Ce médecin a rendu son rapport le 16 avril 2014, dans lequel il a fixé le statu quo sine au 6 décembre 2011, soit à la fin du premier traitement physiothérapeutique de l'épaule, et indiqué que les lésions mises en évidence ultérieurement n'étaient pas en relation de causalité vraisemblable avec l'accident.
Par décision du 23 mai 2014, confirmée sur opposition le 30 juillet suivant, la Bâloise a supprimé le droit de l'assuré aux prestations d'assurance avec effet au 7 décembre 2011.
B.
L'assuré a recouru contre la décision sur opposition du 30 juillet 2014 devant la Cour des assurances sociales du Tribunal cantonal du Valais. Il a produit un rapport du docteur C._ du 19 janvier 2015, dans lequel ce médecin prend position sur le rapport d'expertise du docteur D._.
Le Tribunal cantonal a rejeté le recours par jugement du 25 février 2016.
C.
A._ interjette un recours en matière de droit public. Il conclut, sous suite de frais et dépens, à l'annulation du jugement cantonal et de la décision sur opposition du 30 juillet 2014 ainsi qu'au maintien de son droit aux prestations LAA également après le 7 décembre 2011. Subsidiairement, il demande le renvoi de la cause à la juridiction cantonale pour nouvelle décision dans le sens des considérants.
L'intimée conclut au rejet du recours. La cour cantonale et l'Office fédéral de la santé publique n'ont pas déposé de détermination.
Par écriture du 23 juin 2016, le recourant s'est exprimé sur la réponse de l'intimée.

Considérant en droit :
1.
1.1. Le litige porte sur le droit du recourant à des prestations d'assurance au-delà du 6 décembre 2011 pour les suites de l'accident du 25 octobre 2011.
1.2. Le 1 er janvier 2017 est entrée en vigueur la modification du 25 septembre 2015 de la LAA. Dans la mesure où l'accident est survenu avant cette date, le droit du recourant aux prestations d'assurance est soumis à l'ancien droit (cf. dispositions transitoires relatives à la modification du 25 septembre 2015).
1.3. Lorsque, comme en l'espèce, le jugement entrepris porte sur des prestations en espèces et en nature de l'assurance-accidents, le Tribunal fédéral dispose d'un pouvoir d'examen étendu en ce qui concerne les faits communs aux deux types de prestations (cf. arrêt 8C_584/2009 du 2 juillet 2010 consid. 4, in SVR 2011 UV n° 1 p. 2 s.).
2.
2.1. Le recourant demande la production du dossier de l'assurance-invalidité, en faisant valoir que l'intimée en avait demandé la copie mais qu'elle ne l'a pas produite devant l'instance précédente. Par ailleurs, le recourant a joint un bordereau de pièces à l'appui de son recours.
2.2. Le Tribunal ne procède qu'exceptionnellement à l'administration de preuves nouvelles (cf. JEAN-MAURICE FRÉSARD, in Commentaire de la LTF, 2 e éd. 2014, n° 9 ad <ref-law>). En l'espèce, aucune circonstance exceptionnelle ne justifie des mesures probatoires. Il n'y a donc pas lieu de donner suite à la requête du recourant. On notera, au demeurant, que le dossier produit par l'intimée devant la juridiction cantonale contient de nombreuses pièces issues du dossier de l'office AI. Par ailleurs, dans la mesure où elles ne figureraient pas déjà au dossier, les documents produits par le recourant à l'appui de son recours ne peuvent pas être pris en considération par la Cour de céans dès lors que, sauf exception non réalisée en l'espèce, un moyen de preuve qui n'a pas été examiné dans la procédure devant l'autorité précédente n'est pas admissible dans la procédure devant le Tribunal fédéral (<ref-law>).
3.
3.1. Le recourant fait valoir que la lettre de l'intimée du 21 mai 2013, par laquelle elle a annulé sa décision du 23 mai 2012 et confirmé la prise en charge du cas, est une décision qui est entrée en force. Selon lui, l'intimée ne pouvait donc plus supprimer le droit aux prestations rétroactivement au 7 décembre 2011 par sa décision du 23 mai 2014.
3.2. En l'occurrence, l'assureur-accidents a la possibilité de mettre fin avec effet ex nunc et pro futuro à son obligation de prester, qu'il avait initialement reconnue en versant des indemnités journalières et en prenant en charge les frais de traitement, sans devoir se fonder sur un motif de révocation (reconsidération ou révision procédurale), c'est-à-dire liquider le cas en invoquant le fait qu'un événement assuré - selon une appréciation correcte de la situation - n'est jamais survenu (<ref-ruling>). En l'espèce, il ressort de la décision de l'intimée du 23 mai 2014, confirmée sur opposition, que celle-ci a renoncé à réclamer au recourant la restitution des prestations versées au-delà du 6 décembre 2011. Elle avait ainsi la possibilité de supprimer le droit aux prestations sans devoir invoquer un motif de révocation. Partant, le grief est mal fondé.
4.
4.1. Selon une jurisprudence constante, lorsque des expertises confiées à des médecins indépendants sont établies par des spécialistes reconnus, sur la base d'observations approfondies et d'investigations complètes, ainsi qu'en pleine connaissance du dossier et que les experts aboutissent à des résultats convaincants, le juge ne saurait les écarter aussi longtemps qu'aucun indice concret ne permet de douter de leur bien-fondé (<ref-ruling> consid. 4.4 p. 469 s.; <ref-ruling> consid. 1c p. 161). En présence d'avis médicaux contradictoires, le juge doit apprécier l'ensemble des preuves à disposition et indiquer les motifs pour lesquels il se fonde sur une appréciation plutôt que sur une autre. A cet égard, l'élément décisif pour apprécier la valeur probante d'une pièce médicale n'est en principe ni son origine, ni sa désignation sous la forme d'un rapport ou d'une expertise, mais bel et bien son contenu. Il importe, pour conférer pleine valeur probante à un rapport médical, que les points litigieux importants aient fait l'objet d'une étude circonstanciée, que le rapport se fonde sur des examens complets, qu'il prenne également en considération les plaintes exprimées par la personne examinée, qu'il ait été établi en pleine connaissance de l'anamnèse, que la description du contexte médical et l'appréciation de la situation médicale soient claires et enfin que les conclusions de l'expert soient dûment motivées (<ref-ruling> consid. 5.1 p. 232; <ref-ruling> consid. 3a p. 352).
4.2.
4.2.1. Dans son rapport d'expertise du 10 avril 2013, le docteur C._ a mis en évidence différents critères de reconnaissance étiologique "généralement admis et reconnus en cas de traumatisme", à savoir la nature du traumatisme, la qualité des muscles, la rétraction tendineuse, l'ascension de la tête humérale et l'existence de lésions dégénératives. Au vu de la description de la chute donnée par le recourant - celui-ci portait une pile d'assiettes du bras gauche lorsqu'il a glissé sur le sol mouillé et a violemment heurté un petit muret de son épaule droite - le docteur C._ a retenu la présence d'un accident à haute énergie. En revanche, il a expliqué ne pas pouvoir se prononcer sur les critères de la rétraction tendineuse et de l'ascension de la tête humérale, dans la mesure où la rupture partielle du tendon du sus-épineux n'intéressait que la face profonde du tendon, lequel était "en continuité". Il a retenu en outre l'absence d'atrophie musculaire et d'altération dégénérative de l'épaule. En conclusion, il y avait selon lui plus d'arguments pour admettre une origine traumatique des lésions que pour leur reconnaître une cause dégénérative.
4.2.2. Pour sa part, le docteur D._ a retenu que l'accident du 25 octobre 2011 ne constituait pas un traumatisme à haute énergie, dans la mesure où le recourant était tombé de sa hauteur. Le choc direct subi n'était selon lui pas une action vulnérante appropriée pour léser le tendon du sus-épineux. En outre, la chute n'avait pas dû être trop grave, puisque le recourant avait continué à travailler et qu'il ne s'était rendu chez le médecin que six jours plus tard. Lors de cette visite, son médecin traitant n'avait pas décrit d'atteinte importante ni jugé nécessaire d'effectuer des examens complémentaires (radiologies ou IRM). Le recourant avait suivi des séances de physiothérapie jusqu'au 6 décembre 2011 et exercé son activité de serveur qui sollicitait particulièrement les membres supérieurs. Ce n'est que deux mois plus tard, le 14 février 2012, que le recourant était retourné voir son médecin traitant, lequel a alors attesté une incapacité de travail depuis le jour précédent. L'IRM pratiquée le 27 mars 2012 avait mis en évidence des troubles dégénératifs débutants de l'articulation acromio-claviculaire, associés à une importante tendinopathie du sus-épineux. Elle n'avait pas montré de lésion transfixiante mais une zone de délamination de la face articulaire du tendon du sus-épineux, à savoir une atteinte très fréquente vers l'âge de 50 ans, dont la cause était l'utilisation des membres supérieurs et la mauvaise vascularisation locale. Le fait que le recourant était diabétique était un facteur aggravant puisque ce trouble était connu pour induire des atteintes de la microcirculation distale. Selon le docteur D._, on ne pouvait donc pas conclure que la tendinopathie était d'origine accidentelle. Pour finir, il a relevé que l'origine dégénérative des troubles de la coiffe des rotateurs était confirmée par le fait que malgré une première intervention chirurgicale (révision-suture d'une déchirure de la coiffe des rotateurs du 3 juillet 2012), une fissure était réapparue, ce qui démontrait la mauvaise qualité des tissus.
4.3. La cour cantonale s'est fondée sur l'appréciation du docteur D._ pour nier le droit du recourant à des prestations d'assurance à compter du 7 décembre 2011. Elle s'est écartée des conclusions du rapport d'expertise du docteur C._ en invoquant les motifs suivants: Le docteur C._ avait retenu de manière erronée que le recourant avait consulté son médecin de famille le lendemain de sa chute. En réalité, il ne l'avait rencontré que six jours plus tard, soit le 31 octobre 2011. Vu ce laps de temps et le fait que le recourant avait continué à travailler, les premiers juges ont considéré que les douleurs ressenties n'apparaissaient pas particulièrement importantes et mis en doute que la déchirure du tendon soit la conséquence de la chute. Par ailleurs, le docteur C._ n'avait pas tenu compte du diabète du recourant et avait qualifié la chute de traumatisme à haute énergie, ce qui n'était pas soutenable de l'avis de la cour cantonale. Quant au rapport d'expertise du docteur D._, il était plus complet et en accord avec les connaissances et l'expérience médicales relatives aux lésions tendineuses.
4.4. De son côté, le recourant conteste l'affirmation selon laquelle les douleurs ne devaient pas être importantes. Il fait valoir qu'il n'a pas travaillé entre son accident et la première consultation médicale du lundi 31 octobre 2011, contrairement à ce qu'ont retenu les premiers juges, et qu'une durée de six jours, week-end inclus, avant de consulter un médecin n'est pas excessive. En outre, s'il avait ensuite continué de travailler c'était seulement sous calmants et par peur d'être licencié, mais le 12 février 2012, ne pouvant plus supporter les douleurs, il avait été mis en arrêt de travail par son médecin traitant. Les douleurs n'avaient donc pas cessé et la situation ne s'était pas améliorée à l'issue du traitement préconisé par son médecin traitant. Le recourant soutient également que le docteur C._ a tenu compte du diabète dans son rapport d'expertise (en page 3) mais que selon ce médecin il n'influençait pas de manière déterminante la relation de causalité entre l'accident et les troubles de l'épaule (cf. rapport du docteur C._ du 19 janvier 2015). Se prévalant de la jurisprudence en matière de lésion corporelle assimilée, le recourant fait valoir que dans tous les cas, un état antérieur n'exclut pas l'existence d'une lésion corporelle assimilée à un accident, lorsque cet état est aggravé par l'accident. La présence de troubles dégénératifs, attestée par le docteur D._, ne serait pas non plus susceptible d'exclure l'existence d'une telle lésion. Enfin, la force ou l'énergie liée au choc ne sont pas déterminantes de l'avis du recourant. Au demeurant, le docteur D._ n'aurait pas tenu compte du fait qu'il portait 6 ou 7 assiettes lors de la chute et que le sol était mouillé.
4.5.
4.5.1. En l'occurrence, le recourant se réfère à un planning transmis par son ancien employeur à l'office AI pour faire valoir qu'il n'a pas travaillé entre l'accident du 25 octobre 2011 et la première consultation médicale du 31 octobre 2011. Ce faisant, il fait une mauvaise lecture du document. En effet, d'après la légende accompagnant le planning, les jours marqués d'une croix ne correspondent pas aux jours travaillés mais aux jours de repos, ce qui est confirmé par le total inscrit sous la colonne "Repos perçus". Il s'ensuit que d'après ce planning, le recourant semble bel et bien avoir travaillé du 26 au 30 octobre 2011. Dans tous les cas, le dossier ne contient aucun certificat d'incapacité de travail pour la période antérieure au 13 février 2012. On ne peut donc pas retenir que le recourant a été en incapacité de travail dans les suites immédiates de l'accident. On relèvera par ailleurs qu'il a été licencié avec effet immédiat le 12 février 2012 pour des motifs liés à son comportement et non à son état de santé (cf. questionnaire pour l'employeur et ses annexes). Dans ces conditions, on ne saurait donner crédit aux déclarations du recourant, selon lesquelles il n'a plus été en mesure de travailler à compter de cette date en raison de ses douleurs. Partant, il y a lieu de retenir, en accord avec les constatations du docteur D._ et des premiers juges, que les conséquences de la chute n'avaient plus d'incidence sur l'état de santé du recourant en tout cas entre la fin de son premier traitement, à savoir le 6 décembre 2011, et le 13 février 2012.
4.5.2. En ce qui concerne la question du diabète, le docteur C._ a relevé sous le titre "Antécédents médicaux personnels" que le recourant était traité depuis 7-8 ans pour ce trouble. Dans son rapport du 19 janvier 2015, il a mentionné qu'à son avis le diabète de type 2 dont souffre le recourant était une affection courante après la cinquantaine qui n'influençait pas de façon déterminante la relation de causalité entre l'accident et les troubles de l'épaule. Ce faisant, il ne met pas concrètement en doute l'appréciation du docteur D._ selon laquelle il s'agit d'une maladie métabolique connue pour entraîner des troubles de la micro-circulation aggravant les atteintes tendineuses. En tout état de cause, le docteur D._ ne fonde pas son appréciation étiologique des troubles sur la seule présence de ce diabète. Quant aux troubles dégénératifs, s'il est vrai qu'ils ne peuvent pas exclure en soi l'existence d'une lésion corporelle assimilée, ils constituaient autant d'indices plaidant dans le sens d'une origine maladive des troubles. En conclusion, les arguments du recourant ne sont pas susceptibles de remettre en cause l'avis du docteur D._, selon lequel on ne pouvait rattacher les troubles diagnostiqués en 2012, en particulier la lésion du sus-épineux, à l'accident du 25 octobre 2011. On doit enfin admettre avec les premiers juges que le rapport d'expertise de ce médecin est plus complet que celui du docteur C._ et qu'il se fonde sur des considérations pertinentes et une version des faits plus proche de la réalité. Le docteur C._ a d'ailleurs reconnu la cohérence des conclusions de ce médecin dans son rapport du 19 janvier 2015, bien qu'il ne se soit pas rallié explicitement à l'avis de celui-ci.
5.
Vu ce qui précède, le recours doit être rejeté et le jugement attaqué confirmé.
6.
Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>). Bien qu'elle obtienne gain de cause, la Bâloise n'a pas droit aux dépens qu'elle prétend (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, à la Cour des assurances sociale du Tribunal cantonal du Valais et à l'Office fédéral de la santé publique.
Lucerne, le 1er mars 2017
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Juge présidant : Frésard
La Greffière : Castella