詳解計(jì)數(shù)排序算法及C語言程序中的實(shí)現(xiàn)

更新時(shí)間：2016年07月06日 15:51:18 作者：zhoutk

技術(shù)排序算法與我們普通接觸的冒泡排序和快速排序等基于元素比較的算法不同,在編程中通過C語言的數(shù)組能夠清除地表達(dá)出來,這里我們就來詳解計(jì)數(shù)排序算法及C語言程序中的實(shí)現(xiàn)

關(guān)于計(jì)數(shù)排序算法

當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量?jī)?nèi)存。計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。

算法的步驟如下：

找出待排序的數(shù)組中最大和最小的元素
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

代碼示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
  int *C=new int[K+1];
  int i;
  memset(C,0,sizeof(int)*(K+1));
  for (i=1;i<=N;i++) //把A中的每個(gè)元素分配
    C[A[i]]++;
  for (i=2;i<=K;i++) //統(tǒng)計(jì)不大于i的元素的個(gè)數(shù)
    C[i]+=C[i-1];
  for (i=N;i>=1;i--)
  {
    B[C[A[i]]]=A[i]; //按照統(tǒng)計(jì)的位置，將值輸出到B中，將順序輸出到Order中
    Order[C[A[i]]]=i;
    C[A[i]]--;
  }
}
int main()
{
  int *A,*B,*Order,N=15,K=10,i;
  A=new int[N+1];
  B=new int[N+1];
  Order=new int[N+1];
  for (i=1;i<=N;i++)
    A[i]=rand()%K+1; //生成1..K的隨機(jī)數(shù)
  printf("Before CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",A[i]);
  CountingSort(A,B,Order,N,K);
  printf("\nAfter CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",B[i]);
  printf("\nOrder:\n");
  for (i=1;i<=N;i++)
    printf("%d ",Order[i]);
  return 0;
}

您可能感興趣的文章:

相關(guān)文章

教你5分鐘輕松搞定內(nèi)存字節(jié)對(duì)齊
隨便google一下,人家就可以跟你解釋的,一大堆的道理,我們沒怎么多時(shí)間,討論為何要對(duì)齊.直入主題,怎么判斷內(nèi)存對(duì)齊規(guī)則,sizeof的結(jié)果怎么來的,請(qǐng)牢記以下3條原則
2013-09-09
最新C語言自定義類型詳解
生活當(dāng)中有很多物品是不能簡(jiǎn)單的用整型、浮點(diǎn)型、字符型來區(qū)分，它們常常是復(fù)雜的集合，比如人，一個(gè)人擁有年齡，身高、體重、學(xué)歷......等信息，我們可以用結(jié)構(gòu)體來實(shí)現(xiàn)準(zhǔn)確描述人這種復(fù)雜集合，這篇文章主要介紹了C語言?自定義類型,需要的朋友可以參考下
2023-01-01
C語言單鏈表實(shí)現(xiàn)方法詳解
這篇文章主要介紹了C語言單鏈表實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了基于C語言的單鏈表定義、創(chuàng)建、添加、刪除、排序、打印等操作技巧,并附帶了相關(guān)的優(yōu)化算法,需要的朋友可以參考下
2018-04-04
C++中漢字字符串的截取
C++中漢字字符串的截取，需要的朋友可以參考一下
2013-05-05
C++輸入流和輸出流超級(jí)詳細(xì)
C++ 的開發(fā)者認(rèn)為數(shù)據(jù)輸入和輸出的過程也是數(shù)據(jù)傳輸?shù)倪^程，數(shù)據(jù)像水一樣從一個(gè)地方流動(dòng)到另一個(gè)地方，所以 C++ 中將此過程稱為“流”，實(shí)現(xiàn)此過程的類稱為“流類”。下面小編將詳細(xì)介紹這個(gè)話題,需要的朋友可以參考一下
2021-09-09
Qt編寫地圖實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)軌跡效果
實(shí)時(shí)動(dòng)態(tài)軌跡主要是需要在地圖上動(dòng)態(tài)顯示GPS的運(yùn)動(dòng)軌跡，也是編寫地圖時(shí)一個(gè)重要的功能。本文將利用Qt實(shí)現(xiàn)這一功能，需要的可以參考一下
2022-02-02
C++ 智能指針深入解析
以下是對(duì)C++中智能指針的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下
2013-07-07
C++設(shè)計(jì)模式之觀察者模式
這篇文章主要介紹了C++設(shè)計(jì)模式之觀察者模式,本文講解了什么是觀察者模式、觀察者模式的UML類圖、觀察者模式的使用場(chǎng)合等內(nèi)容,需要的朋友可以參考下
2014-10-10
Qt+OpenCV利用幀差法實(shí)現(xiàn)車輛識(shí)別
所謂幀差法也就是對(duì)連續(xù)圖像幀做差分運(yùn)算，其結(jié)果與定義好的閾值比較，若大于閾值則為運(yùn)動(dòng)目標(biāo)值為1，否則值為0?。本文將利用幀差法實(shí)現(xiàn)車輛識(shí)別，感興趣的可以了解一下
2022-08-08
Qt實(shí)現(xiàn)自定義矩陣布局
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)自定義矩陣布局，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-08-08