排序演算法基本思想及實現

来源:https://www.cnblogs.com/shixiaogu/archive/2022/09/21/16716138.html
-Advertisement-
Play Games

一、插入排序 1、直接插入排序 基本思想:類似抓撲克牌,待排序元素在已排序的序列中從後往前遍歷,遇到小於他的元素向後移一位,直至遇到小於或等於他的元素,在其後插入即可 2、希爾排序(是對直接插入排序的一種改進) 二、交換排序 1、冒泡排序 基本思想:相鄰的兩個元素進行兩兩比較,如果出現逆序,則小的元 ...


一、插入排序

1、直接插入排序

    基本思想:類似抓撲克牌,待排序元素在已排序的序列中從後往前遍歷,遇到小於他的元素向後移一位,直至遇到小於或等於他的元素,在其後插入即可

2、希爾排序(是對直接插入排序的一種改進)

二、交換排序

  1、冒泡排序

    基本思想:相鄰的兩個元素進行兩兩比較,如果出現逆序,則小的元素向前移動

    代碼實現:

      

 1 def bubble_sort(lst):
 2     """冒泡排序"""
 3     n = len(lst)
 4     for i in range(n):
 5         for j in range(1, n-i):
 6             if not lst[j-1] > lst[j]:
 7                 # print("{}小於{},無需替換".format(lst[j-1], lst[j]))
 8                 continue
 9             lst[j-1], lst[j] = lst[j], lst[j-1]
10 
11     return lst

  2、快速排序(是對冒泡排序的一種改進)

    基本思想:找到一個基準元素,比其小的元素放置左邊,反之不小於他的元素放置右邊,由此分成左右兩個區間,對左右兩個區間進行遞歸,重覆以上操作,最終形成有序序列

    代碼實現:

1 def quick_sort(lst):
2     """快速排序"""
3     n = len(lst)
4     if n <= 1:
5         return lst
6     baseline = lst[0]
7     left = [lst[i] for i in range(1, len(lst)) if lst[i] < baseline]
8     right = [lst[i] for i in range(1, len(lst)) if lst[i] >= baseline]
9     return quick_sort(left) + [baseline] + quick_sort(right)

 

三、選擇排序

  1、直接選擇排序

    基本思想:從待排序記錄中找到最小或最大的元素,放置起始位置,然後再從剩下的序列中找到最值,放置在已排序的序列末尾,直至待排序記錄為空

    代碼實現:

1 def select_sort(lst):
2     """直接選擇排序"""
3     for i in range(len(lst)):
4         res = min(lst)
5         yield res
6         lst.remove(res)

  2、堆排序

    基本思想:堆是python中一種基本的數據結構,heapq[0]永遠是序列中最小的元素

    代碼實現:

1 def select_sort(lst):
2     """堆排序"""
3     heapq.heapify(lst)
4     for i in range(len(lst)):
5         yield heapq.heappop(lst)

四、歸併排序

  1、二路歸併排序

    基本思想:先拆再合:帶有N個元素的待排序序列分成N個子序列 ,相鄰的序列進行兩兩合併,在合併的過程中,較小的元素放置左邊,較大的元素放置右邊

以上總結僅代表個人理解,可能存在不足,還請批評指正

