-
Notifications
You must be signed in to change notification settings - Fork 0
/
ch09.html
2 lines (2 loc) · 5.58 KB
/
ch09.html
1
2
<!DOCTYPE html><html></html><head><meta charset="UTF-8"><meta content="text/html; charset=UTF-8" http-equiv="content-type"><link href="style.css" rel="stylesheet" type="text/css"><link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css"><script src="jquery/dist/jquery.min.js"></script><script type="text/javascript" src="./selectchapter.js"></script><script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script><title>第九章 排序</title></head><body><nav class="navbar navbar-default" role="navigation"><div class="container-fluid"><div class="navbar-header"><a class="navbar-brand" href="index.html">板中資訊社</a></div><div><ul class="nav navbar-nav"><li class="active"><a href="#">C++</a></li><li class="dropdown"><a class="dropdown-toggle" href="#" data-toggle="dropdown">課程<b class="caret"></b></a><ul class="dropdown-menu"><li><a href="ch01.html">第一章 立刻動手</a></li><li><a href="ch02.html">第二章 變數與指定運算子「=」</a></li><li><a href="ch03.html">第三章 比較運算子與 if 陳述式</a></li><li><a href="ch04.html">第四章 迴圈</a></li><li><a href="ch05.html">第五章 基礎資料型別</a></li><li><a href="ch06.html">第六章 字元與字串</a></li><li><a href="ch07.html">第七章 陣列</a></li><li><a href="ch08.html">第八章 自定義函數與資料型別</a></li><li><a href="ch09.html">第九章 排序</a></li></ul></li><li class="dropdown"><a class="dropdown-toggle" href="#" data-toggle="dropdown">附錄<b class="caret"></b></a><ul class="dropdown-menu"><li><a href="basic_type.html">A 基礎資料型別</a></li></ul></li></ul></div></div></nav><h1>第九章 排序</h1><button id="button1">特殊條件排序</button><button id="button2">字典序</button><button id="button3">排序演算法</button><div class="para" id="para1" style="display:none;"><h2>9.1 特殊條件排序</h2><p>第七章中我們用 <algorithm> 中的 sort
函數來排序。但是它只能依數值由小到大排序。可是如果遇到特殊條件的排序,Sort 就不知道要如何去排了。</p><li><a href="https://zerojudge.tw/ShowProblem?problemid=d750">d750. 11321 - Sort! Sort!! and Sort!!!</a></li><p>這題的排序條件很詭異。</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-01.cpp"></script><li><a href="https://zerojudge.tw/ShowProblem?problemid=d731">d731. 11039 - Building designing</a></li><li><a href="https://zerojudge.tw/ShowProblem?problemid=d305">d385: 10905 - Children's Game</a></li><li><a href="http://contest.cc.ntu.edu.tw/npsc2005/problem/2005jFinal.doc">2005 NPSC 國中組決賽 E. 誰先晚餐(高中組決賽pE)</a></li></div><div class="para" id="para2" style="display:none;"><h2>9.2 字典序</h2><li><a href="https://zerojudge.tw/ShowProblem?problemid=d829">d829. 146 - ID Codes</a></li><p>給你一串陣列,,要你找出下一個排列</p><p>規則</p><ol><li>找出最右邊一組a[x]小於a[x+1]</li><li>找不到時已經到最大排列,停止搜尋</li><li>否則找出在a[x]右邊大裕a[x],的最小值a[y]</li><li>交換a[x]和a[y]</li><li>翻轉a[x]的序列</li><li>所得排列即得所求</li></ol><p>以下是範例程式碼</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-02.cpp"></script><h3>next_permutation</h3><p>c++裡已有內建字典序排列,是在<algorithm>的next_permutation</algorithm></p><p>範例如下</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-03.cpp"></script><p>是不是簡潔許多?</p></div><div class="para" id="para3" style="display:none;"><h2>9.3 排序演算法</h2><p>在第七章使用"algorithm"裡的sort解題目時,你可能遇到TLE,這時你可能會懷疑是不是自己寫出無限迴圈,但其實是sort讓你超過時間了,在<a href="https://l.facebook.com/?u=https%3A%2F%2Fzh.wikipedia.org%2Fwiki%2F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&e=ATMU7TuXbr4Pz69i_8NZUXeuPoPy0IEa3QeCr3_CaRvR7L0VU6PoBoW5CaWcMnblh5OSxa2e-f_uYfM4KcTrQYDUryWgthVaF6oRjf19SfUuZ-n8CAt7FIpQ_fzm52nRLvxf5mE">wiki的排序演算法</a>內有各種演算法,例如sort是內省排序。這些演算法各有優缺點,有的省時,有的省空間,有的很好寫,以下介紹幾種</p><li>氣泡排序</li><p>氣泡排序是一種最基本的排序,是兩兩元素做比較然後交換。時間複雜度為O(n^2),空間複雜度為O(n)。</p><p>範例程式碼</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-04.cpp"></script><li>合併排序</li><p>合併排序法是使用分治法的概念,先將陣列分成兩半,再將兩個小陣列進行比大小,合併成一個陣列,以此類推,時間複雜度為O(n log n),空間複雜度為O(n)</p><p>範例程式碼</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-05.cpp"></script><li>計數排序</li><p>計數排序是一種線性時間排序算法,須先開一個陣列來計算各個數字的總數,再開另一個陣列,把數字由小(大)到大(小)填入,時間複雜度為O(n+k),空間複雜度為O(n+k),n為陣列大小,k為數字範圍。</p><p>範例程式碼</p><script src="https://gist.github.com/allem40306/63bb96df79dde4a3efce7e27bb0fd16c.js?file=sort-06.cpp"></script><p>補充資料</p><li><a href="www.csie.ntnu.edu.tw/~u91029/SequenceManipulation.html">演算法筆記 - Sequence Manipulation</a></li><li><a href="https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95">wiki 排序演算法</a></li><br><br><br></div></body>