ACM_ICPC競賽中sort函數的簡要介紹

文/焦靜頤 崔馭 賈子璇

1 sort函數的介紹及優點

sort函數是STL中用于對給定區間進行排序的函數，所在頭文件是#include 。主要原理是快速排序，但又不是簡單的快速排序，它還結合了插入排序和堆排序，根據需要排序對象的不同情況，自動選用合適的排序方法。所以雖然理論上sort函數和快速排序的復雜度都是O(n*logn)，但在實際應用中，sort函數比快速排序的效率更高，實用方法簡單，因此更加實用。

2 sort函數的使用方法

sort函數有三個參數

（1）要排序數組的起始地址。

（2）要排序數組的結束地址，即最后一個要排序地址的下一個地址。

（3）排序方法，可以是從大到小，也可以自定義，也可以不寫，如果不寫，默認的排序方式是從小到大排序。

sort函數使用模板是：

sort(start,end,cmp);

對區間[f irst,last)根據cmp的方式進行排序。

3 sort函數的用法舉例

3.1 直接使用

整型默認為從小到大排序，字符型根據ASCII碼值進行排序。

N為整型常數，f irst為起始地址，last為結束地址。

3.2 自定義排序

3.2.1 自定義比較函數

系統默認為x>y返回true，故程序是從大到小排序。

3.2.2 重載比較運算符

這種方法用于結構體中。

根據成員a的數值由大到小排序，當a的數值相同時，根據成員b的數值由小到大排序。

4 結束語

sort函數在使用上帶來極大便利，因為高效率，使用靈活的特點，無論是在日常開發中還是算法競賽中，sort函數都能發揮很大的作用。本文介紹了sort的使用方法，只要加以練習，就可以將sort函數更好的應用。掌握好sort函數對學生學習其他STL函數也有很大幫助，可以提高學生的編程能力。