python-doc-tw.github.io/howto/sorting.html at master · python-doc-tw/python-doc-tw.github.io

History

466 lines (445 loc) · 46.4 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"

"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<head>

<title>如何排序 — Python 3.7.0 說明文件</title>

title="在 Python 3.7.0 說明文件中搜尋"

href="../_static/opensearch.xml"/>

</head><body>

<ul>

<a href="../genindex.html" title="General Index"

accesskey="I">索引</a></li>

<a href="../py-modindex.html" title="Python 模組索引"

>模組</a> |</li>

<a href="unicode.html" title="Unicode HOWTO"

accesskey="N">下一頁</a> |</li>

<a href="sockets.html" title="Socket Programming HOWTO"

accesskey="P">上一頁</a> |</li>

<li><img src="../_static/py.png" alt=""

style="vertical-align: middle; margin-top: -1px"/></li>

<li><a href="https://www.python.org/">Python</a> »</li>

<li>

zh_TW

3.7.0

<a href="../index.html">Documentation </a> »

</li>

<li class="nav-item nav-item-1"><a href="index.html" accesskey="U">Python HOWTOs</a> »</li>

</form>

</div>

</li>

</ul>

</div>

<tr class="field-odd field"><th class="field-name">Author:</th><td class="field-body">Andrew Dalke and Raymond Hettinger</td>

</tr>

<tr class="field-even field"><th class="field-name">Release:</th><td class="field-body">0.1</td>

</tr>

</tbody>

</table>

Python lists have a built-in <a class="reference internal" href="../library/stdtypes.html#list.sort" title="list.sort"><code class="xref py py-meth docutils literal notranslate">list.sort()</code></a> method that modifies the list

in-place. There is also a <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> built-in function that builds a new

sorted list from an iterable.

在此文件，我們使用Python進行各種方式排序資料

A simple ascending sort is very easy: just call the <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> function. It

returns a new sorted list:

[1, 2, 3, 4, 5]

</pre></div>

</div>

You can also use the <a class="reference internal" href="../library/stdtypes.html#list.sort" title="list.sort"><code class="xref py py-meth docutils literal notranslate">list.sort()</code></a> method. It modifies the list

in-place (and returns <code class="docutils literal notranslate">None</code> to avoid confusion). Usually it’s less convenient

than <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> - but if you don’t need the original list, it’s slightly

more efficient.

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> a = [5, 2, 3, 1, 4]

>>> a.sort()

>>> a

[1, 2, 3, 4, 5]

</pre></div>

</div>

Another difference is that the <a class="reference internal" href="../library/stdtypes.html#list.sort" title="list.sort"><code class="xref py py-meth docutils literal notranslate">list.sort()</code></a> method is only defined for

lists. In contrast, the <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> function accepts any iterable.

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})

[1, 2, 3, 4, 5]

</pre></div>

</div>

<h2>Key Functions<a class="headerlink" href="#key-functions" title="本標題的永久連結">¶</a></h2>

Both <a class="reference internal" href="../library/stdtypes.html#list.sort" title="list.sort"><code class="xref py py-meth docutils literal notranslate">list.sort()</code></a> and <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> have a key parameter to specify a

function to be called on each list element prior to making comparisons.

For example, here’s a case-insensitive string comparison:

