[学習アルゴリズム]実戦アルゴリズム15強-ソート2

私がバーク金督がアップロードした「実戦アルゴリズム」のビデオを見て勉強した過程を記録します.
すべての写真は巴金督のブログから持ってきたものです.
https://blog.encrypted.gg/

Counting Sort

時間複雑度はO(n)であり,数範囲が限られている場合,sortをカウントすることによって実現できる.

#include <bits/stdc++.h>
using namespace std;

int arr[2000002];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, num;
	cin >> n;
	
	for(int i = 0; i < n; ++i)
	{
		cin >> num;
		arr[num + 1000000]++;
	}

	for (int i = 0; i < 2000002; ++i)
	{
		while(arr[i]--) 
			cout << i - 1000000 << ' ';
	}
}

Radix Sort

1位置比較...10桁の比較...100桁の比較...10^n-1ビット比較..ソート方法
時間複雑度O(n)

merge, quick, bubble vs counting radix

Comparison Sort vs Non-comparision Sort

Comparison Sort merge、quick、bubbleは、要素間でサイズを比較するプロセスです.
非比較ソフトウェアカウント、基数比較プロセスなし

STL sort

STL sortはquick sortに基づいており,最悪の場合でもO(nlogn)を保証できる.

vector<int> a = {1, 5, 4, 3, 2};
sort(a.begin(), a.end()); 

同じ優先度を持つ要素を既存の順序でソートする場合はstable sortを使用します.