排序應用

本頁面將簡要介紹排序的用法。

理解數據的特點

使用排序處理數據有利於理解數據的特點，方便我們之後的分析與視覺化。像一些生活中的例子比如詞典，菜單，如果不是按照一定順序排列的話，人們想要找到自己需要的東西的時間就會大大增加。

計算機需要處理大規模的數據，排序後，人們可以根據數據的特點和需求來設計計算機的後續處理流程。

使用排序預處理可以降低求解問題所需要的時間複雜度，通常是一個以空間換取時間的平衡。如果一個排序好的列表需要被多次分析的話，只需要耗費一次排序所需要的資源是很划算的，因為之後的每次分析都可以減少很多時間。

示例：檢查給定數列中是否有相等的元素

考慮一個數列，你需要檢查其中是否有元素相等。

一個樸素的做法是檢查每一個數對，並判斷這一對數是否相等。時間複雜度是 \(O(n^2)\)。

我們不妨先對這一列數排序，之後不難發現：如果有相等的兩個數，它們一定在新數列中處於相鄰的位置上。這時，只需要 \(O(n)\) 地掃一遍新數列了。

總的時間複雜度是排序的複雜度 \(O(n\log n)\)。

排序是二分查找所要做的預處理工作。在排序後使用二分查找，可以以 \(O(\log n)\) 的時間在序列中查找指定的元素。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用