程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> [C#] 用菜鳥的思維學習算法,

[C#] 用菜鳥的思維學習算法,

編輯:C#入門知識

[C#] 用菜鳥的思維學習算法,


用菜鳥的思維學習算法 -- 馬桶排序、冒泡排序和快速排序

【博主】反骨仔    【來源】http://www.cnblogs.com/liqingwen/p/4994261.html   

馬桶排序

  一、場景:期末考試完了,老師要將同學們的分數從高到低排序。假設班上有 5 名同學,分別考了 5 分、3 分、5 分、2 分和 8 分【滿分:10 分】,排序後的結果就是 8 5 5 3 2,現在,讓我們先思考 10 分鐘吧!     二、思路:     (1)先創建一個數組 int scores[11],就有 scores[0]~scores[10] 共 11 個變量。我們用變量值為 0 表示沒有人得到該分數,即 scores [0]=0 表示沒有人得 0 分,scores [10]=0 表示沒有人得 10 分,而 scores [8]=1 表示有一個人得到 8 分。     (2)第 1 個數為 5,所以在 scores[5]=0 的基礎上+1,即 scores[5]=1 表示有 1 人得到 5 分     (3)第 2 個數為 3,所以在 scores[3]=0 的基礎上+1,即 scores[3]=1 表示有 1 人得到 3 分     (4)第 3 個數為 5,所以在 scores[5]=1 的基礎上+1,即 scores[5]=2 表示有 2 人得到 5 分          ... ...     (5)依此類推,處理第 4 和第 5 個數,最終的結果圖如下:     (6)我們發現,scores[0]~scores[10] 內對應的值就是 0~10 分中每個分數所出現的次數。現在,只需將結果打印即可,出現幾次就打印機次。          我們暫且稱它為“馬桶排序”,這個算法就相當於有 11 個馬桶,編號從 0~10。每出現一個數,就在對應編號的馬桶中放一個旗子。          三、思考:現在分別有 5 個人的名字和分數:小A 5、小二 3、小三 5、小妞 2 和王大錘 8,請按照分數從高到低,輸出他們的名字?          【特點】          假設需要排序的范圍 0~20000000,則需要 new int[20000001],非常浪費空間,即便只給 2 個數排序(1,19999999 );          如果排序的數是小數也不行,如:3.141 5926 5358 9793 2384 6264 3383 2795 0238;  

冒泡排序

  一、基本思想:每次比較相鄰的兩個 元素,按需調整順序     二、題目:要求將 12 35 99 18 76 這 5 個數進行從大到小排序     三、思路:     (1)先比較第 1 位和第 2 位的大小,12<35,因為希望越小越靠後,所以要調整兩者順序,交換後的結果:35 12 99 18 76     (2)現在比較第 2 位和第 3 位的大小,12<99,所以需要交換位置,交換後的結果為:35 99 12 18 76     (3)接著比較第 3 位和第 4 位的大小,12<18,交換後的結果為:35 99 18 12 76     (4)最後比較第 4 位和第 5 位的大小,12<76,交換後的結果為:35 99 18 76 12     (5)經過 4 次後我們發現 5 個數中最小的一個數已經就位,每將一個數歸位我們稱其為“一趟”;     (6)現在我們開始第二趟,目標將第 2 小的數歸位,根據之前邏輯,還是從第 1 個數和第 2 個數開始比較上:             35 99 18 76 12 --①--> 99 35 18 76 12 --②--> 99 35 18 76 12 --③--> 99 35 76 18 12             在第一趟比較就知道第 5 位是最小的,所以第 4 位不用和第 5 位比較,這一趟只需比較 3 次     (7)第3趟:99 35 76 18 12 --> 99 35 76 18 12 --> 99 76 35 18 12 (比較 2 次)     (8)第4趟:99 76 35 18 12 --> 99 76 35 18 12 ,有4個數已經就位,那麼最後一個數無須比較,它就是最大的     【總結】如果有 n 個數進行排序,只需將 n-1 個數歸位,即要進行 n-1 趟操作,而每一趟開始都從第 1 位進行相鄰的兩個數 進行比較,將小的那個數放在後面,已經歸位的就不用進行比較。      【特點】冒泡算法的核心部分是雙重嵌套循環,可以看出時間復雜度是 O(N²),這是一個非常高的時間復雜度。  

快速排序

  一、場景:對 6 1 2 7 9 3 4 5 10 8 這 10 個數進行排序     二、思路:     先找一個基准數(一個用來參照的數),為了方便,我們選最左邊的 6,希望將 >6 的放到 6 的右邊,<6 的放到 6 左邊。如:3 1 2 5 4 6 9 7 10 8     先假設需要將 6 挪到的位置為 k,k 左邊的數 <6,右邊的數 >6     (1)我們先從初始數列“6 1 2 7 9 3 4 5 10 8 ”的兩端開始“探測 ”,先從右邊往左找一個 <6 的數,再從左往右找一個 >6 的數,然後交換。我們用變量 i 和變量 j 指向序列的最左邊和最右邊。剛開始時最左邊 i=0 指向 6,最右邊 j=9 指向 8       (2)現在設置的基准數是最左邊的數,所以序列先右往左移動(j--),當找到一個 <6 的數(5)就停下來。接著序列從左往右移動(i++),直到找到一個 >6 的數又停下來(7);     (3)兩者交換,結果:6 1 2 5 9 3 4 7 10 8;       (4)j 的位置繼續向左移動(友情提示:每次都必須先從 j 的位置出發),發現 4 滿足要求,接著 i++ 發現 9 滿足要求,交換後的結果:6 1 2 5 4 3 9 7 10 8;
    (5)目前 j 指向的值為 9,i 指向的值為 4,j-- 發現 3 符合要求,接著 i++ 發現 i=j,說明這一輪移動結束啦。現在將基准數 6 和 3 進行交換,結果:3 1 2 5 4 6 9 7 10 8;現在 6 左邊的數都是 <6 的,而右邊的數都是 >6 的,但游戲還沒結束          (6)我們將 6 左邊的數拿出來先:3 1 2 5 4,這次以 3 為基准數進行調整,使得 3 左邊的數 <3,右邊的數 >3,根據之前的模擬,這次的結果:2 1 3 5 4     (7)再將 2 1 摳出來重新整理,得到的結果: 1 2     (8)剩下右邊的序列:9 7 10 8 也是這樣來搞,最終的結果: 1 2 3 4 5 6 7 8 9 10           【總結】快速排序的每一輪處理其實就是將這一輪的基准數歸位,當所有的基准數歸位,排序就結束啦        

  【參考】文字與插圖來源《啊哈!算法》

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved