C++ 計數排序算法的實作與改進(含筆試面試題)

      計數排序局限性比較大，算法思想：假定輸入是有一個小範圍内的整數構成的（比如年齡等），利用額外的數組去記錄元素應該排列的位置，思想比較簡單。

      計數排序是典型的不是基于比較的排序算法，基于比較的排序算法最少也要O(nlogn)，有沒有可能創造線性時間的排序算法呢？那就是不基于比較的排序算法；

      如果數組的資料範圍為0~100，則很适合此算法。計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等于i的元素的個數。然後根據數組C來将A中的元素排到正确的位置。它隻能對整數進行排序

算法步驟：

1、找出待排序的數組中最大和最小的元素

2、統計數組中每個值為i的元素出現的次數，存入數組C的第i項

3、對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

4、反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1

實作代碼：

/***************************************************************************
 *  @file       main.cpp
 *  @author     MISAYAONE
 *  @date       27  March 2017
 *  @remark     27  March 2017 
 *  @theme      Counting Sort 
 ***************************************************************************/

#include <iostream>
#include <vector>
#include <time.h>
#include <Windows.h>
using namespace std;

void Counting_sort(int a[], size_t n, int k)
{
	//申請額外空間
	int *p = new int[n];
	int *q = new int[k+1];
	for (int i = 0; i < k; ++i)
	{
		q[i] = 0;//将q指向的數組所有元素置0
	}

	//儲存數組a中每個元素出現的個數，将排序交給了q數組(其順序在q數組中就是有序的)
	
	for (int j = 0; j < n; ++j)
	{
		q[a[j]]++ ;
	}
		

	//将所有計數次數累加
	for (int i = 1; i < k; ++i)
	{
		q[i] = q[i] + q[i-1];
	}


	//将元素重新輸入
	for (int i = n-1; i >= 0; --i)
	{
		//次數大小最小為1、數組開始為0
		p[q[a[i]]-1] = a[i];
		q[a[i]]--;
	}

	for (int j = 0; j < n; ++j)
	{
		a[j] = p[j];
	}
	//不要忘了釋放配置設定的空間
	delete []p;
	delete []q;
}

int main(int argc, char **argv)
{
	int a[10] = {2,56,4,2,9,56,3,59,9,16};
	int max = a[0];
	for (int i = 1;i < 10; ++i)
	{
		if (a[i]>max)
		{
			max = a[i];
		}
	}

	Counting_sort(a,10,max+1);//傳入max+1是為了讓計數的數組從0開始足夠大
	for (int i = 0; i < 10; ++i)
	{
		cout<<a[i]<<" ";
	}
	cin.get();
	return 0;
}
           

複雜度分析：

在一定限制下時間複雜度為O(n)，額外空間O(n)（需要兩個數組）

O(n+k), n為原數組長度，k為資料範圍

特點：穩定排序stable_sort，out_place排序

例題1、某地區年齡排序問題？

夠典型的計數排序吧，年齡的區間也就那麼大，代碼就不上了，請參照上述參照計數排序算法。