Sachverhalt:
A.
A.a. Dem algerischen Staatsangehörigen A._ (geb. 1973) widerrief das Migrationsamt des Kantons Basel-Stadt am 4. Februar 2014 die gestützt auf die Ehe mit einer Schweizer Bürgerin erteilte Aufenthaltsbewilligung und wies ihn aus der Schweiz weg. Ein kantonales Rechtsmittel hiegegen blieb erfolglos. Zur Sicherstellung dieser Wegweisung wurde A._ am 23. September 2014 in Ausschaffungshaft genommen; auf die gegen den richterlichen Haftgenehmigungsentscheid erhobene Beschwerde trat das Bundesgericht am 14. Oktober 2014 nicht ein (Urteil 2C_939/2014). Am 23. Oktober 2014 wurde A._ nach Algerien ausgeschafft.
A.b. Am 26. November 2015 nahm die Kantonspolizei Basel-Stadt A._ in der Notschlafstelle Y._ fest; gleichentags wurde er durch die Staatsanwaltschaft und das Migrationsamt befragt. Ebenso ordnete das Migrationsamt eine Ausschaffungshaft für drei Monate (bis zum 26. Februar 2016) an, welche mit Urteil des basel-städtischen Einzelrichters für Zwangsmassnahmen im Ausländerrecht vom 27. November 2015 für rechtmässig befunden wurde.
A.c. Mit Verfügung vom 9. Februar 2016 ordnete das Migrationsamt gegenüber A._ eine Verlängerung der Ausschaffungshaft um drei Monate (bis zum 25. Mai 2016) an. Diese wurde vom zuständigen Einzelrichter anlässlich einer mündlichen Verhandlung im Gefängnis X._ überprüft und mit Urteil vom 25. Februar 2016 für rechtmässig befunden.
B.
Mit Eingabe vom 21. März 2016 beantragt A._ dem Bundesgericht, das letztgenannte Urteil aufzuheben und ihn umgehend aus der Haft zu entlassen.
Der Einzelrichter und das SEM äussern sich, ohne einen ausdrücklichen Antrag zu stellen. Der Beschwerdeführer hält an seinen Anträgen fest.

