一. 冒泡排序(重點)
思路:每次比較把較小的放在前面, 大的放到後面;
圖解:下圖是最壞情況下的排序
冒泡排序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();
}
這個直接上代碼會比較清晰
聲明: 每一行都是一個二維數組, 聲明時先定義好一共幾行, 初始化的時候再具體定義每一行的二維數組;
取值: 先周遊每一行的元素, 針對各個行再用周遊二維數組的方法周遊;
=======================================================
思維導圖