只有永不遏止的奮鬥,才能使青春之花,即便是凋謝,也是壯麗地凋謝
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 前言 工欲善其事,必先利其器。本篇文章我們介紹下 Terraform,為後續創建各種雲資源做準備,比如Kubernetes 關鍵詞:IaC, Infrastructure as Code, Terraform, 基礎架構即代碼,Terraform 例子, Terraform 入門,Terraform ...
  • 顧名思義,子流程是一個包含其他活動、網關、事件等的活動,這些活動本身形成了一個流程,該流程是更大流程的一部分。 使用子流程確實有一些限制: 一個子流程只能有一個none類型的啟動事件,不允許有其他類型的啟動事件。一個子流程必須至少有一個結束事件。(請註意,BPMN 2.0 規範允許在子流程中省略開始 ...
  • Docker安裝和卸載 一,已安裝Docker,卸載Docker 1.方法一 sudo yum remove docker \ docker-client \ docker-client-latest \ docker-common \ docker-latest \ docker-latest-l ...
  • Django_模型ORM Django中內嵌了ORM框架,不需要直接編寫SQL語句進行資料庫操作,而是通過定義模型類,操作模型類來完成對資料庫中表的增刪改查和創建等操作。 O是object,也就類對象的意思。 R是relation,翻譯成中文是關係,也就是關係資料庫中數據表的意思。 M是mappin ...
  • 17.1遠程資源授權準備 17.1.1認證和訪問流程圖 參考:http://www.zyiz.net/tech/detail-141309.html 17.1.2為用戶指定角色 可以使用ROLE_USER和ROLE_ADMIN 兩種角色 17.1.3添加認證服務和資源服務 17.1.4配置客戶端的認 ...
  • 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 特效 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> O ...
  • “為什麼加索引能提升查詢效率”! 我們都認為“加索引”提升查詢效率是理所應當的 竟然還有理由? 該怎麼回答呢? 大家好,我是Mic,一個工作了14年的Java程式員 下麵分析一下這個問題的考察點 考察目標 這是一道原理性的問題,考察求職者對於Mysql中索引的實現原理的理解程度。 一般情況下,考察3 ...
  • 摘要:java中一切都是對象,為什麼int不用創建對象實例化,而可以直接使用? 本文分享自華為雲社區《【Java】對基本類型-整型數據結構的認識》,作者: huahua.Dr 。 整型數據類型有兩個:基本類型和引用類型(包裝類) 整數型基本類型:byte,int,short,long 其引用類型:B ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 1.講故事 在分析的眾多dump中,經常會遇到各種奇葩的問題,僅通過dump這種快照形式還是有很多問題搞不定,而通過 perfview 這種粒度又太粗,很難找到問題之所在,真的很頭疼,比如本篇的 短命線程 問題,參考圖如下: 我們在 t2 時刻抓取的dump對查看 短命線程 毫無幫助,我根 ...
  • 在日常後端Api開發中,我們跟前端的溝通中,通常需要協商好入參的數據類型,和參數是通過什麼方式存在於請求中的,是表單(form)、請求體(body)、地址欄參數(query)、還是說通過請求頭(header)。 當協商好後,我們的介面又需要怎麼去接收這些數據呢?很多小伙伴可能上手就是直接寫一個實體, ...
  • 許多情況下我們需要用到攝像頭獲取圖像,進而處理圖像,這篇博文介紹利用pyqt5、OpenCV實現用電腦上連接的攝像頭拍照並保存照片。為了使用和後續開發方便,這裡利用pyqt5設計了個相機界面,後面將介紹如何實現,要點包括界面設計、邏輯實現及完整代碼。 ...
  • 思路分析 註冊頁面需要對用戶提交的數據進行校驗,並且需要對用戶輸入錯誤的地方進行提示! 所有我們需要使用forms組件搭建註冊頁面! 平時我們書寫form是組件的時候是在views.py裡面書寫的, 但是為了接耦合,我們需要將forms組件都單獨寫在一個地方,需要用的時候導入就行! 例如,在項目文件 ...
  • 思路分析 登錄頁面,我們還是採用ajax的方式提交用戶數據 唯一需要學習的是如何製作圖片驗證碼! 具體的登錄頁面效果圖如下: 如何製作圖片驗證碼 推導步驟1:在img標簽的src屬性里放上驗證碼的請求路徑 補充1.img的src屬性: 1.圖片路徑 2.url 3.圖片的二進位數據 補充2:字體樣式 ...
  • 哈嘍,兄弟們! 最近有許多小伙伴都在吐槽打工好難。 每天都是執行許多重覆的任務 例如閱讀新聞、發郵件、查看天氣、打開書簽、清理文件夾等等, 使用自動化腳本,就無需手動一次又一次地完成這些任務, 非常方便啊有木有?! 而在某種程度上,Python 就是自動化的代名詞。 今天就來和大家一起學習一下, 用 ...
  • 作者:IT王小二 博客:https://itwxe.com 前面小二介紹過使用Typora+PicGo+LskyPro打造舒適寫作環境,那時候需要使用水印功能,但是小二在升級LskyPro2.x版本發現有很多不如人意的東西,遂棄用LskyPro使用MinIO結合代碼實現自己需要的圖床功能,也適合以後 ...
  • OpenAI Gym是一款用於研發和比較強化學習演算法的工具包,本文主要介紹Gym模擬環境的功能和工具包的使用方法,並詳細介紹其中的經典控制問題中的倒立擺(CartPole-v0/1)問題。最後針對倒立擺問題如何建立控制模型並採用爬山演算法優化進行了介紹,並給出了相應的完整python代碼示例和解釋。要... ...
  • python爬蟲瀏覽器偽裝 #導入urllib.request模塊 import urllib.request #設置請求頭 headers=("User-Agent","Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, l ...
  • 前端代碼搭建 主要利用的是bootstrap3中js插件里的模態框版塊 <li><a href="" data-toggle="modal" data-target=".bs-example-modal-lg">修改密碼</a></li> <div class="modal fade bs-exam ...