工作小驛

          Ninja!

          BlogJava 首頁 新隨筆 聯(lián)系 聚合 管理
            103 Posts :: 0 Stories :: 36 Comments :: 0 Trackbacks
          接上文

          第三種:插入排序

          public static int[] insertionSort(int[] a) {
          int n = a.length;
          for (int i = 1; i < n; i++) {
          int temp = a[i];
          int j;
          for (j = i - 1; j >= 0 && temp < a[j]; j--) {
          a[j + 1] = a[j];
          }
          a[j + 1] = temp;
          }
          return a;
          }
          }

          算法分析: 插入排序的思想是這樣的,第一層for循環(huán)表示要循環(huán)n次,且每次循環(huán)要操作的主體是a[i],第二層循環(huán)是對a[i]的具體操作,是從原數(shù)祖第i個位置起,向前比較,若a[i]比前面的數(shù)小,前面的數(shù)后移占去a[i]的位置,同時也為a[i]空出了插入地點,然后向前繼續(xù)比較,直到a[i]比前面的數(shù)來的大,插入。下一次循環(huán)開始,這樣就完成一個完整的升序插入排序。

          很明顯,這種排序也是不穩(wěn)定的,
          最好的情況是:順序已經(jīng)排好那么我們只要進行n-1次比較即可。
          最壞的情況是:順序恰好是逆序,慘了,我們要比較1+2+...+n-1次

          平均的復雜度算起來還是比較困難的,也是很有參考價值的:

          1。首先,我們來看 對于第i個元素 a[i] 的操作

          從等概率角度思考:a[i]只比較 1 次的概率為 1/i;
          a[i]只比較 2 次的概率為 1/i;
          a[i]只比較 3 次的概率為 1/i;




          a[i]只比較 i-1 次的概率為 1/i;
          a[i]只比較 i 次的概率為 1/i;
          于是又編號為i的元素平均比較次數(shù)為:(1/i)*(1+2+3+...+i)=(i+1)/2

          2。然后我們來看

          平均比較次數(shù)為 T=(2+3+4+...+n)/2
          所以插入排序的平均時間復雜度也是O(n^2).



          第四種:Rank排序
          public static int[] rankSort(int[] a){
          int n=a.length;
          int[] r1=new int[n];
          int[] r2=new int[n];
          for (int i = 0; i for(int j=i+1;j if(a[i] r1[j]++;
          else
          r1[i]++;
          }
          }
          for(int i=0;i r2[r1[i]]=a[i];
          }
          return r2;
          }





          算法分析:Rank排序是基于這樣的思想,建立一個和待排序數(shù)組相同大小的數(shù)組,初識化為全0,然后掃描原數(shù)組將每個數(shù)的大小排名,然后更具排名安排各自元素的位次,思路非常簡單
          復雜度分析:這個算法是穩(wěn)定的一共要比較的次數(shù)為n*(n-1)/2
          時間復雜度是O(n^2);
          posted on 2007-09-20 15:58 王君 閱讀(812) 評論(2)  編輯  收藏 所屬分類: J2SE

          Feedback

          # re: JAVA 實現(xiàn)各種排序算法和復雜度分析2 2007-09-22 00:18 千里冰封
          分析得很有道理  回復  更多評論
            

          # re: JAVA 實現(xiàn)各種排序算法和復雜度分析2 2007-09-23 00:19 黑蝙蝠
          for (int i = 0; i for(int j=i+1;j
          if(a[i]
          r1[j]++;
          else
          r1[i]++;
          }

          Rank排序這代碼寫錯了?
          快速排序講不?  回復  更多評論
            

          主站蜘蛛池模板: 平泉县| 高雄县| 轮台县| 榕江县| 利辛县| 三台县| 沅江市| 来凤县| 乐业县| 仙居县| 南皮县| 六枝特区| 射洪县| 茌平县| 清原| 寻乌县| 正定县| 凤凰县| 安泽县| 苍溪县| 收藏| 建阳市| 武隆县| 定兴县| 安义县| 云安县| 崇信县| 阿克苏市| 柏乡县| 阿勒泰市| 微博| 班玛县| 镇原县| 习水县| 千阳县| 利津县| 沭阳县| 同心县| 宜州市| 汤原县| 景宁|