資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式實現對小於100個數進行O(n)複雜度的排序
為了線上性時間內對一些小數字進行排序，我們可以使用計數排序技術。
計數排序是一種穩定的排序技術，用於根據作為小數字的鍵對物件進行排序。它計算鍵值相同的鍵的數量。當不同鍵之間的差異不大時，這種排序技術效率很高，否則它可能會增加空間複雜度。
計數排序技術的複雜度
時間複雜度：O(n + r)
空間複雜度：O(n + r)
Input − A list of unsorted data: 2 5 6 2 3 10 3 6 7 8 Output − Array after Sorting: 2 2 3 3 5 6 6 7 8 10
演算法
countingSort(陣列, 大小)
輸入 - 資料陣列，以及陣列中的總數
輸出 - 排序後的陣列
Begin max = get maximum element from array. define count array of size [max+1] for i := 0 to max do count[i] = 0 //set all elements in the count array to 0 done for i := 1 to size do increase count of each number which have found in the array done for i := 1 to max do count[i] = count[i] + count[i + 1] //find cumulative frequency done for i := size to 1 decrease by 1 do store the number in the output array decrease count[i] done return the output array End
示例程式碼
#include <iostream>
using namespace std;
void counting_sort(int array[], int n) {
int i, j;
int count[n];
for (i = 0; i < n; i++)
count[i] = 0;
for (i = 0; i < n; i++)
(count[array[i]])++;
for (i = 0, j = 0; i < n; i++)
for (; count[i] > 0; (count[i])--)
array[j++] = i;
}
int main() {
int array[100], i, num;
cout << "Enter the size of array : ";
cin >> num;
cout << "Enter the " << num << " elements to be sorted:" << endl;
for (i = 0; i < num; i++)
cin >> array[i];
cout << "\nThe array of elements before sorting : " <<endl;
for (i = 0; i < num; i++)
cout << array[i] << " ";
cout << "\nThe array of elements after sorting : " << endl;
counting_sort(array, num);
for (i = 0; i < num; i++)
cout << array[i] << " ";
return 0;
}輸出
Enter the size of array : 8 Enter the 8 elements to be sorted: 54 89 23 20 18 88 65 31 The array of elements before sorting : 54 89 23 20 18 88 65 31 The array of elements after sorting : 54 89 23 20 18 88 65 31
更新於: 2019年7月30日
259 次瀏覽
廣告