iOS可視化動態繪製八種排序過程(Swift版)

收藏待读

前面幾篇博客都是關於排序的,在之前陸陸續續發佈的博客中,我們先後介紹了冒泡排序、選擇排序、插入排序希爾排序、堆排序、歸併排序以及快速排序。俗話說的好,做事兒要善始善終,本篇博客就算是對之前那幾篇博客的總結了。而本篇博客的示例Demo也是在之前那些博客Demo的基礎上做的,也算是集成了各種排序的方法,然後給出了可視化的解決方案。今天博客的內容還是比較有趣的。

因為本猿是做iOS開發的,所以就使用iOS相關的組件來表示上述各種排序的過程。使用可視化方式來感受一下上述這些排序方法的異同。本篇博客所使用的相關的排序代碼都是來自於之前的博客。因為我們在之前實現各種排序Demo時,我們定義了相應的排序接口SortType,所以上述的七種排序對外的調用方式是一致的,所以在此基礎上給出相應排序的可視化解決方案並不困難。本篇博客就會給出其相應的擴展過程。

如果你想對上述7中排序進行詳細的了解,請移步與之前的博客《 冒泡排序、插入排序、希爾排序、選擇排序 》、《 堆排序 》、《 歸併排序 》、《 快速排序 》、《 基數排序 》。廢話少說,開始今天的博客。

一、可視化解決方案綜述

1.交互UI綜述

在本篇博客的第一部分我們先來整體的看一下我們Demo的功能。下方就是我們今天博客中的Demo的交互示意圖。上方的輸入框可以輸入要排序元素的個數,下方輸入的是300。程序會根據你輸入的個數來隨機生成數據,你輸入300,就會隨機生成300個數據提供排序使用。下方的SegmentControl可以選擇不同的排序方式,本篇博客給出了7中常用的排序方式,選擇完排序方式後可以點擊右上方的排序按鈕進行相應的排序。

下方顯示的不同顏色的顏色條就是我們要排序的東西,我們會按照從小到大的方式對這些色條進行排序。左圖中是未排序的狀態,右圖中是已經排序的狀態。我們上面隨機生成的數據反應到色條上就是色條的高度,我們按照色條的高度進行從小到大的排序。下方會給出每種排序的介紹。

iOS可視化動態繪製八種排序過程(Swift版)iOS可視化動態繪製八種排序過程(Swift版)

2、部分核心代碼實現

為了實現今天的Demo,我們需要對之前我們實現的那一些列的排序的方法進行擴展。因為我們之前在實現各種排序時,我們先定義了SortType接口,依據「開放封閉原則」,我們可以為各種排序的類創建一個「簡單工廠」以供我們的視圖層使用。關於設計模式更多以及更詳細的內容,可以移步之前發佈的設計模式系列博客《 設計模式Swift版 》。

iOS可視化動態繪製八種排序過程(Swift版)

上方就是為各種Sort類提供的「簡單工廠」。上面這個簡單工廠在視圖控制器中點擊SegmentControl時會使用,因為我們在選擇不同排序類的時候需要使用不同的排序對象。下方就是我們視圖控制器對「簡單工廠」的調用,當然我們所有排序類都有父類,你也可以使用「工廠方法」來創建相應的對象,在此就不做過多贅述了。

下方代碼段就是點擊SegmentControl要調用的方法,其中從「簡單工廠」中獲取到相應排序方式的對象後,然後在設置相應的閉包回調。

iOS可視化動態繪製八種排序過程(Swift版)

二、冒泡排序

接下來我們來逐一看一下每種排序的具體效果。下方就是冒泡排序的效果,因為冒泡排序的時間複雜度是O(n^2)的,所以我們先設置元素個數是80, 如果太大的話會比較慢。因為我們在排序步驟結果輸出時,每進行一次交換操作或者比較操作讓排序線程休眠0.001秒,便於我們觀察整個排序過程。

從下方這個動圖上我們不難看出冒泡的整個過程,較小的數據從右往左以此往外冒。下方這個效果還是比較直觀的,整個冒泡過程就是從後往前比較,如果後邊的數要比前邊的小就交換。冒泡過程如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

三、選擇排序

選擇排序的時間複雜度也是O(n^2)。下方是「選擇排序」的可視化過程,選擇排序的過程就是從無序序列中找出最小的那個值放到有序序列中最後方。不斷執行這個過程,我們的序列就是有序的了。下方就是選擇排序的整個過程,元素的個數是80.

iOS可視化動態繪製八種排序過程(Swift版)

四、插入排序

插入排序的複雜度與上述選擇排序的時間複雜度一樣,都是O(n^2)。下方就是插入排序的運行結果。插入排序是從無序序列中取出第一個值,然後插入到前方有序序列中相應的位置。每次插入後,有序序列就會增加1,無序序列就會減少1。下方就是插入排序的過程,如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

五、希爾排序

希爾排序的效率要高一些,其時間複雜度是O(n^(3/2))。下方就是希爾排序的具體執行步驟,希爾排序又稱為縮小增量排序。該排序方式是插入排序的升級版,等增量縮小到1時,我們的序列就是有序的了。下方就是希爾排序的具體執行步驟,如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

六、堆排序

堆排序比希爾排序更為高效,其時間複雜度為O(nlog2n)。下方的「堆排序」是根據大頂堆來進行排序的,大頂堆第一個值是序列中最大的,我們可以利用這一點獲取無序序列中最大的那個值。首先我們將序列調整為大頂堆,然後把大頂堆的第一個值與最後一個值進行交換,然後再將剩下的序列調整成大頂堆,然後進行下一輪的替換。

iOS可視化動態繪製八種排序過程(Swift版)

七、歸併排序

歸併排序的時間複雜度也是O(nlog2n)。歸併排序就是將無序數組拆分成多個只有一個元素的數組,然後進行兩兩合併。在合併的過程中將兩個數組中的元素進行比較,將較小的放在前方,兩個有序的數組合併後依然是有序的,然後再次進行兩兩合併,直到合併成一個數組為止。下方就是歸併排序的執行順序,從執行過程中,我們可以清楚的看到在排序過程中被分割的小的有序序列。歸併排序的執行過程如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

八、快速排序

快速排序的時間複雜度為O(nlog2n)。下方是快速排序的執行步驟,快速排序是利用里分治法的思想。從無序序列中取出一個值,比該值大的放在前方,比該值小的放在後方。然後遞歸執行前半部分和後半部分依次遞歸下去,我們的序列就是有序的了。

iOS可視化動態繪製八種排序過程(Swift版)

九、基數排序

下方是基數排序的運行效果,我們先輸入1000個元素,生成1000個隨機數,選擇基數排序。如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

十、上述排序的比較

關於上述排序的比較,在此就不做過多贅述了,就引用「維基百科」中的表格來說明吧,如下所示:

iOS可視化動態繪製八種排序過程(Swift版)

今天博客中所涉及的Demo依然會在github上進行分享,分享地址如下。

github源碼分享地址: https://github.com/lizelu/DataStruct-Swift/tree/master/AllKindsOfSortForiOS

原文 : CocoaChina

相關閱讀

免责声明:本文内容来源于CocoaChina,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。