數據結構-歸并排序+計數排序

1.歸并排序

基本思想:
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。 歸并排序核心步驟:

相當于每次把待排數據分為兩個子區間,如果每個子區間有序,再讓兩個子區間歸并起來也有序,那整體就有序了。我們可以按照二叉樹的思想,把子區間再分為兩份,使子區間的子區間有序.......直到子區間分無可分為止。

具體過程如下:

那該如何讓兩個有序子區間歸并呢?

直接在數組中肯定不行,這樣會發生數據的覆蓋。所以我們可以像之前合并兩個有序數組一樣,另外開辟一個空間tmp,依次比較兩個有序子區間的值,每次比較后把較小的放在tmp中,如果其中一個子區間提前結束,就把另外一個子區間的剩余的數據全放進tmp,最后把tmp中的數據拷貝回原數組。

使用遞歸實現:

#include<stdio.h>
#include<stdlib.h>
void _MegeSort(int* a, int begin, int end,int*tmp)
{//只剩一個數據,遞歸結束if (begin == end){return;}int mid = (begin + end) / 2;//遞歸子區間,分為兩部分_MegeSort(a, begin, mid, tmp);_MegeSort(a, mid+1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int j = begin;//兩部分比較,每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余,全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷貝到原數組memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MegeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MegeSort(a, 0, n - 1, tmp);free(tmp);
}void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ",a[i]);}printf("\n");
}
int main()
{int a[] = { 1,4,9,6,3,5,2,8,10,7,11,1};MegeSort(a, sizeof(a) / sizeof(int));Print(a, sizeof(a) / sizeof(int));return 0;
}

注意:

1.?因為每次遞歸的子區間都不一定是從0開始的,所以我們拷貝數據時,最好從begin的位置開始:

//拷貝到原數組
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

2. 在代碼中j作為tmp的坐標,每次往tmp中放入數據后都要加一,但不能初始化為0,否則每次遞歸進入,j的值都會清0,所以最好初始化:j=begin

歸并排序的復雜度:

時間復雜度O(N*logN)

歸并排序每次遞歸都要把待排數據分為兩份,相當于二分法,那一共有logN層遞歸,而每次遞歸都要比較數據,要把每個數據都遍歷一遍,每層的時間復雜度就是O(N),所以總共的時間復雜度是O(N*logN)。

空間復雜度:O(N)?

剛開始就開辟了空間,此時就已經是O(N)了,而遞歸過程中函數棧幀的創建是logN,所以總的空間復雜度是:O(N+logN),但是量級沒變,還是O(N)。

2.非遞歸實現歸并排序

非遞歸實現歸并排序,我們只需模擬上述的遞歸過程即可,把遞歸過程轉換為:把數據先分為2個一組,全部歸并一遍,拷貝回原數組,然后4個一組,全部歸并一遍,拷貝回原數組,再8個一組,?全部歸并一遍,拷貝回原數組,

那我們就可以設置一個gap,兩個數據為一組時,gap=1,每歸并一組數據就往后跳2*gap步,直到全部歸并一遍,再次分組,這次gap=2,每歸并一組數據往后跳2*gap步,直到全部歸并一遍,下次gap=4,跳2*gap步.....,直到gap>n就停止,

代碼如下:

void MegeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//兩部分比較,每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余,全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}

測試一下:

上面結果看起來,我們排序成功了,但是上述代碼真的對嗎?

上面代碼我們在測試時用的是8個數據,但是如果用9個、10個等,就會發現排序并不會成功,可能程序還會崩掉,這是為什么呢?

因為我們在分組時,是按照固定的2的次方分的,一旦數據個數不是2、4、8的次方,后面歸并時就會發生越界問題。

下面我們給10個數據打印一下邊界,會發現,有三種越界的方式,:

那我們對這三種情況分別做一下處理:

第1、2種情況出現時,我們直接break,第三種情況,我們修改邊界,令end2=n-1,但是注意直接break后,第1、2種情況往tmp中歸并時會少一部分數據(如上圖藍框所示),所以最后把tmp的數據往a中拷貝時,不能一次性全部拷貝回去,否則a中這些數據就永遠丟失了,所以最好歸并一段,拷貝一段,這樣拷貝過去的數據只會把前面的數據覆蓋,沒參與歸并的數據還在a中。

代碼如下:

void MegeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}//修正if (end2 >= n){end2 = n - 1;}//兩部分比較,每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余,全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//歸并一段,拷貝一段memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);
}

3.計數排序

基本思想:

1. 統計每個數據出現的次數。

2. 根據數據的次數排序。?

如果我們要排序的數在0~9之間,我們可以像上面一樣開辟10個int大小的空間,統計待排數據中每個數據的個數,在開辟出的數組的相應下標處計數,那如果我們要排序的數據在100~109之間呢?難道開辟110個空間嗎?

