資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究抽屜排序
這是一個非比較排序技術的示例。它用於專案數量和可能金鑰值範圍大約相同的情況。
為了執行此排序，我們需要建立一些抽屜。所需的抽屜數量由數字範圍決定。專案會插入到每個抽屜中。最後從抽屜中刪除，並存儲到已排序順序的陣列中。
抽屜排序技術的複雜性
- 時間複雜度：O(n+2^k)
- 空間複雜度：O(2^k)
輸入和輸出
Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output: Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932
演算法
pigeonHoleSort(array, size)
輸入 − 一個數據陣列，以及陣列中的總數
輸出 − 已排序的陣列
Begin find max and min from the array list holeRange := max – min +1 define holeRange number of Lists for i := 0 to n-1 do hole[array[i]-min].append(array[i]) done count := 0 for j := 0 to holeRange-1 do while hole[j] is not empty do array[count] := get first node of hole[j] and delete it count := count +1 done done End
示例
#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
maximum = minimum = arr[0]; //initially max and min ar arr[0]
for(int i = 1; i<n; i++) {
if(arr[i] > maximum)
maximum = arr[i]; //get maximum data
if(arr[i] < minimum)
minimum = arr[i]; //get minimum data
}
}
void pegionHoleSort(int *arr, int n) {
int max, min;
getMaxMin(arr, n, max, min);
int holeRange = max - min +1;
list<int> hole[holeRange]; //create an array of holes
for(int i = 0; i<n; i++) {
hole[arr[i]-min].push_back(arr[i]);
}
int count = 0;
for(int j = 0; j<holeRange; j++) {
//delete from linked lists and store to array
while(!hole[j].empty()) {
arr[count] = *(hole[j].begin());
hole[j].erase(hole[j].begin());
count++;
}
}
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
pegionHoleSort(arr, n);
cout << "Data after Sorting: ";
display(arr, n);
}輸出
Enter the number of elements: 10 Enter elements: 802 630 20 745 52 300 612 932 78 187 Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932
更新日期：15-06-2020
827 次瀏覽
廣告