如何通過(guò)axure做網(wǎng)站架構(gòu)信息流推廣方式
原創(chuàng)不易,轉(zhuǎn)載請(qǐng)注明出處。歡迎點(diǎn)贊收藏~
計(jì)數(shù)排序(Counting Sort)是一種線性時(shí)間復(fù)雜度的排序算法,其核心思想是通過(guò)統(tǒng)計(jì)待排序元素的個(gè)數(shù)來(lái)確定元素的相對(duì)位置,從而實(shí)現(xiàn)排序。
具體的計(jì)數(shù)排序算法步驟如下:
1. 找出待排序數(shù)組中的最大值,并創(chuàng)建一個(gè)統(tǒng)計(jì)數(shù)組count[],其長(zhǎng)度為最大值加1。
2. 遍歷待排序數(shù)組,統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù),將統(tǒng)計(jì)結(jié)果存儲(chǔ)在count[]數(shù)組中。count[i]表示元素i出現(xiàn)的次數(shù)。
3. 對(duì)count[]數(shù)組進(jìn)行累加,得到每個(gè)元素在排序后的數(shù)組中的最后一個(gè)位置。即count[i]表示小于等于元素i的元素個(gè)數(shù)。
4. 創(chuàng)建一個(gè)臨時(shí)數(shù)組temp[],其長(zhǎng)度與待排序數(shù)組相同。
5. 逆序遍歷待排序數(shù)組,根據(jù)count[]數(shù)組中的記錄,將每個(gè)元素放入temp[]數(shù)組中的正確位置。
6. 將temp[]數(shù)組的元素復(fù)制回待排序數(shù)組,完成排序。
計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(n+k),其中n是待排序數(shù)組的長(zhǎng)度,k是待排序數(shù)組中的最大值。由于需要?jiǎng)?chuàng)建額外的count[]和temp[]數(shù)組,所以空間復(fù)雜度為O(n+k)。
需要注意的是,計(jì)數(shù)排序適用于元素范圍較小且非負(fù)整數(shù)的排序,如果待排序數(shù)組包含負(fù)數(shù)或者小數(shù),則需要進(jìn)行適當(dāng)?shù)霓D(zhuǎn)換或調(diào)整。計(jì)數(shù)排序是穩(wěn)定的排序算法,因?yàn)橄嗤氐南鄬?duì)順序在排序后保持不變,但它不是基于比較的排序算法,因此在某些情況下比其他排序算法更高效。
下面是一個(gè)使用C語(yǔ)言實(shí)現(xiàn)的計(jì)數(shù)排序示例:
#include <stdio.h>void counting_sort(int arr[], int n)
{int max = arr[0];// 找出最大值for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}}// 創(chuàng)建統(tǒng)計(jì)數(shù)組count[],并初始化為0int count[max + 1];for (int i = 0; i <= max; i++){count[i] = 0;}// 統(tǒng)計(jì)每個(gè)元素的次數(shù)for (int i = 0; i < n; i++){count[arr[i]]++;}// 累加count[]數(shù)組,表示小于等于元素i的元素個(gè)數(shù)for (int i = 1; i <= max; i++){count[i] += count[i - 1];}// 創(chuàng)建臨時(shí)數(shù)組temp[],存儲(chǔ)排好序的元素int temp[n];// 根據(jù)count[]數(shù)組中的記錄,將元素放入temp[]數(shù)組的正確位置for (int i = n - 1; i >= 0; i--){temp[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}// 將temp[]數(shù)組的元素復(fù)制回原數(shù)組arr[]for (int i = 0; i < n; i++){arr[i] = temp[i];}
}int main()
{int arr[] = {9, 3, 6, 1, 3, 2, 9, 0};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的數(shù)組:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}counting_sort(arr, n);printf("\n排序后的數(shù)組: \n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}
這段代碼實(shí)現(xiàn)了計(jì)數(shù)排序算法。主要包括以下步驟:
1.遍歷數(shù)組找出最大值,確定統(tǒng)計(jì)數(shù)組count[]的長(zhǎng)度。
2.創(chuàng)建并初始化統(tǒng)計(jì)數(shù)組count[],長(zhǎng)度為最大值加1。
3.遍歷數(shù)組,統(tǒng)計(jì)每個(gè)元素的出現(xiàn)次數(shù),存儲(chǔ)在count[]中。
4.累加count[]數(shù)組,表示小于等于元素i的元素個(gè)數(shù)。
5.創(chuàng)建臨時(shí)數(shù)組temp[],用于存儲(chǔ)排好序的元素。
6.逆序遍歷原數(shù)組,根據(jù)count[]數(shù)組中的記錄,將元素放入temp[]數(shù)組的正確位置。
7.將temp[]數(shù)組的元素復(fù)制回原數(shù)組arr[],完成排序。
運(yùn)行如上代碼,你可以看到以下輸出: