基于計(jì)算機(jī)程序設(shè)計(jì)的排序問(wèn)題分析

王倩

摘要：隨著計(jì)算機(jī)技術(shù)的不斷創(chuàng)新發(fā)展，其在實(shí)際生中的應(yīng)用也非常廣泛。計(jì)算機(jī)程序設(shè)計(jì)是按照機(jī)器邏輯語(yǔ)言的開(kāi)發(fā)規(guī)律實(shí)現(xiàn)不同應(yīng)用功能的渠道之一。在算法體系中，排序問(wèn)題類型多樣化，在實(shí)現(xiàn)排序功能的層面需要程序設(shè)計(jì)語(yǔ)言參與其中。該文主要針對(duì)計(jì)算機(jī)程序設(shè)計(jì)中的經(jīng)典排序算法進(jìn)行深入分析，將相關(guān)排序問(wèn)題與程序設(shè)計(jì)方法之間的內(nèi)在聯(lián)系進(jìn)行探討，提出排序問(wèn)題優(yōu)化的策略。

關(guān)鍵詞：計(jì)算機(jī);程序設(shè)計(jì);排序問(wèn)題

中圖分類號(hào)：TP311? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）21-0067-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

機(jī)器語(yǔ)言是利用最簡(jiǎn)單的二進(jìn)制邏輯進(jìn)行硬件操縱的語(yǔ)言形式，計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言類型較多，有匯編語(yǔ)言、C語(yǔ)言、C++語(yǔ)言、Java語(yǔ)言、C#語(yǔ)言、Python語(yǔ)言等。計(jì)算機(jī)程序設(shè)計(jì)需要遵循基本原則，通過(guò)編譯器實(shí)現(xiàn)某種功能。排序問(wèn)題是算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)體系中研究時(shí)間最久、應(yīng)用最廣泛的算法設(shè)計(jì)項(xiàng)目之一，在計(jì)算機(jī)程序設(shè)計(jì)過(guò)程中，經(jīng)常需要利用排序算法實(shí)現(xiàn)多種功能。

1 計(jì)算機(jī)程序設(shè)計(jì)概述

計(jì)算機(jī)程序設(shè)計(jì)，是計(jì)算機(jī)專業(yè)領(lǐng)域內(nèi)非常基礎(chǔ)的一項(xiàng)技能，是實(shí)現(xiàn)應(yīng)用軟件的核心方式[1]。在調(diào)試與分析計(jì)算機(jī)程序的過(guò)程中，根據(jù)編程語(yǔ)言的不同，設(shè)計(jì)實(shí)現(xiàn)的方式也有很大差異性。在計(jì)算機(jī)程序設(shè)計(jì)體系中，需要熟練掌握思想、算法、數(shù)據(jù)類型、控制語(yǔ)句、函數(shù)、類、模板、結(jié)構(gòu)體共同體、指針、數(shù)據(jù)結(jié)構(gòu)等多維度內(nèi)容，根據(jù)高級(jí)語(yǔ)言之間的差異，有選擇性地進(jìn)行應(yīng)用。計(jì)算機(jī)程序設(shè)計(jì)是一個(gè)較為抽象的概念，但是在學(xué)習(xí)和生活中的應(yīng)用非常廣泛[2]。

在教育行業(yè)中，計(jì)算機(jī)程序設(shè)計(jì)可以實(shí)現(xiàn)多樣化的教學(xué)與操作實(shí)踐內(nèi)容，在互聯(lián)網(wǎng)企業(yè)的日常工作中，可以實(shí)現(xiàn)多種需求的應(yīng)用軟件產(chǎn)品。在互聯(lián)網(wǎng)行業(yè)中，不同高級(jí)程序設(shè)計(jì)語(yǔ)言最終呈現(xiàn)的方式不同，通過(guò)編譯器和解碼器，將不同前端和后端編碼內(nèi)容呈現(xiàn)在應(yīng)用層中[3]。在日常生產(chǎn)生活中，計(jì)算機(jī)程序設(shè)計(jì)需要根據(jù)具體問(wèn)題具體分析，在基礎(chǔ)理論研究的支撐下，應(yīng)用在社會(huì)實(shí)踐過(guò)程中。計(jì)算機(jī)程序設(shè)計(jì)的普遍應(yīng)用方式是封裝在應(yīng)用軟件中，通過(guò)業(yè)務(wù)或者功能流程圖實(shí)現(xiàn)與執(zhí)行自動(dòng)化程序，將不同網(wǎng)絡(luò)開(kāi)發(fā)環(huán)境中的編碼結(jié)果呈現(xiàn)在可視化界面中。在計(jì)算機(jī)程序設(shè)計(jì)相關(guān)原理中，需要對(duì)順序結(jié)構(gòu)、選擇結(jié)構(gòu)以及循環(huán)結(jié)構(gòu)等理論知識(shí)進(jìn)行深度剖析，實(shí)現(xiàn)更多功能和性能需求內(nèi)容[4]。此外，在實(shí)際應(yīng)用中，更多語(yǔ)言都采用面向?qū)ο笠约懊嫦蚍?wù)的設(shè)計(jì)風(fēng)格，也需要用戶使用友好的程序設(shè)計(jì)規(guī)范。

2 經(jīng)典排序算法

2.1 冒泡排序

