Python实现快速排序算法及去重的快速排序的简单示例-Python教學-PHP中文網

首頁

後端開發

Python教學

Python实现快速排序算法及去重的快速排序的简单示例

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jul 06, 2016 pm 01:29 PM

python 快速排序排序演算法

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

现在通过一个实例来说明快排。

比如有一个数组：

6 2 4 5 3

登入後複製

第一步：选取一个基准数，不要被这个名词吓到了，你可以把它看作是一个比较大小的数，因为排序就是比较大小，

比如我选取最后一个数3为基准数，依次把数组的数和3比较，比3小的放左边，比3大的放右边，这样有如下结果：

2 3 6 4 5

登入後複製

第二步：判断区间个数，经过第一步后左边区间只有一个数了，没有数字再和它比较了，因此不需要重复操作，右边区间还有：

6 4 5

登入後複製

重复第一步，选取5作为基准数，得到比较结果：

4 5 6

登入後複製

这样左右两边区间都只有一个数了，这就标志着排序完成，最后把所有区间合并就得到排序结果：

2 3 4 5 6

登入後複製

def quick_sort(array):
  less = []; greater = []
  if len(array) <= 1:
    return array
  pivot = array.pop()
  for x in array:
    if x <= pivot: less.append(x)
    else: greater.append(x)
  return quick_sort(less) + [pivot] + quick_sort(greater)
list = [2,4,2,6,7,8,1]

登入後複製

print quick_sort(list)

登入後複製

[1, 2, 2, 4, 6, 7, 8]

登入後複製

相比C、C#、JAVA之类的是不是简单多了^.^

TIP：去重的快速排序
如下, 只需要把集合修改为单值元素,这里我们使用Python3来演示:

# -*- coding: utf-8 -*- 
  
import random 
 
L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] 
 
def qsort(L): 
  if len(L)<2: return L 
  pivot_element = random.choice(L) 
  small = [i for i in L if i< pivot_element] 
  #medium = [i for i in L if i==pivot_element] 
  large = [i for i in L if i> pivot_element] 
  return qsort(small) + [pivot_element] + qsort(large) 
 
print(qsort(L))

登入後複製

输出:

[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]

登入後複製

也可以直接使用, 集合(set)进行排序和去重.

mylist = list(set(L)) #集合自动排序字符串

登入後複製

本網站聲明

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

熱工具

熱門話題

gmail信箱登陸入口在哪裡

7868

Java教學

1649

CakePHP 教程

1407

Laravel 教程

1301

PHP教程

1243

Related knowledge

PHP和Python：解釋了不同的範例 Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程，但也支持面向對象編程（OOP）；Python支持多種範式，包括OOP、函數式和過程式編程。 PHP適合web開發，Python適用於多種應用，如數據分析和機器學習。

在PHP和Python之間進行選擇：指南 Apr 18, 2025 am 12:24 AM

PHP適合網頁開發和快速原型開發，Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發，語法簡單，適合快速開發。 2.Python語法簡潔，適用於多領域，庫生態系統強大。

PHP和Python：深入了解他們的歷史 Apr 18, 2025 am 12:25 AM

PHP起源於1994年，由RasmusLerdorf開發，最初用於跟踪網站訪問者，逐漸演變為服務器端腳本語言，廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發，1991年首次發布，強調代碼可讀性和簡潔性，適用於科學計算、數據分析等領域。

Python vs. JavaScript：學習曲線和易用性 Apr 16, 2025 am 12:12 AM

Python更適合初學者，學習曲線平緩，語法簡潔；JavaScript適合前端開發，學習曲線較陡，語法靈活。 1.Python語法直觀，適用於數據科學和後端開發。 2.JavaScript靈活，廣泛用於前端和服務器端編程。

vs code 可以在 Windows 8 中運行嗎 Apr 15, 2025 pm 07:24 PM

VS Code可以在Windows 8上運行，但體驗可能不佳。首先確保系統已更新到最新補丁，然後下載與系統架構匹配的VS Code安裝包，按照提示安裝。安裝後，注意某些擴展程序可能與Windows 8不兼容，需要尋找替代擴展或在虛擬機中使用更新的Windows系統。安裝必要的擴展，檢查是否正常工作。儘管VS Code在Windows 8上可行，但建議升級到更新的Windows系統以獲得更好的開發體驗和安全保障。

sublime怎麼運行代碼python Apr 16, 2025 am 08:48 AM

在 Sublime Text 中運行 Python 代碼，需先安裝 Python 插件，再創建 .py 文件並編寫代碼，最後按 Ctrl B 運行代碼，輸出會在控制台中顯示。

visual studio code 可以用於 python 嗎 Apr 15, 2025 pm 08:18 PM

VS Code 可用於編寫 Python，並提供許多功能，使其成為開發 Python 應用程序的理想工具。它允許用戶：安裝 Python 擴展，以獲得代碼補全、語法高亮和調試等功能。使用調試器逐步跟踪代碼，查找和修復錯誤。集成 Git，進行版本控制。使用代碼格式化工具，保持代碼一致性。使用 Linting 工具，提前發現潛在問題。

vscode在哪寫代碼 Apr 15, 2025 pm 09:54 PM

在 Visual Studio Code（VSCode）中編寫代碼簡單易行，只需安裝 VSCode、創建項目、選擇語言、創建文件、編寫代碼、保存並運行即可。 VSCode 的優點包括跨平台、免費開源、強大功能、擴展豐富，以及輕量快速。

See all articles

Python实现快速排序算法及去重的快速排序的简单示例

熱AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

熱門文章

熱工具

記事本++7.3.1

SublimeText3漢化版

禪工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

熱門話題