['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

</pre></div>

</div>

The value of the key parameter should be a function that takes a single argument

and returns a key to use for sorting purposes. This technique is fast because

the key function is called exactly once for each input record.

A common pattern is to sort complex objects using some of the object’s indices

as keys. For example:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> student_tuples = [

... ('john', 'A', 15),

... ('jane', 'B', 12),

... ('dave', 'B', 10),

... ]

>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

The same technique works for objects with named attributes. For example:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> class Student:

... def __init__(self, name, grade, age):

... self.name = name

... self.grade = grade

... self.age = age

... def __repr__(self):

... return repr((self.name, self.grade, self.age))

</pre></div>

</div>

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> student_objects = [

... Student('john', 'A', 15),

... Student('jane', 'B', 12),

... Student('dave', 'B', 10),

... ]

>>> sorted(student_objects, key=lambda student: student.age) # sort by age

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

<h2>Operator Module Functions<a class="headerlink" href="#operator-module-functions" title="本標題的永久連結">¶</a></h2>

The key-function patterns shown above are very common, so Python provides

convenience functions to make accessor functions easier and faster. The

<a class="reference internal" href="../library/operator.html#module-operator" title="operator: Functions corresponding to the standard operators."><code class="xref py py-mod docutils literal notranslate">operator</code></a> module has <a class="reference internal" href="../library/operator.html#operator.itemgetter" title="operator.itemgetter"><code class="xref py py-func docutils literal notranslate">itemgetter()</code></a>,

<a class="reference internal" href="../library/operator.html#operator.attrgetter" title="operator.attrgetter"><code class="xref py py-func docutils literal notranslate">attrgetter()</code></a>, and a <a class="reference internal" href="../library/operator.html#operator.methodcaller" title="operator.methodcaller"><code class="xref py py-func docutils literal notranslate">methodcaller()</code></a> function.

Using those functions, the above examples become simpler and faster:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> from operator import itemgetter, attrgetter

</pre></div>

</div>

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

The operator module functions allow multiple levels of sorting. For example, to

sort by grade then by age:

[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

</pre></div>

</div>

[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

</pre></div>

</div>

<h2>升冪與降冪<a class="headerlink" href="#ascending-and-descending" title="本標題的永久連結">¶</a></h2>

boolean value. This is used to flag descending sorts. For example, to get the

student data in reverse age order:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> sorted(student_tuples, key=itemgetter(2), reverse=True)

[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

</pre></div>

</div>

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> sorted(student_objects, key=attrgetter('age'), reverse=True)

[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

</pre></div>

</div>

<h2>Sort Stability and Complex Sorts<a class="headerlink" href="#sort-stability-and-complex-sorts" title="本標題的永久連結">¶</a></h2>

Sorts are guaranteed to be <a class="reference external" href="https://en.wikipedia.org/wiki/Sorting_algorithm#Stability">stable</a>. That means that

when multiple records have the same key, their original order is preserved.

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]

>>> sorted(data, key=itemgetter(0))

[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

</pre></div>

</div>

Notice how the two records for blue retain their original order so that

<code class="docutils literal notranslate">('blue', 1)</code> is guaranteed to precede <code class="docutils literal notranslate">('blue', 2)</code>.

This wonderful property lets you build complex sorts in a series of sorting

steps. For example, to sort the student data by descending grade and then

ascending age, do the age sort first and then sort again using grade:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key

>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

The <a class="reference external" href="https://en.wikipedia.org/wiki/Timsort">Timsort</a> algorithm used in Python

does multiple sorts efficiently because it can take advantage of any ordering

already present in a dataset.

</div>

<h2>The Old Way Using Decorate-Sort-Undecorate<a class="headerlink" href="#the-old-way-using-decorate-sort-undecorate" title="本標題的永久連結">¶</a></h2>

This idiom is called Decorate-Sort-Undecorate after its three steps:

<li>First, the initial list is decorated with new values that control the sort order.</li>

<li>Second, the decorated list is sorted.</li>

<li>Finally, the decorations are removed, creating a list that contains only the

initial values in the new order.</li>

</ul>

For example, to sort the student data by grade using the DSU approach:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]

>>> decorated.sort()

>>> [student for grade, i, student in decorated] # undecorate

[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

</pre></div>

</div>

This idiom works because tuples are compared lexicographically; the first items

are compared; if they are the same then the second items are compared, and so

on.

It is not strictly necessary in all cases to include the index i in the

decorated list, but including it gives two benefits:

<li>The sort is stable – if two items have the same key, their order will be

preserved in the sorted list.</li>

<li>The original items do not have to be comparable because the ordering of the

decorated tuples will be determined by at most the first two items. So for

example the original list could contain complex numbers which cannot be sorted

directly.</li>

</ul>

Another name for this idiom is

<a class="reference external" href="https://en.wikipedia.org/wiki/Schwartzian_transform">Schwartzian transform</a>,

after Randal L. Schwartz, who popularized it among Perl programmers.

Now that Python sorting provides key-functions, this technique is not often needed.

</div>

<h2>The Old Way Using the cmp Parameter<a class="headerlink" href="#the-old-way-using-the-cmp-parameter" title="本標題的永久連結">¶</a></h2>

Many constructs given in this HOWTO assume Python 2.4 or later. Before that,

there was no <a class="reference internal" href="../library/functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> builtin and <a class="reference internal" href="../library/stdtypes.html#list.sort" title="list.sort"><code class="xref py py-meth docutils literal notranslate">list.sort()</code></a> took no keyword

arguments. Instead, all of the Py2.x versions supported a cmp parameter to

handle user specified comparison functions.

In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to

simplify and unify the language, eliminating the conflict between rich

comparisons and the <code class="xref py py-meth docutils literal notranslate">__cmp__()</code> magic method).

In Py2.x, sort allowed an optional function which can be called for doing the

comparisons. That function should take two arguments to be compared and then

return a negative value for less-than, return zero if they are equal, or return

a positive value for greater-than. For example, we can do:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> def numeric_compare(x, y):

... return x - y

>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)

[1, 2, 3, 4, 5]

</pre></div>

</div>

Or you can reverse the order of comparison with:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> def reverse_numeric(x, y):

... return y - x

[5, 4, 3, 2, 1]

</pre></div>

</div>

When porting code from Python 2.x to 3.x, the situation can arise when you have

the user supplying a comparison function and you need to convert that to a key

function. The following wrapper makes that easy to do:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>def cmp_to_key(mycmp):

'Convert a cmp= function into a key= function'

class K:

def __init__(self, obj, *args):

self.obj = obj

def __lt__(self, other):

return mycmp(self.obj, other.obj) < 0

def __gt__(self, other):

def __eq__(self, other):

def __le__(self, other):

def __ge__(self, other):

def __ne__(self, other):

return K

</pre></div>

</div>

To convert to a key function, just wrap the old comparison function:

<div class="highlight-pycon notranslate"><div class="highlight"><pre>>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))

[5, 4, 3, 2, 1]

</pre></div>

</div>

In Python 3.2, the <a class="reference internal" href="../library/functools.html#functools.cmp_to_key" title="functools.cmp_to_key"><code class="xref py py-func docutils literal notranslate">functools.cmp_to_key()</code></a> function was added to the

<a class="reference internal" href="../library/functools.html#module-functools" title="functools: Higher-order functions and operations on callable objects."><code class="xref py py-mod docutils literal notranslate">functools</code></a> module in the standard library.

</div>

<ul>

<li>For locale aware sorting, use <a class="reference internal" href="../library/locale.html#locale.strxfrm" title="locale.strxfrm"><code class="xref py py-func docutils literal notranslate">locale.strxfrm()</code></a> for a key function or

<a class="reference internal" href="../library/locale.html#locale.strcoll" title="locale.strcoll"><code class="xref py py-func docutils literal notranslate">locale.strcoll()</code></a> for a comparison function.

</li>

<li>The reverse parameter still maintains sort stability (so that records with

equal keys retain the original order). Interestingly, that effect can be

simulated without the parameter by using the builtin <a class="reference internal" href="../library/functions.html#reversed" title="reversed"><code class="xref py py-func docutils literal notranslate">reversed()</code></a> function

twice:

>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)

