C++ 計數(shù)排序?qū)嵗斀?/h1>
更新時間：2017年07月06日 08:42:20 投稿：lqh
這篇文章主要介紹了C++ 計數(shù)排序?qū)嵗斀獾南嚓P(guān)資料,需要的朋友可以參考下
計數(shù)排序
計數(shù)排序是一種非比較的排序算法
優(yōu)勢：
計數(shù)排序在對于一定范圍內(nèi)的整數(shù)排序時，時間復(fù)雜度為O(N+K) （K為整數(shù)在范圍）快于任何比較排序算法，因為基于比較的排序時間復(fù)雜度在理論上的上下限是O(N*log(N))。
缺點：
計數(shù)排序是一種犧牲空間換取時間的做法，并且當(dāng)K足夠大時O（K）>O(N*log(N)),效率反而不如比較的排序算法。并且只能用于對無符號整形排序。
時間復(fù)雜度：
O（N） K足夠大時為O（K）
空間復(fù)雜度：
O（最大數(shù)-最小數(shù)）
性能：
計數(shù)排序是一種穩(wěn)定排序
代碼實現(xiàn)：
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//計數(shù)排序，適用于無符號整形
void CountSort(int* a, size_t size)
{
assert(a);
size_t max = a[0];
size_t min = a[0];
for (size_t i = 0; i < size; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
size_t range = max - min + 1; //要開辟的數(shù)組范圍
size_t* count = new size_t[range];
memset(count, 0, sizeof(size_t)*range); //初始化為0
//統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)
for (size_t i = 0; i < size; ++i) //從原數(shù)組中取數(shù)，原數(shù)組個數(shù)為size
{
count[a[i]-min]++;
}
//寫回到原數(shù)組
size_t index = 0;
for (size_t i = 0; i < range; ++i) //從開辟的數(shù)組中讀取，開辟的數(shù)組大小為range
{
while (count[i]--)
{
a[index++] = i + min;
}
}
delete[] count;
}
void Print(int* a, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
#include "CountSort.h"
void TestCountSort()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 11, 22, 12, 12 };
size_t size = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, size);
Print(arr, size);
}
int main()
{
TestCountSort();
system("pause");
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
您可能感興趣的文章:
相關(guān)文章
-
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)自行車管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下 2022-08-08
-
這篇文章主要介紹了C++中的雙冒號 ::，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧 2020-09-09
-
C++讀寫鎖是一種多線程同步機制,它允許多個線程同時讀取共享數(shù)據(jù),但只允許一個線程寫入共享數(shù)據(jù),這種鎖可以提高程序的并發(fā)性和性能,本文給大家介紹了C++?實現(xiàn)讀寫鎖的代碼,需要的朋友可以參考下 2023-10-10
-
深入C++中構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值操作符、析構(gòu)函數(shù)的調(diào)用過程總結(jié)
本篇文章是對C++中構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值操作符、析構(gòu)函數(shù)的調(diào)用過程進(jìn)行了總結(jié)與分析，需要的朋友參考下 2013-05-05
-
C++數(shù)據(jù)精度問題(對浮點數(shù)保存指定位小數(shù))
這篇文章主要介紹了對浮點數(shù)保存指定位小數(shù)。比如， 1.123456. 要保存1位小數(shù)，，調(diào)用方法后， 保存的結(jié)果為： 1.1。 再比如，1.98765, 保存2位小數(shù)的結(jié)果為： 2.00,需要的朋友可以參考下 2017-08-08
-
這篇文章主要介紹了C++11新特性std::make_tuple的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2020-10-10
-
嵌入式C實戰(zhàn)項目開發(fā)技巧:對一個有規(guī)律的數(shù)組表進(jìn)行位移操作的方法
今天小編就為大家分享一篇關(guān)于嵌入式C實戰(zhàn)項目開發(fā)技巧:對一個有規(guī)律的數(shù)組表進(jìn)行位移操作的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧 2018-12-12
-
這篇文章主要介紹了利用C++實現(xiàn)的放煙花程序，用到了EGE圖形庫，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下 2023-01-01
-
深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對齊
要求數(shù)據(jù)內(nèi)存的起始地址的值是某個數(shù)k的倍數(shù),這就是所謂的內(nèi)存對齊,本文就來深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對齊,需要的朋友可以參考下 2016-05-05
-
C++實現(xiàn)LeetCode(163.缺失區(qū)間)
這篇文章主要介紹了C++實現(xiàn)LeetCode(163.缺失區(qū)間),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下 2021-07-07
最新評論
計數(shù)排序
計數(shù)排序是一種非比較的排序算法
優(yōu)勢：
計數(shù)排序在對于一定范圍內(nèi)的整數(shù)排序時，時間復(fù)雜度為O(N+K) （K為整數(shù)在范圍）快于任何比較排序算法，因為基于比較的排序時間復(fù)雜度在理論上的上下限是O(N*log(N))。
缺點：
計數(shù)排序是一種犧牲空間換取時間的做法，并且當(dāng)K足夠大時O（K）>O(N*log(N)),效率反而不如比較的排序算法。并且只能用于對無符號整形排序。
時間復(fù)雜度：
O（N） K足夠大時為O（K）
空間復(fù)雜度：
O（最大數(shù)-最小數(shù)）
性能：
計數(shù)排序是一種穩(wěn)定排序
代碼實現(xiàn)：
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//計數(shù)排序，適用于無符號整形
void CountSort(int* a, size_t size)
{
assert(a);
size_t max = a[0];
size_t min = a[0];
for (size_t i = 0; i < size; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
size_t range = max - min + 1; //要開辟的數(shù)組范圍
size_t* count = new size_t[range];
memset(count, 0, sizeof(size_t)*range); //初始化為0
//統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)
for (size_t i = 0; i < size; ++i) //從原數(shù)組中取數(shù)，原數(shù)組個數(shù)為size
{
count[a[i]-min]++;
}
//寫回到原數(shù)組
size_t index = 0;
for (size_t i = 0; i < range; ++i) //從開辟的數(shù)組中讀取，開辟的數(shù)組大小為range
{
while (count[i]--)
{
a[index++] = i + min;
}
}
delete[] count;
}
void Print(int* a, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
#include "CountSort.h"
void TestCountSort()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 11, 22, 12, 12 };
size_t size = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, size);
Print(arr, size);
}
int main()
{
TestCountSort();
system("pause");
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
您可能感興趣的文章:
相關(guān)文章
- 這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)自行車管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
- 這篇文章主要介紹了C++中的雙冒號 ::，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2020-09-09
- C++讀寫鎖是一種多線程同步機制,它允許多個線程同時讀取共享數(shù)據(jù),但只允許一個線程寫入共享數(shù)據(jù),這種鎖可以提高程序的并發(fā)性和性能,本文給大家介紹了C++?實現(xiàn)讀寫鎖的代碼,需要的朋友可以參考下2023-10-10
-
深入C++中構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值操作符、析構(gòu)函數(shù)的調(diào)用過程總結(jié)
本篇文章是對C++中構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值操作符、析構(gòu)函數(shù)的調(diào)用過程進(jìn)行了總結(jié)與分析，需要的朋友參考下2013-05-05 -
C++數(shù)據(jù)精度問題(對浮點數(shù)保存指定位小數(shù))
這篇文章主要介紹了對浮點數(shù)保存指定位小數(shù)。比如， 1.123456. 要保存1位小數(shù)，，調(diào)用方法后， 保存的結(jié)果為： 1.1。 再比如，1.98765, 保存2位小數(shù)的結(jié)果為： 2.00,需要的朋友可以參考下2017-08-08 - 這篇文章主要介紹了C++11新特性std::make_tuple的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
-
嵌入式C實戰(zhàn)項目開發(fā)技巧:對一個有規(guī)律的數(shù)組表進(jìn)行位移操作的方法
今天小編就為大家分享一篇關(guān)于嵌入式C實戰(zhàn)項目開發(fā)技巧:對一個有規(guī)律的數(shù)組表進(jìn)行位移操作的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12 - 這篇文章主要介紹了利用C++實現(xiàn)的放煙花程序，用到了EGE圖形庫，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2023-01-01
-
深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對齊
要求數(shù)據(jù)內(nèi)存的起始地址的值是某個數(shù)k的倍數(shù),這就是所謂的內(nèi)存對齊,本文就來深入剖析C++中的struct結(jié)構(gòu)體字節(jié)對齊,需要的朋友可以參考下2016-05-05 -
C++實現(xiàn)LeetCode(163.缺失區(qū)間)
這篇文章主要介紹了C++實現(xiàn)LeetCode(163.缺失區(qū)間),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07