一周刷爆LeetCode，算法大神左神（左程云）耗時(shí)100天打造算法與數(shù)據(jù)...
1.時(shí)間復(fù)雜度:常數(shù)的計(jì)算次數(shù)(讀取，交換都算一次)按照最壞情況算
隨機(jī)數(shù)據(jù)
????private static List<int> anyMath()
????{
??????List<int> maths = new List<int>();
??????Random ran = new Random();
??????for (int i=0; i<10; i++)
??????{
????????//Random在循環(huán)中的隨機(jī)數(shù)相同,所以需要在循環(huán)外創(chuàng)建
????????maths.Add(ran.Next(0,10));
??????}
??????return maths;
????}
主函數(shù)：
????static void Main(string[] args)
????{
??????List<int> list = anyMath();
??????foreach (int i in list)
??????{
????????Console.Write(i+" ");
??????}
??????Console.WriteLine("源數(shù)據(jù)");
??????int[] list2 = list.ToArray();
??????int[] list3 = list.ToArray();
??????int[] list4 = list.ToArray();
??????int[] list5 = list.ToArray();
??????int[] list6 = list.ToArray();
??????int[] list7 = list.ToArray();
?????????int[] list8 = list.ToArray();
??????Array.Sort(list2);
??????foreach (int i in list2)
??????{
????????Console.Write(i + " ");
??????}
??????Console.WriteLine("函數(shù)數(shù)據(jù)");
??????selectSort(list3);//
??????maoPaoSort(list4);//
??????guiBinSort(list5);//
??????insertSort(list6);
??????quikeSort(list7);//
??????heapSort(list8);
??????Console.ReadLine();
????}
選擇排序:最小歸左
????private static int[] selectSort(int[] list)
????{
??????int min = list[0];
??????for(int i=0;i<list.Length-1;i++)
??????{
????????for(int j=i+1; j<list.Length; j++)
????????{
??????????if (list[i] > list[j])
????????????swap(ref list[i],ref list[j]);
??????????else continue;
????????}
??????}
??????foreach (int i in list)
??????{
????????Console.Write(i + " ");
???????????}
??????Console.WriteLine("選擇排序");
??????return list;
????}
冒泡排序:最大歸右
????private static int[] maoPaoSort(int[] list)
????{
??????for(int i=0;i<list.Length;i++)
??????{
????????for(int j=0;j<list.Length-i-1;j++)
????????{
??????????if (list[j] > list[j + 1])
??????????{
????????????swap(ref list[j], ref list[j+1]);
??????????}
??????????else continue;
????????}
??????}
??????foreach (int i in list)
??????{
????????Console.Write(i+ " ");
??????}
??????Console.WriteLine("冒泡排序");
??????return list;
????}
異或，不進(jìn)位相加，a,b的地址不可相同
????private static void swap(ref int a,ref int b)
????{
??????//a,b同地址崩潰
??????a ^= b;b ^= a;a ^= b;
????}
????private static void change(ref int a,ref int b)
????{
??????int temp=a;
??????a = b;b = temp;
????}
2.
master公式算遞歸時(shí)間復(fù)雜度，遞歸的子問題規(guī)模相同，其中例子a=2,b=2,d=0
歸并排序，將數(shù)組分成兩份，使兩份數(shù)據(jù)分別有序，然后使用"雙指針"比較兩份數(shù)據(jù)的首數(shù)字大小，比較大小后將其拷貝如原數(shù)組，相比選擇，冒泡排序等，沒有浪費(fèi)比較的結(jié)果，選擇等的比較每次都只能比較出一個(gè)位置的數(shù)字，歸并排序始終有序。部分也有序，不會(huì)浪費(fèi)。
????private static int[] guiBinSort(int[] list)
????{
??????list=masterSort(list);
??????foreach (int i in list)
??????{
????????Console.Write(i + " ");
??????}
??????Console.WriteLine("歸并排序");
??????return list;
????}
????private static int[] masterSort(int[] list)
????{
??????List<int> list4 = new List<int>();
??????if (list.Length== 1)
??????{
????????return list;
??????}
??????else
??????{
????????int[] list2 = masterSort(list.Take(list.Length / 2).ToArray());
????????int[] list3 = masterSort(list.Skip(list.Length / 2).ToArray());
????????for(int i=0,j=0;i<list2.Length||j<list3.Length;)
????????{
??????????????????if(i==list2.Length)
??????????{
????????????list4.Add(list3[j++]);
????????????continue;
??????????}
??????????else if(j==list3.Length)
??????????{
????????????list4.Add(list2[i++]);
????????????continue;
??????????}
??????????if (list2[i] <= list3[j])
????????????list4.Add(list2[i++]);
??????????else list4.Add(list3[j++]);
??????????????}
????????return list4.ToArray();
??????}
????}
快速排序:隨機(jī)選擇數(shù)組中的一個(gè)數(shù)字，然后將其與數(shù)組最后一位交換順序，然后遍歷數(shù)組，如果當(dāng)前比較數(shù)字較小，那么數(shù)字不動(dòng)，左邊區(qū)域大小加一。如果數(shù)字較大，和末尾被比較數(shù)字換位置，末尾的范圍加一(指針向前指一位)。相等則不管。
????private static int[] quikeSort(int[] list)
????{
??????list1.Clear();
??????list = quikelySort(list);
??????foreach (int i in list)
??????{
????????Console.Write(i + " ");
??????}
??????Console.WriteLine("快速排序");
??????return list;
????}
????private static int[] quikelySort(int[] list)
????{
??????if (list.Length == 0 || list.Length == 1)
??????{
????????canAdd = true;
????????return list;
??????}
??????else if(list.Length == 2)
??????{
????????if (list[0] > list[1])
??????????change(ref list[0], ref list[1]);
????????canAdd = true;
????????return list;
??????}
??????foreach(var li in list.GroupBy(x=>x))
??????{
????????if (li.Count() == list.Length)
????????{
??????????canAdd = true;
??????????return list;
????????}
??????}
??????byte[] buffer = Guid.NewGuid().ToByteArray();
??????Random random = new Random(BitConverter.ToInt32(buffer,0));//偽隨機(jī)，為其參數(shù)添加一個(gè)較可靠的因子
??????change(ref list[list.Length - 1], ref list[random.Next(0, list.Length)]);
??????for(int i=0,L=0,R=0;i<list.Length;)//R=list.Length-1-i
??????{
????????if(L+R==list.Length-1)
????????{
??????????canAdd = false;
??????????change(ref list[list.Length-1],ref list[L]);
??????????//若數(shù)據(jù)為0，2，0，3，并不會(huì)運(yùn)行到Length<=2處，內(nèi)部無序，遞歸---fail
??????????//1.判斷返回長度---影響前幾次數(shù)據(jù)
??????????//2.判斷數(shù)據(jù)的最后一位是否最大
??????????//不設(shè)除0 1 2數(shù)字的出口。----fail
??????????//quikelySort(list.Take(L + 1).ToArray())；
??????????int[] list2 = quikelySort(list.Take(L + 1).ToArray());//1 1 1 無法從遞歸中出來
??????????//同理 1 1 1 1 1
??????????//每次遞歸數(shù)據(jù)都會(huì)增加，判斷數(shù)據(jù)是否有序，若有序則加入
??????????//若數(shù)據(jù)無效，則跳過此段循環(huán)
??????????if(canAdd)
??????????{
????????????for (int j = 0; j < list2.Length; j++)
??????????????list1.Add(list2[j]);
????????????canAdd = false;
??????????}
??????????int[] list3 = quikelySort(list.Skip(L + 1).ToArray());
??????????if(canAdd)
??????????{
????????????for (int j = 0; j < list3.Length; j++)
??????????????list1.Add(list3[j]);
????????????canAdd = false;
??????????}
??????????return list1.ToArray();
????????}
????????if (list[i] > list[list.Length - 1])
????????{
??????????R++;
??????????change(ref list[i], ref list[list.Length-1-R]);
????????}
????????else
????????{
??????????i++;L++;
????????}
??????}
??????return list1.ToArray();
????}
插入排序：每次數(shù)字與其前面所有數(shù)據(jù)比較，小于則換位置，知道前面沒有更大數(shù)字
????private static int[] insertSort(int[] list)
????{
??????list=InsertSort(list);
??????foreach (int i in list)
??????{
????????Console.Write(i + " ");
??????}
??????Console.WriteLine("插入排序");
??????return list;
????}
????private static int[] InsertSort(int [] list)
????{
??????for(int i=0;i<list.Length;i++)
??????{
????????int k = i-1;
????????for(int j=i;k>=0&&j<list.Length;k--,j--)
????????{
??????????int temp = list[j];
??????????if (list[k] > list[j])
??????????{
????????????list[j] = list[k];list[k] = temp;
??????????}
??????????continue;
????????}
??????}
?????????????return list;
????}
3.堆排序，大根堆--父永遠(yuǎn)比子大，左子樹的序號(hào)減一除二幾位父節(jié)點(diǎn)的序號(hào)，右子樹則 減二除二,heapInsert，
????private static int[] heapSort(int[] list)
????{
??????//無需定義樹結(jié)構(gòu)！數(shù)據(jù)的下表代表其在樹中的位置。
??????//設(shè)左子樹的位置為n，左子樹的父節(jié)點(diǎn)為(n-1)/2
??????//設(shè)右子樹的位置為n，右子樹的父節(jié)點(diǎn)為(n-2)/2
??????list = heapInsert(list, list.Length);
??????foreach (int i in list)
??????{
????????Console.Write(i + " ");
??????}
??????Console.WriteLine("堆排序");
??????return list;
????}
????public class Tree
????{
??????public int val;
??????public Tree leftChild;
??????public Tree rightChild;
??????public Tree(int val = 0, Tree leftChild = null, Tree rightChild = null)
??????{
????????this.val = val;
????????this.leftChild = leftChild;
????????this.rightChild = rightChild;
??????}
????}
????private static int[] heapInsert(int[] list, int Length)
????{
??????if (Length == -1||Length==0)
????????return list;
??????for (int i = Length - 1; i > 0; i -= 2)
??????{
????????//右子樹
????????if (i % 2 == 0)
????????{
??????????int temp = list[(i - 2) / 2] > (list[i - 1] > list[i] ? list[i - 1] : list[i]) ? list[(i - 2) / 2] : list[i - 1] > list[i] ? list[i - 1] : list[i];
??????????if (temp == list[(i - 2) / 2])
????????????continue;
??????????else if (temp == list[i])
????????????swap(ref list[i], ref list[(i - 2) / 2]);
??????????else
????????????swap(ref list[i - 1], ref list[(i - 2) / 2]);
????????}
????????//左子樹
????????else
????????{
??????????if (i == Length - 1)
??????????{
????????????if (list[i] > list[(i - 1) / 2])
??????????????swap(ref list[i], ref list[(i - 1) / 2]);
??????????}
??????????else
??????????{
????????????int temp = list[(i - 1) / 2] > (list[i + 1] > list[i] ? list[i + 1] : list[i]) ? list[(i - 1) / 2] : list[i + 1] > list[i] ? list[i + 1] : list[i];
????????????if (temp == list[(i - 1) / 2])
??????????????continue;
????????????else if (temp == list[i])
??????????????swap(ref list[i], ref list[(i - 1) / 2]);
????????????else
??????????????swap(ref list[i + 1], ref list[(i - 1) / 2]);
??????????}
????????}
??????}
??????change(ref list[0], ref list[Length - 1]);
??????heapInsert(list, Length-1);
??????return list;
????}
4.桶排序，找到所有數(shù)字中最大數(shù)字的位數(shù)，如：10為兩位數(shù)，將其他諸如1，2的數(shù)字補(bǔ)齊兩位-01，02等，準(zhǔn)備最多10個(gè)桶，所有數(shù)字一共進(jìn)桶，出桶兩次，首先根據(jù)所有數(shù)字的個(gè)位進(jìn)桶---依次進(jìn)入下標(biāo)為0-9的桶中，按照桶的順序出通，然后根據(jù)十位進(jìn)桶，出桶，排序就完成了。
5.計(jì)數(shù)排序
6.基數(shù)排序
/*
*/