冒泡排序法是比較常用的排序算法之一，冒泡法最佳情況的時(shí)間復(fù)雜度是[Ο（n）]，最差情況的時(shí)間復(fù)雜度是[Ο（n2）]，普遍應(yīng)用在小規(guī)模數(shù)據(jù)排序、教學(xué)、從高到低列隊(duì)的場(chǎng)景中[5]。小規(guī)模數(shù)據(jù)排序時(shí)，可以手動(dòng)寫(xiě)出數(shù)據(jù)比較的冒泡法排序過(guò)程。此方法的邏輯相對(duì)比較簡(jiǎn)單，在講解for循環(huán)以及分析算法復(fù)雜度時(shí)，可以將此方法作為示例。在算法與數(shù)據(jù)結(jié)構(gòu)教學(xué)過(guò)程中，冒泡法可以使用多種程序設(shè)計(jì)語(yǔ)言進(jìn)行功能實(shí)現(xiàn)。以Java語(yǔ)言為例，將數(shù)組中臨近的數(shù)字兩兩比較，按照升序或者降序的規(guī)律排列，設(shè)置外層和內(nèi)層循環(huán)，用模板函數(shù)類Bubble Sort實(shí)現(xiàn)內(nèi)層冒泡循環(huán)即可完成排序[6]。在不同類型高級(jí)語(yǔ)言中，可以通過(guò)模板類函數(shù)和自定義函數(shù)等多種方式實(shí)現(xiàn)冒泡排序循環(huán)，需要引入for循環(huán)語(yǔ)句，合理設(shè)置排序邏輯和方式。

2.2 拓?fù)渑判?/p>

拓?fù)渑判蚴轻槍?duì)圖和二叉樹(shù)等相關(guān)理論中較為常用的排序方式之一。對(duì)某一個(gè)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判颍枰獙D中所有頂點(diǎn)排成一個(gè)線性序列，將圖中任意一對(duì)頂點(diǎn)，頂點(diǎn)所在的邊屬于無(wú)環(huán)圖，前序頂點(diǎn)在線性序列中在后序頂點(diǎn)之前，按照此類拓?fù)浯涡蛲瓿捎邢驘o(wú)環(huán)圖的線性排序[7]。簡(jiǎn)單地說(shuō)，對(duì)于給定的前后依賴關(guān)系，需要記錄每個(gè)頂點(diǎn)的度，首先尋找度為0的頂點(diǎn)，從圖里刪除，然后按照順序查找度為0的頂點(diǎn)，直到最后圖為空集，這樣的線性排序稱為拓?fù)渑判颉Ｍ負(fù)渑判蚍椒ㄖ饕獞?yīng)用到課程表排序、序列重建、矩陣中的最長(zhǎng)遞增路徑計(jì)算、火星詞典以及項(xiàng)目管理案例中。

以Python程序設(shè)計(jì)語(yǔ)言為例，需要找到所有入度為0的節(jié)點(diǎn)，有向圖不能有環(huán)，有環(huán)則代表節(jié)點(diǎn)有依賴關(guān)系，刪除入度為0的節(jié)點(diǎn)后，會(huì)新增新一批入度為0的節(jié)點(diǎn)，直到有向圖所有節(jié)點(diǎn)遍歷完畢。因此在程序設(shè)計(jì)時(shí)，需要規(guī)定節(jié)點(diǎn)值、入度、出度、鄰居節(jié)點(diǎn)、邊的集合、邊的權(quán)重、邊來(lái)源與去向的節(jié)點(diǎn)、圖節(jié)點(diǎn)集合以及字典、圖邊集合等變量項(xiàng)[8]。拓?fù)渑判虻某绦蛟O(shè)計(jì)，需要先統(tǒng)計(jì)當(dāng)前所有節(jié)點(diǎn)的入度，將入度為0的節(jié)點(diǎn)排到隊(duì)列中，再將入度為0的節(jié)點(diǎn)加入列表中，消除影響后，將后續(xù)節(jié)點(diǎn)的入度減一，循環(huán)一直到有向圖的所有節(jié)點(diǎn)都遍歷完畢才結(jié)束。

2.3 快速排序

快速排序是應(yīng)用最廣泛的排序算法之一，是體現(xiàn)分治思想的重要手段。在快排法中，需要將一個(gè)數(shù)組分成前半部分和后半部分，要求前半部分的數(shù)值大于或者小于后半部分的數(shù)值，然后調(diào)用遞歸函數(shù)，再次分治，最終達(dá)到前半部分和后半部分內(nèi)的數(shù)值達(dá)到升序或者降序目標(biāo)。快排法的時(shí)間復(fù)雜度最佳情況是[Ο（NlogN）]，最壞情況的時(shí)間復(fù)雜度是[Ο（N*N）]，并且此種方法為原址排序，不需要設(shè)置額外的內(nèi)存空間，但是不屬于穩(wěn)定排序方法，在數(shù)據(jù)交換過(guò)程中會(huì)破壞穩(wěn)定性[9]。以C++程序設(shè)計(jì)為例，可以將數(shù)組長(zhǎng)度作為參數(shù)，或者將數(shù)組的下標(biāo)區(qū)間作為參數(shù)進(jìn)行數(shù)據(jù)交換。在程序編寫(xiě)時(shí)，可以將支點(diǎn)選擇為序列的第一個(gè)元素，分別定義從左到右移動(dòng)的索引以及從右到左移動(dòng)的索引變量，將位于左側(cè)不小于支點(diǎn)的元素和位于右側(cè)不大于支點(diǎn)的元素進(jìn)行交換，然后對(duì)左側(cè)的數(shù)據(jù)進(jìn)行內(nèi)部快排，對(duì)右側(cè)的數(shù)據(jù)進(jìn)行內(nèi)部快排，直到最終找到最大值，結(jié)束查找和排序。