最近看了一句話,說的是在現實生活中,會寫字的人不見得會寫出好文章,學習編程語言就像是學會了寫字,學會了編程語言並不一定能寫出好程式。 我覺得就是很有道理,以前讀書的時候,基本學完了C#中的語法知識,算是入了個門,但是一到寫程式就毫無頭緒,做出來的程式就像是小學生日記,僅僅只是用一些簡單的api把功能 ...
最近看了一句話,說的是在現實生活中,會寫字的人不見得會寫出好文章,學習編程語言就像是學會了寫字,學會了編程語言並不一定能寫出好程式。
我覺得就是很有道理,以前讀書的時候,基本學完了C#中的語法知識,算是入了個門,但是一到寫程式就毫無頭緒,做出來的程式就像是小學生日記,僅僅只是用一些簡單的api把功能拼湊起來,沒有一點邏輯性,毫不美觀優雅。
所以我決定慢慢的開始學習演算法知識,雖然我數學很爛,邏輯能力差到極點,看這些演算法的代碼看的我是心態爆炸,真的頭皮發麻,只有長期堅持學習,一點一點的慢慢進步了。
快速排序是分治法中的一種常見排序演算法,主要運用遞歸求解。
演算法思想是將一個數組分為小於等於基準數的子數組和大於基準數的子數組,然後通過遞歸調用,不斷對這兩個子數組進行排序,直到數組元素只有0個或1個元素時,停止遞歸,再將各個排好序的子數組加起來,最終就得到了排好序的數組。
步驟如下:
1. 選擇一個基準值
2. 將數組分為兩個子數組:小於基準值的元素和大於基準值的元素
3. 對這兩個子數組進行排序
接著對子數組重覆以上3步,直到子數組無法分解(子數組只有0個或1個元素時)
可以使用函數遞歸重覆上述過程,在遞歸函數中必須滿足2個條件
1.基線條件——指滿足某個條件以後,函數不在調用自身進行遞歸
2.遞歸條件——滿足遞歸條件就調用自身函數進行遞歸
我看的書舉例是使用Python代碼實現的快速排序,代碼如下:
1 def quicksort(array):
2 if len(array) < 2: #基線條件:為空或者只包含一個元素的數組是“有序”的
3 return array
4 else:#遞歸條件
5 pivot = array[0]
6 less = [i for i in array[1:] if i<= pivot]#由所有小於等於基準值的元素組成的數組
7 greater = [i for i in array[1:] if i> pivot]#由所有大於基準值的元素組成的子數組
8 return quicksort(less) + [pivot] + quicksort(greater)
9
10
11 print(quicksort([10, 5, 2, 3]))
在這段代碼里,首先滿足遞歸條件時,取得一個基準數,基準數通常為數組的第一個元素,然後分成兩個子數組,一個是小於等於基準數的子數組和大於基準數的子數組,不斷進行遞歸調用對這兩個子數組進行排序,最後得到排序好的數組。
書中講解看完後,頭腦里很快就有了思緒,但是當我想把上面的代碼轉換成C#時,就摸不著頭腦,打腦殼的遭不住,因為在C#里並不能像上面一樣簡簡單單的就實現,最主要的就是C#中數組不能通過直接相加來合併。
所以還是在網上看了不少C#快速排序的詳解後寫出了以下代碼:
1 /// <summary>
2 /// 快速排序對數組進行升序排序
3 /// </summary>
4 /// <param name="array">要排序的數組</param>
5 /// <param name="leftIndex">從左邊遍歷的第一個數的索引</param>
6 /// <param name="rightIndex">從右邊遍歷的第一個數的索引</param>
7 public static void QuickSort(int[] array, int leftIndex, int rightIndex)
8 {
9 if (leftIndex >= rightIndex)//基線條件
10 return;
11 int n = leftIndex;
12 int m = rightIndex;
13 int pivot = array[leftIndex];
14 while (n != m)
15 {
16 for (; n < m; m--)
17 {
18 if (array[m] < pivot)
19 {
20 array[n] = array[m];//交換位置
21 break;
22 }
23 }
24 for (; n < m; n++)
25 {
26 if (array[n] > pivot)
27 {
28 array[m] = array[n];
29 break;
30 }
31 }
32 }
33 array[n] = pivot;//迴圈完成後已經按照小於基準數和大於基準數左右排好序,基準數放中間。
34 QuickSort(array, leftIndex, n - 1);//對著兩個子數組進行遞歸
35 QuickSort(array, n + 1, rightIndex);
36 }
網上快速排序的思路如上,甚至來說基線條件和我在書中看見的都已經完全不一樣,並且和書中的邏輯也不太相同,只是依舊是分治法解決問題。
不僅是分出兩個子數組,而是對當前的數組進行排序,排序過程也不好理解,從右至左迴圈,找出比基準數大的數,再從左至右迴圈,找出比基準數小的數,然後將兩個數字調換位置,到最後只剩一個數的時候,就是基準數該在的位置,把基準數放到這個位置。
所以我足足想了2天,才能夠獨立寫出上面的快速排序代碼,不過我已經不知道我到底是真真切切理解了排序的思路,還是說因為看了太久,已經把排序的方式背在腦中了,真是悲哀,聰明的小伙伴一定一下就能學會,我卻想了兩天連自己也不清楚到底想明白沒有了。
最後,我依舊有一個疑問,快速排序的時間複雜度是O(nlogn),那麼上面的Python代碼依舊是O(nlogn)嗎?
新聲明數組,然後將他們賦值,再合併,這樣的操作會影響時間複雜度嗎?
甚至我想用Linq語法
1 int[] less = (from i in array where i < pivot select i).ToArray();
2 int[] greater = (from i in array where i > pivot select i).ToArray();
返回的數組甚至還是排好序的,那我直接用將這兩個數組和基準數加起來不是更簡單嗎?我已經完全懵逼了,不知道時間複雜度是如何計算的,學習的長路真是漫漫啊!