當然不是,我們可以做相對映射,在開辟空間之前,先找到待排數據中的最小值和最大值,開辟空間的大小就是:sizeof(int)*(max-min+1),開辟出的數組下標應該是:0~9,0~9下標的位置分別對應的是100~109,計數時,在下標為該數據減待排數據中的最小值的位置統計次數,例如:109就在109-100=9的下標處統計次數,統計完排序的時候再加上最小值即可。

代碼如下:

#include<stdio.h>
#include<stdlib.h>
void CountSort(int* a, int n)
{int min = a[0], max = a[0];//找最大值和最小值for (int i = 0; i < n; i++){if (a[i] < a[0]){min = a[i];}if (a[i] > a[0]){max = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);memset(count, 0, sizeof(int) * range);//計數for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int k = 0;for (int j = 0; j < range; j++){while (count[j]--){a[k++] = j + min;}}
}
//打印函數
Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{int a[] = { 6,1,6,7,9,6,4,5,6,1 };CountSort(a, sizeof(a) / sizeof(int));Print(a, sizeof(a) / sizeof(int));return 0;
}

計數排序的復雜度:

時間復雜度:O(N+range)

尋找最大值和最小值時,遍歷一遍數組,時間復雜度是:O(N),由于待排數據的范圍是range,排序時所耗費的時間復雜度是:O(range),所以最終的時間復雜度是:O(N+range)

如果知道N和range的大小,N大,就是O(N),range大,就是O(range)

空間復雜度:O(range)

額外開辟的空間個數是range,所以空間復雜度就是:O(range)

4.排序的復雜度和穩定性

總結如下:

?以上就是排序學習的全部內容了,到這,數據結構的學習就告一段落了,近期會停更一段時間,用來復習,后面將繼續學習C++的知識,

未完待續。。。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/167446.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/167446.shtml
英文地址,請注明出處:http://en.pswp.cn/news/167446.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

2023年P氣瓶充裝證模擬考試題庫及P氣瓶充裝理論考試試題

題庫來源&#xff1a;安全生產模擬考試一點通公眾號小程序 2023年P氣瓶充裝證模擬考試題庫及P氣瓶充裝理論考試試題是由安全生產模擬考試一點通提供&#xff0c;P氣瓶充裝證模擬考試題庫是根據P氣瓶充裝最新版教材&#xff0c;P氣瓶充裝大綱整理而成&#xff08;含2023年P氣瓶…

pulseaudio是如何測試出音頻延遲的

