一. 冒泡排序(重点)
思路:每次比较把较小的放在前面, 大的放到后面;
图解:下图是最坏情况下的排序
冒泡排序m个元素, 就有(m-1)趟排序, 第一趟m-1次, 第二趟 m-2次.... 总结下来就是趟数加上次数就等于总的元素数;
核心算法:int[] intNums = new int[] { 5, 4, 3, 2, 1 };
int temp;
// 第一层循环 控制趟数 n - 1 趟
for (int i = 0; i < intNums.Length - 1 ; i++)
{
// 第二层循环 控制次数 n - i, 因为下标是从 0 开始的, 所有还要再减1 , 要不然会溢出
for (int j = 0; j < intNums.Length - 1 - i; j++)
{
// 判断 元素大小 进行交换
if (intNums[j] > intNums[j + 1])
{
temp = intNums[j];
intNums[j] = intNums[j + 1];
intNums[j + 1] = temp;
}
}
}
foreach (int item in intNums)
{
Console.WriteLine(item);
}
上述写的代码有个很大的问题, 总体效率太低. 只有当数组初始排序是最坏情况的时候, 才需要走完所有的趟数和次数(两层循环). 但如果初始排序时已经有一部分是有序的, 例如 {5, 1, 2, 3, 4}这样的一个顺序, 当执行完一趟的时候 其实已经得到了最终的结果, 没有必要再进行一趟趟的循环.
当数据量小的时候影响还不是很大, 但是如果数量上升到一定等级这个时间消耗就很可怕了. 因此我们有必要对它进行一些优化; 如果已经排好顺序就可以提前终止循环, 那么如何判断?
显而易见, 当一趟中没有发生任何交换, 即内层for循环里的if如果没有被激活, 就代表顺序已经排好了. 那么我们就可以用一个标签来进行记录.
int[] intNums = new int[] { 5, 4, 3, 2, 1 };
int temp;
bool tag = true; //定义一个tag标签 用来进行判断
// 在循环条件中加一个逻辑与运算符, 如果tag为true那么就继续进行循环, 如果为false就终止循环, 不用使用break来终止了;
for (int i = 0; i < intNums.Length - 1 && tag; i++)
{
tag = false; // 这里是必不可少的, 少了tag 就会一直为真, 无法起到终止循环的目的.
for (int j = 0; j < intNums.Length - 1 - i; j++)
{
if (intNums[j] > intNums[j + 1])
{
// 如果激活了 if 语句, 就让 tag 为真, 表示循环还需要继续执行
tag = true;
temp = intNums[j];
intNums[j] = intNums[j + 1];
intNums[j + 1] = temp;
}
}
}
foreach (int item in intNums)
{
Console.WriteLine(item);
}
二.选择排序
思路:以数组 array = {5, 4, 3, 2, 1}为例:
第一趟用第一个元素和剩下的元素比较大小, 找到最小的元素, 然后把它的下标和值记录下来, 这一趟结束后将其和第一个元素进行交换;
第二趟用第二元素和它之后的元素进行比较, 找到最小值, 最后再进行交换, 以此类推.
总的来说就是, 每趟找到数组中最小的数,将它们依次放到前面来.
图解:
int[] array = new int[] { 5, 4, 3, 2, 1 };
for (int i = 0; i < array.Length - 1; i++)
{
int min = array[i]; // min用来存放最小值
int index = i; // index就用来存放最小值的下标
for (int j = i + 1; j <= array.Length - 1; j++)
{
if (min > array[j])
{
min = array[j];
index = j;
}
}
array[index] = array[i];
array[i] = min;
}
foreach (int item in array)
{
Console.Write(item + " ");
}
三.二分查找
查找元素在开发中经常会使用到, 没有任何技巧的查找方法就是一个个遍历, 对比我们的期望元素. 这种查找方法有一个非常致命的缺点, 在数据量庞大时, 对性能的消耗非常大; 因此我们还需要学习一些有关查找的算法, 今天就介绍一下二分查找.
说明:二分查找又称为折半查找, 这种查找是有前提的:
要查找的数组必须是有序的,升序和降序均可; 以升序数组为例, 首先拿到已知元素(num)与数组中间位置的元素(mid)进行比较, 如果 mid > num, 说明 mid右边的数一定都比num大, 那么就可以把mid右边的数都pass, 直接从mid 左边的数里查找有没有num. 同理, 如果mid < num , 就说明mid左边的数都小于num , 就可以把它们都pass了. 这样反反复复直到查找到num为止.
图解: int[] sortNums = new int[] { 5, 12, 16, 36, 45, 99, 102 };
int start = 0, end = sortNums.Length - 1; // 定义开头和结尾的旗
Console.WriteLine("请输入你想要查找的数:");
int num = int.Parse(Console.ReadLine());
while(start <= end) // 如果start > end说明num不在查找的数组里, 就可以终止循环了
{
int mid = (start + end) / 2; // 每次都用中间的元素和num比较
if (sortNums[mid] > num)
{
// 如果 mid 大于 num 说明 mid 右边的数都比num大就没有比较的必要了, 把 end 放到mid-1的位置来.
end = mid - 1;
}
else if(sortNums[mid] < num)
{
start = mid + 1;
}
else
{
Console.WriteLine("查到了, 在第 {0} 个位置", mid + 1);
break;
}
}
if (start > end)
{
Console.WriteLine("对不起元素没有找到.");
}
四.二维数组(重点)
4.1二维数组的声明和初始化 声明数据类型[,] 数组名= new 数据类型[行数, 列数];初始化
: 分为动态初始化和静态初始化 , 花括号里面的各个花括号代表一行
第一种动态初始化:
int[, ] array = new int[2, 3] {{1, 2, 3}, {4, 5, 6}};
第二种动态初始化:
int[, ] array = new int[, ] {{1, 2, 3}, {4, 5, 6}};
静态初始化:
int[, ] array = {{1, 2, 3}, {4, 5, 6}};
注意: 二维数组静态初始化定义时, 行数可以是任意的, 但是列数必须是相同的, 即 每个内层花括号中元素的个数必须要相同.
4.2 二维数组的遍历C#中通过 GetLength方法可以得到二维数组的行数和列数
array.GetLength(0) 得到行数;
array.GetLength(1) 得到列数;
int[,] array = new int[2, 3] { { 7, 6, 3 }, { 2, 8, 5 } };
for(int i = 0; i < array.GetLength(0); i++)
{
for(int j = 0; j < array.GetLength(1); j++)
{
Console.Write(array[i, j] + " " );
}
Console.WriteLine();
}
1.定义一个数组, 将该数组的转置存到另一个数组中;
int[,] array = new int[2, 3] { { 7, 6, 3 }, { 2, 8, 5 } };
int[,] newArray = new int[array.GetLength(1), array.GetLength(0)];
for(int i = 0; i < array.GetLength(0); i++)
{
for(int j = 0; j < array.GetLength(1); j++)
{
newArray[j, i] = array[i, j];
}
}
Console.WriteLine("转置为:");
for (int i = 0; i < newArray.GetLength(0); i++)
{
for (int j = 0; j < newArray.GetLength(1); j++)
{
Console.Write(newArray[i, j] + " ");
}
Console.WriteLine();
}
2.有一个3行4列的二维数组, 要求编程找出最大元素, 并输出所在的行和列.
int[,] array = new int[,] { { 25, 6, 78, 5 }, { 4, 55, 8, 6 }, { 11, 2, 6, 74 } };
int max = array[0, 0], r = 0, c = 0;
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
if(max < array[i, j])
{
max = array[i, j];
r = i;
c = j;
}
}
}
Console.WriteLine("最大值为: {0}, 在{1}行 {2}列", max, r+1, c+1);
五.交错数组
5.1 交错数组中包含一维数组 声明:int[][] 数组名= new int[行数][列数]; 行数必须写, 但是列数可以不写
初始化:
int[][] array = new int[3][];
array[0] = new int[] { 1, 2, 3, 4 };
array[1] = new int[] { 6, 7, 8 };
array[2] = new int[] { 1, 4 };
// 赋值的时候必须动态赋值
int[][] array1 =
{
new int[] {1, 2, 3},
new int[] {3, 4, 5,6}
};
直接把写上行号和列号就可以, 例如, 如果我们要取 array1 中的元素2, 就可以写 array1[0][1];
遍历:交错数组的遍历要比二维数组更简单一些, 交错数组可以被拆分开
int[][] array = new int[3][];
array[0] = new int[] { 1, 2, 3, 4 };
array[1] = new int[] { 6, 7, 8 };
array[2] = new int[] { 1, 4 };
// array.Length得到该交错数组一共有多少行
for(int i = 0; i < array.Length; i++)
{
// array[i].Length 可以得到每行中有多少列
for(int j = 0; j < array[i].Length; j++)
{
Console.Write(array[i][j] + " " );
}
Console.WriteLine();
}
这个直接上代码会比较清晰
声明: 每一行都是一个二维数组, 声明时先定义好一共几行, 初始化的时候再具体定义每一行的二维数组;
取值: 先遍历每一行的元素, 针对各个行再用遍历二维数组的方法遍历;
=======================================================
思维导图