sort - a920604a/leetcode GitHub Wiki
| Complexity | Best case | Average case | Worst case | Memory space | Stable |
|---|---|---|---|---|---|
| Bubble | O(N) |
O(N^2) |
O(N^2) |
1 | stable |
| Insertion | O(N) |
O(N^2) |
O(N^2) |
1 | stable |
| Selection | O(N^2) |
O(N^2) |
O(N^2) |
1 | non-stable |
| Merge | O(NlogN) |
O(NlogN) |
O(NlogN) |
O(N) |
|
| Quick | O(NlogN) |
O(NlogN) |
O(N^2) |
O(N) or O(logN)
|
non-stable |
| Radix | O(KN) |
||||
| Count | O(N+K) |
O(N+K) |
O(N+K) |
O(N+K) |
|
| Bucket | O(N+K) |
O(N+K) |
O(N^2) |
O(N+K) |
stable |
| Shell | O(NlogN) |
O(N^2)~O(nlog^2 N)
|
1 | non-stable | |
| Heap | O(NlogN) |
O(NlogN) |
O(NlogN) |
1 | non-stable |
Count sort 計算每個鍵值的出現次數，並用額外的陣列保存
// #include <stdlib>
#include <iostream>
#include <vector>
using namespace std;
void swap(int &x, int &y)
{
int tmp = x;
x = y;
y = tmp;
}
// void swap(int *a, int *b)
// {
// int temp = *a;
// *a = *b;
// *b = temp;
// }
void SelectSort(vector<int> &nums)
{
//每輪確保最小值在前面 best case O(n^2) 可以是 stable
for (int i = 0; i < nums.size() - 1; ++i)
{
int min_idx = i;
for (int j = i + 1; j < nums.size(); ++j)
{
if (nums[min_idx] > nums[j])
{
min_idx = j;
}
}
swap(nums[min_idx], nums[i]);
}
}
void InsertSort(vector<int> &nums)
{
// 前i 個元素是已排序過的，插入第i+1 個元素 best case O(n) stable
for (int i = 1; i < nums.size(); ++i)
{
int key = nums[i];
int j = i - 1;
while (j > -1 && nums[j] > key)
{
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
}
void BubbleSort(vector<int> &nums)
{
// 每輪確保最大值在最後 best case O(n) stable
for (int i = 0; i < nums.size(); ++i)
{
for (int j = 0; j < nums.size() - i - 1; j++)
{
if (nums[j + 1] < nums[j])
{
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
int Partition(vector<int> &nums, int l, int r)
{
int pivot = nums[r];
int i = l - 1;
for (int j = l; j < r; j++)
{
if (nums[j] < pivot)
{
i++;
swap(nums[i], nums[j]);
}
}
i++;
swap(nums[r], nums[i]);
return i;
}
void QuickSort(vector<int> &nums, int l, int r)
{
// O(nlogn) avg case, worse case O(n^2)
// internal sortting , in-place
// unstable
// preferred for arrays
// preorder
if (l < r)
{
int pivot = Partition(nums, l, r);
QuickSort(nums, l, pivot - 1);
QuickSort(nums, pivot + 1, r);
}
}
void Merge(vector<int> &nums, int l, int mid, int r)
{
if(l>=r) return;
vector<int> left(nums.begin() + l, nums.begin() + mid+1);
vector<int> right(nums.begin() + mid+1, nums.begin() + r + 1);
int i = 0, j = 0, k = l;
while (i < left.size() && j < right.size())
{
if (left[i] <= right[j])
nums[k++] = left[i++];
else
nums[k++] = right[j++];
}
while (i < left.size())
nums[k++] = left[i++];
while (j < right.size())
nums[k++] = right[j++];
// option 2
// left.push_back(INT_MAX);
// right.push_back(INT_MAX);
// int j=0, k=0;
// for(int i=l ;i<=r ;++i){
// if(left[j]<right[k]) nums[i] = left[j++];
// else nums[i] = right[k++];
// }
}
void MergeSort(vector<int> &nums, int l, int r)
{
// external sort , worse cse and avg case O(nlogn)
// not in place , need eatra space
// stable
// preferred for linked list
if (l < r)
{
int mid = l + (r - l) / 2;
MergeSort(nums, l, mid);
MergeSort(nums, mid + 1, r);
Merge(nums, l, mid, r);
}
}
int main()
{
// void (*f[3])(vector<int> &) = {SelectSort, InsertSort, BubbleSort};
void (*f[1])(vector<int> &) = {SelectSort};
for (int i = 0; i < 1; i++)
{
vector<int> test = {5, 1, 2, 32, 4};
vector<int> test1 = {10, 1, 2, 2, 4};
vector<int> test2 = {5, 4, 3, 2, 1, 0};
for (int i : test1)
cout << i << " ";
cout << endl;
(*f[i])(test1);
for (int i : test1)
cout << i << " ";
cout << endl;
}
void (*fp[1])(vector<int> &, int, int) = {MergeSort};
for (int i = 0; i < 1; ++i)
{
vector<int> test3 = {3, 2, 1, 5, 6, 4};
for (int i : test3)
cout << i << " ";
cout << endl;
(*fp[i])(test3, 0, test3.size() - 1);
for (int i : test3)
cout << i << " ";
cout << endl;
}
return 0;
}