一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据...
1.时间复杂度:常数的计算次数(读取，交换都算一次)按照最坏情况算
随机数据
private static List<int> anyMath()
{
List<int> maths = new List<int>();
Random ran = new Random();
for (int i=0; i<10; i++)
{
//Random在循环中的随机数相同,所以需要在循环外创建
maths.Add(ran.Next(0,10));
}
return maths;
}
主函数：
static void Main(string[] args)
{
List<int> list = anyMath();
foreach (int i in list)
{
Console.Write(i+" ");
}
Console.WriteLine("源数据");
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("函数数据");
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;
}
异或，不进位相加，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公式算递归时间复杂度，递归的子问题规模相同，其中例子a=2,b=2,d=0
归并排序，将数组分成两份，使两份数据分别有序，然后使用"双指针"比较两份数据的首数字大小，比较大小后将其拷贝如原数组，相比选择，冒泡排序等，没有浪费比较的结果，选择等的比较每次都只能比较出一个位置的数字，归并排序始终有序。部分也有序，不会浪费。
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();
}
}
快速排序:随机选择数组中的一个数字，然后将其与数组最后一位交换顺序，然后遍历数组，如果当前比较数字较小，那么数字不动，左边区域大小加一。如果数字较大，和末尾被比较数字换位置，末尾的范围加一(指针向前指一位)。相等则不管。
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));//伪随机，为其参数添加一个较可靠的因子
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]);
//若数据为0，2，0，3，并不会运行到Length<=2处，内部无序，递归---fail
//1.判断返回长度---影响前几次数据
//2.判断数据的最后一位是否最大
//不设除0 1 2数字的出口。----fail
//quikelySort(list.Take(L + 1).ToArray())；
int[] list2 = quikelySort(list.Take(L + 1).ToArray());//1 1 1 无法从递归中出来
//同理 1 1 1 1 1
//每次递归数据都会增加，判断数据是否有序，若有序则加入
//若数据无效，则跳过此段循环
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();
}
插入排序：每次数字与其前面所有数据比较，小于则换位置，知道前面没有更大数字
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.堆排序，大根堆--父永远比子大，左子树的序号减一除二几位父节点的序号，右子树则 减二除二,heapInsert，
private static int[] heapSort(int[] list)
{
//无需定义树结构！数据的下表代表其在树中的位置。
//设左子树的位置为n，左子树的父节点为(n-1)/2
//设右子树的位置为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.桶排序，找到所有数字中最大数字的位数，如：10为两位数，将其他诸如1，2的数字补齐两位-01，02等，准备最多10个桶，所有数字一共进桶，出桶两次，首先根据所有数字的个位进桶---依次进入下标为0-9的桶中，按照桶的顺序出通，然后根据十位进桶，出桶，排序就完成了。
5.计数排序
6.基数排序
/*
*/