Erwägungen:
1.
Gegen letztinstanzliche kantonale richterliche Entscheide betreffend die Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, soweit der Betroffene am vorinstanzlichen Verfahren teilgenommen hat, durch den angefochtenen Entscheid besonders berührt ist und an der Beurteilung seiner Eingabe ein aktuelles praktisches Interesse hat (Art. 86 Abs. 1 und 2, <ref-law>). Der Beschwerdeführer befindet sich gestützt auf den hier angefochtenen Entscheid bis zum 25. Mai 2016 in Ausschaffungshaft. Er hat ein aktuelles Interesse, entlassen zu werden. Ein Ausschlussgrund ist nicht ersichtlich (<ref-law>). Auf die frist- und formgerecht eingereichte Beschwerde ist einzutreten.
2.
Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, kann die zuständige Behörde die betroffene Person zur Sicherstellung von dessen Vollzug unter anderem in Ausschaffungshaft nehmen bzw. in dieser belassen, wenn konkrete Anzeichen befürchten lassen, dass sie sich der Ausschaffung entziehen will (Art. 76 Abs. 1 lit. b Ziff. 3 AuG). Der Wegweisungsentscheid muss dabei nicht bereits rechtskräftig sein; es genügt, dass sein Vollzug (z.B. wegen fehlender Papiere) noch nicht möglich, jedoch absehbar erscheint. Der Vollzug der Weg- oder Ausweisung darf sich nicht aus rechtlichen oder tatsächlichen Gründen als undurchführbar erweisen (vgl. Art. 80 Abs. 6 lit. a AuG) und muss mit dem nötigen Nachdruck verfolgt werden (Art. 76 Abs. 4 AuG: "Beschleunigungsgebot"). Die ausländerrechtliche Festhaltung hat zudem als Ganzes verhältnismässig zu sein (<ref-ruling> E. 2.3.2 S. 97; Urteile 2C_765/2015 vom 18. September 2015 E. 5.3; 2C_334/2015 vom 19. Mai 2015 E. 2.2; 2C_218/2013 vom 26. März 2013 E. 5.1).
Die maximale Haftdauer von 6 Monaten (Art. 79 Abs. 1 AuG) kann mit Zustimmung der kantonalen richterlichen Behörde nach Art. 79 Abs. 2 AuG um höchstens zwölf Monate verlängert werden, wenn (lit. a) die betroffene Person nicht mit der zuständigen Behörde kooperiert bzw. (lit. b) sich die Übermittlung der für die Ausreise erforderlichen Unterlagen durch einen Staat, der kein Schengen-Staat ist, verzögert (Fassung gemäss Art. 2 Ziff. 1 des BB vom 18. Juni 2010 betreffend die Übernahme der EG-Rückführungsrichtlinie [Richtlinie 2008/115/EG], in Kraft seit 1. Januar 2011 [AS 2010 5925; BBl 2009 8881]).
3.
3.1. Die Vorinstanz hat unter Verweisung auf ihren Entscheid vom 27. November 2015 den Haftgrund der Untertauchensgefahr (Art. 76 Abs. 1 lit. b Ziff. 3 AuG) bejaht. Dessen Vorliegen wird vom Beschwerdeführer nicht substanziiert bestritten (<ref-law>), und darüber hinaus kann der Vorinstanz - angesichts des Umstandes, dass der Beschwerdeführer bereits ein erstes Mal ausgeschafft worden war und heimlich zurückkehrte -, nicht vorgeworfen werden wenn sie vom Risiko des Untertauchens ausgeht. Zudem hat die Vorinstanz - obwohl formell erst insgesamt sechs Monate ausländerrechtliche Haft zur Diskussion stehen (vgl. Art. 79 Abs. 1 AuG) - bereits im Hinblick auf eine absehbare weitere Verlängerung geprüft, ob die Voraussetzungen nach Art. 79 Abs. 2 AuG (vorne E. 2) erfüllt sind und dies wegen fehlender Kooperation bestätigt.
Der Beschwerdeführer bestreitet seine fehlende Kooperation mit den Behörden nicht, sondern bestätigt sie implizit, indem er ausführt, nicht nach Algerien zurückkehren zu wollen. Damit ist Art. 79 Abs. 2 AuGerfüllt (die Voraussetzungen von lit. a und lit. b sind alternativ zu verstehen, vgl. Art. 15 Abs. 6 der Richtlinie 2008/115/EG).
3.2. Der Beschwerdeführer macht geltend, die Haft sei unzulässig, weil sie bereits vor dem Wegweisungsentscheid (27. November 2015) angeordnet worden sei und im Zeitpunkt der Haftanordnung kein gültiger Wegweisungsentscheid vorgelegen habe; derjenige vom 4. Februar 2014, auf welchen sich das Migrationsamt gestützt habe, sei durch die Ausschaffung am 23. Oktober 2014 vollzogen und konsumiert worden.
Die Rüge ist unbegründet: Die Argumentation des Beschwerdeführers könnte höchstens dazu führen, dass die Haftdauer vor der Anordnung der Wegweisung (26./27. November 2015) als rechtswidrig beurteilt würde. Die Haftdauer bis zum 25. Februar 2016 wurde aber mit Entscheid vom 27. November 2015 rechtskräftig bestätigt (vorne lit. A.b); dieser Zeitraum steht hier nicht mehr zur Diskussion. Die jetzt streitige Verlängerung der Haft ist nach dem Wegweisungsentscheid angeordnet worden. Im Übrigen führt nicht jede Regelwidrigkeit im Verfahren zur Nichtigkeit der Haftanordnung oder zur Aufhebung der Haft, weil sonst die praktische Wirksamkeit der Vorschriften über die Rückführung beeinträchtigt würden. Richterlich zu prüfen ist in solchen Konstellationen, ob dadurch die Verteidigungsrechte des Betroffenen eingeschränkt werden (vgl. Urteil EuGH vom 10. September 2013 C-383/13 Rdnr. 38 - 45). Dies ist hier nicht der Fall.
3.3. Der Beschwerdeführer macht geltend, der Vollzug seiner Wegweisung sei undurchführbar im Sinne der Rechtsprechung.
Die Ausschaffungshaft soll den Vollzug der Entfernungsmassnahme sicherstellen und muss ernsthaft geeignet sein, diesen Zweck zu erreichen, was nicht (mehr) der Fall ist, wenn die Weg- oder Ausweisung trotz der behördlichen Bemühungen nicht in einem dem konkreten Fall angemessenen Zeitraum vollzogen werden kann. Die Festhaltung hat, weil unverhältnismässig, dann als unzulässig zu gelten, wenn triftige Gründe für solche Verzögerungen sprechen oder praktisch feststeht, dass sich der Vollzug kaum innert vernünftiger Frist wird realisieren lassen (<ref-ruling> E. 4.1.3 S. 61 mit Hinweisen, vgl. auch Urteil 2C_1072/2015 vom 21. Dezember 2015 E. 3.2).
Nach den für das Bundesgericht grundsätzlich verbindlichen Feststellungen der Vorinstanz (<ref-law>) sind die Reisekapazitäten für nach Algerien auszuschaffende Personen beschränkt. Einerseits führen nur zwei Fluggesellschaften begleitete Flüge von Genf nach Algerien durch und sind diese Flüge auf jeweils 2 Betroffene beschränkt (vgl. auch Vernehmlassung des SEM vom 5. April 2016). Der Beschwerdeführer wird nach vorreserviertem Termin im Juli 2016 ausgeschafft werden können, allenfalls wird ein früherer Termin noch realisierbar; der Termin liegt jedenfalls klarerweise innerhalb der maximal möglichen Haftdauer. Auch bestehen keine Anhaltspunkte, dass die nötigen Reisepapiere nicht innert vernünftiger Frist erhältlich gemacht werden könnten (vgl. zit. Vernehmlassung sowie - spezifisch für Algerien - zit. Urteil 2C_1072/2015 E. 3.3).
Im Übrigen ist zu berücksichtigen, wieweit der Betroffene es tatsächlich in der Hand hat, seine Festhaltung zu beenden, indem er seiner Mitwirkungs- bzw. Ausreisepflicht nachkommt (<ref-ruling> E. 2.3.2 S. 97, Urteil 2C_1/2016 vom 27. Januar 2016 E. 2.3 / E. 3.2.1). Der Beschwerdeführer wäre primär verpflichtet, selber nach Algerien auszureisen. Dass dies faktisch oder rechtlich unmöglich wäre, ist weder dargetan noch ersichtlich. Der Beschwerdeführer hat es in der Hand, seine Haft selber zu beenden, indem er sich bereit erklärt, seinen rechtlichen Verpflichtungen zur Ausreise nachzukommen.
3.4. Der Beschwerdeführer rügt zu Unrecht eine Verletzung des Beschleunigungsgebots (zum Massstab vgl. <ref-ruling> E. 2.1 S. 211) : Hier geht es um die Haft vom 26. Februar 2016 bis zum 25. Mai 2016. Gemäss den Angaben des Beschwerdeführers selber hat sich die Behörde jedenfalls ab dem 9. Februar um einen Rückflug gekümmert (Rz. 13 der Beschwerdeschrift). Er tut damit nicht dar, dass das Beschleunigungsgebot verletzt wäre.
3.5. Die vom Beschwerdeführer geltend gemachte Depression - und damit verbundene Suizidalität -, welche den Vollzug der Wegweisung unzumutbar mache, ist nach seinen eigenen Angaben (Rz. 16 der Beschwerdeschrift) gerade nicht reaktiv/taktisch aufgrund der bevorstehenden Ausschaffung motiviert, sondern hat ihre Ursache in der im Januar 2016 erfolgten Scheidung. Damit ist der Beschwerdeführer nicht in anderer Lage als alle anderen Personen, die in Algerien leben und wegen Scheidung in Depressionen geraten (zum dort kostenlos möglichen Zugang zur Psychiatrie vgl. angefochtener Entscheid S. 8); ein Grund für die Unzumutbarkeit des Vollzugs der Ausschaffung liegt darin nicht.
4.
Die Beschwerde ist abzuweisen.
Bei diesem Ausgang trägt der Beschwerdeführer die Kosten des Verfahrens (Art. 65/66 BGG). Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann zufolge Aussichtslosigkeit der Beschwerde nicht entsprochen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdefüherr auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht) und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 12. April 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Klopfenstein