>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))

>>> assert standard_way == double_reversed

>>> standard_way

[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]

</pre></div>

</div>

</li>

<li>The sort routines are guaranteed to use <a class="reference internal" href="../reference/datamodel.html#object.__lt__" title="object.__lt__"><code class="xref py py-meth docutils literal notranslate">__lt__()</code></a> when making comparisons

between two objects. So, it is easy to add a standard sort order to a class by

defining an <a class="reference internal" href="../reference/datamodel.html#object.__lt__" title="object.__lt__"><code class="xref py py-meth docutils literal notranslate">__lt__()</code></a> method:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> Student.__lt__ = lambda self, other: self.age < other.age

>>> sorted(student_objects)

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

</pre></div>

</div>

</li>

<li>Key functions need not depend directly on the objects being sorted. A key

function can also access external resources. For instance, if the student grades

are stored in a dictionary, they can be used to sort a separate list of student

names:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> students = ['dave', 'john', 'jane']

>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}

>>> sorted(students, key=newgrades.__getitem__)

['jane', 'dave', 'john']

</pre></div>

</div>

</li>

</ul>

</div>

<ul>

<li><a class="reference internal" href="#key-functions">Key Functions</a></li>

<li><a class="reference internal" href="#operator-module-functions">Operator Module Functions</a></li>

<li><a class="reference internal" href="#ascending-and-descending">升冪與降冪</a></li>

<li><a class="reference internal" href="#sort-stability-and-complex-sorts">Sort Stability and Complex Sorts</a></li>

<li><a class="reference internal" href="#the-old-way-using-decorate-sort-undecorate">The Old Way Using Decorate-Sort-Undecorate</a></li>

<li><a class="reference internal" href="#the-old-way-using-the-cmp-parameter">The Old Way Using the cmp Parameter</a></li>

</ul>

</li>

</ul>

<a href="sockets.html"

title="上一章">Socket Programming HOWTO</a>

<a href="unicode.html"

title="下一章">Unicode HOWTO</a>

<li><a href="../bugs.html">Report a Bug</a></li>

<li>

<a href="https://github.com/python/cpython/blob/3.7/Doc/howto/sorting.rst"

rel="nofollow">Show Source

</a>

</li>

</ul>

</div>

</div>

<ul>

<a href="../genindex.html" title="General Index"

>索引</a></li>

<a href="../py-modindex.html" title="Python 模組索引"

>模組</a> |</li>

<a href="unicode.html" title="Unicode HOWTO"

>下一頁</a> |</li>

<a href="sockets.html" title="Socket Programming HOWTO"

>上一頁</a> |</li>

<li><img src="../_static/py.png" alt=""

style="vertical-align: middle; margin-top: -1px"/></li>

<li><a href="https://www.python.org/">Python</a> »</li>

<li>

zh_TW

3.7.0

<a href="../index.html">Documentation </a> »

</li>

<li class="nav-item nav-item-1"><a href="index.html" >Python HOWTOs</a> »</li>

</form>

</div>

</li>

</ul>

</div>

The Python Software Foundation is a non-profit corporation.

<a href="https://www.python.org/psf/donations/">Please donate.</a>

Last updated on 8月 22, 2018.

<a href="../bugs.html">Found a bug</a>?

Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.7.7.

</div>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

sorting.html

Latest commit

History

sorting.html

File metadata and controls