通常專業的音頻設備生產廠商都有專業的設備來測試精確的音頻鏈路延時。 那么沒有專業設備怎么測試出音頻延遲呢?如下圖,我們可以看到pulseaudio可以測試出硬件音頻延遲。 那么,他是怎么測試出硬件延遲的呢?他的理論依據是什么呢?接下來我帶大伙一起探索一下。 /*占位…

紅隊攻防實戰之從邊界突破到漫游內網(無cs和msf)

也許有一天我們再相逢&#xff0c;睜大眼睛看清楚&#xff0c;我才是英雄。 本文首發于先知社區&#xff0c;原創作者即是本人 本篇文章目錄 網絡拓撲圖&#xff1a; 本次紅隊攻防實戰所需繪制的拓撲圖如下&#xff1a; 邊界突破 訪問網站&#xff1a; http://xxx.xxx.xxx…

leetcode刷題記錄——1991. 找到數組的中間位置

找到數組的中間位置 給你一個下標從 0 開始的整數數組 nums &#xff0c;請你找到 最左邊 的中間位置 middleIndex &#xff08;也就是所有可能中間位置下標最小的一個&#xff09;。 中間位置 middleIndex 是滿足 nums[0] nums[1] … nums[middleIndex-1] nums[middleInd…

數據傳輸的思考

Wi-Fi&#xff1a;Wi-Fi是一種無線網絡技術&#xff0c;可以用于無線互聯網接入、局域網通信和數據傳輸等。Wi-Fi基于IEEE 802.11標準&#xff0c;通過無線信號傳輸數據&#xff0c;提供高速的無線網絡連接。Wi-Fi可用于連接設備與路由器或者設備之間的直接通信&#xff0c;可以…

Linux 排查必看文件

目錄 1. 登錄日志 1.1 /var/log/wtmp 1.2 /var/log/btmp.* 1.3 /var/log/lastlog 1.4 /var/log/faillog 1.5 /var/log/secure 1.6 /var/log/auth.log 2. 系統日志 2.1 /var/log/cron.* 2.2 /var/log/syslog 2.3 /var/log/audit/audit.*log 3. 歷史命令 3.1 ~/…

Docker 中OpenResty下載與使用

1Panel安裝OpenResty 查看到就說明安裝成功 部署項目 在http中添加&#xff1a; server { listen 8001; //端口號 server_name localhost; location / { root /admin; //項目路徑 index index.html index.htm; …

Java二級醫院區域HIS信息管理系統源碼(SaaS服務)

一個好的HIS系統&#xff0c;要具有開放性&#xff0c;便于擴展升級&#xff0c;增加新的功能模塊&#xff0c;支撐好醫院的業務的拓展&#xff0c;而且可以反過來給醫院賦能&#xff0c;最終向更多的患者提供更好的服務。 系統采用前后端分離架構&#xff0c;前端由Angular、J…

P1028 [NOIP2001 普及組] 數的計算

時刻記住一句話&#xff1a;寫遞歸&#xff0c;1畫圖&#xff0c;2大腦放空&#xff01;&#xff01;&#xff01; 意思是&#xff0c;自己寫遞歸題目&#xff0c;先用樣例給的數據畫圖&#xff0c;然后想一個超級簡單的思路&#xff0c;直接套上去就可以了。 上題干&#xff…

牛客 HJ106 字符逆序 golang實現

牛客題目算法連接 題目 golang 實現 package mainimport ("fmt""bufio""os" )func main() {str, _ : bufio.NewReader(os.Stdin).ReadString(\n)if len(str) 0 {return } else {newstr:""strLen:len(str)-1for i:strLen;i>0;i-…

生產環境出現問題,測試人如何做工作復盤?

很多時候我們能把大部分的Bug或一些部署等問題在業務上線之前就解決了&#xff0c;但由于某些因素&#xff0c;線上問題還是時而出現&#xff0c;影響業務生產甚至是公司效益。 避免線上問題的發生以及線上問題及時處理是測試人員的一項重要職責&#xff0c;如何快速地處理&am…

XG916Ⅱ輪式裝載機后驅動橋設計機械設計CAD

wx供重浩&#xff1a;創享日記 對話框發送&#xff1a;裝載機 獲取完整論文報告工程源文件 本次設計內容為XG916Ⅱ裝載機后驅動橋設計&#xff0c;大致上分為主傳動的設計&#xff0c;差速器的設計&#xff0c;半軸的設計&#xff0c;最終傳動的設計四大部分。其中主傳動錐齒輪…

【多線程】Thread類的使用

目錄 1.概述 2.Thread的常見構造方法 3.Thread的幾個常見屬性 4.啟動一個線程-start() 5.中斷一個線程 5.1通過共享的標記來進行溝通 5.2 調用 interrupt() 方法來通知 6.等待一個進程 7.獲取當前線程引用 8.線程的狀態 8.1所有狀態 8.2線程狀態和轉移的意義 1.概述 …

Relabel與Metic Relabel

Prometheus支持多種方式的自動發現目標&#xff08;targets&#xff09;&#xff0c;以下是一些常見的自動發現方式&#xff1a; 靜態配置&#xff1a;您可以在Prometheus配置文件中直接列出要監測的目標。這種方式適用于目標相對穩定的情況下&#xff0c;例如固定的服務器或設…

HCIA-RS基礎:動態路由協議基礎

摘要&#xff1a;本文介紹動態路由協議的基本概念&#xff0c;為后續動態路由協議原理課程提供基礎和引入。主要講解常見的動態路由協議、動態路由協議的分類&#xff0c;以及路由協議的功能和自治系統的概念。文章旨在優化標題吸引力&#xff0c;并通過詳細的內容夯實讀者對動…

自求導的方法實現線性回歸算法

線性回歸是一種常用的回歸算法&#xff0c;用于建立輸入變量和連續輸出變量之間的關系。傳統的線性回歸算法通常依賴于繁瑣的數學推導和梯度計算。但是&#xff0c;隨著深度學習的興起&#xff0c;自求導的方法逐漸成為實現線性回歸算法的有效途徑。本文將介紹如何使用自求導的…

視頻網站適合租用服務器嗎?

視頻網站適合租用服務器嗎&#xff1f; 談到服務器租用&#xff0c;在服務器租用市場中&#xff0c;通常比較常見的用戶群體有電商、外貿和視頻等網站。在這里相信很多用戶都有疑問&#xff1a;租用的服務器適不適合用來建立視頻網站呢&#xff1f;接下來我們一起來看看吧~ 首…

VMware安裝windows操作系統

一、下載鏡像包 地址&#xff1a;鏡像包地址。 找到需要的版本下載鏡像包。 二、安裝 打開VMware新建虛擬機&#xff0c;選擇用鏡像文件。將下載的鏡像包加載進去即可。

python opencv 邊緣檢測(sobel、沙爾算子、拉普拉斯算子、Canny)

python opencv 邊緣檢測&#xff08;sobel、沙爾算子、拉普拉斯算子、Canny&#xff09; 這次實驗&#xff0c;我們分別使用opencv 的 sobel算子、沙爾算子、拉普拉斯算子三種算子取進行邊緣檢測&#xff0c;然后后面又使用了Canny算法進行邊緣檢測。 直接看代碼&#xff0c;代…

論文導讀 | 10月專題內容精選:人的預測

編者按 本次論文導讀&#xff0c;編者選擇了10月份OR和MS上與"人的預測"有關的三篇文章&#xff0c;分別涉及群體智慧的提取&#xff0c;個體序列預測的評估&#xff0c;以及決策者對風險的扭曲感知在分布式魯棒優化中的應用。其中&#xff0c;從基于"生成式可能…