0、算法分类
-
十种常见排序算法可以分为两类
- 比较类排序 通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)
- 非比较类排序 不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行
-
名次解释：
时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
-
n：待排序列的个数。
-
k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
-
In-place：原地算法，指的是占用常用内存，不占用额外内存。空间复杂度为 O(1) 的都可以认为是原地算法。
-
Out-place：非原地算法，占用额外内存。
-
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。
-
1、冒泡排序
#include <iostream>
#include <vector>
using std::vector;
void bubbleSort(vector<int>&&arr)
{
int n = arr.size();
bool flag = false;
for (int i = 0; i < n - 1; ++i)
{
flag = false;
for (int j = 0; j < n - i - 1; ++j)
{
if(arr[j] > arr[j+1])
{
std::swap(arr[j], arr[j+1]);
flag = true;
}
}
if(!flag) break;
}
for(auto&& x : arr)
{
std::cout<< x <<",";
}
std::cout<<std::endl;
}
int main ()
{
bubbleSort(vector<int>{1,2,3,4,5});
bubbleSort(vector<int>{1,3,2,4,5});
bubbleSort(vector<int>{5,4,3,2,1});
bubbleSort(vector<int>{1,5,2,4,3});
}
2、选择排序
#include <iostream>
#include <vector>
using std::vector;
void selectSort(vector<int>&& arr)
{
int n = arr.size();
int minIndex = 0;
for (int i = 0; i < n-1; ++i)
{
minIndex = i;
for (int j = i + 1; j < n; ++j)
if(arr[j] < arr[minIndex]) minIndex = j;
z
if(minIndex != i) std::swap(arr[i], arr[minIndex]);
}
for(auto&& x : arr)
{
std::cout<< x <<",";
}
std::cout<<std::endl;
}
int main ()
{
selectSort(vector<int>{1,2,3,4,5});
selectSort(vector<int>{1,3,2,4,5});
selectSort(vector<int>{5,4,3,2,1});
selectSort(vector<int>{1,5,2,4,3});
}
3、插入排序
#include <iostream>
#include <vector>
using std::vector;
void insertSort(vector<int> arr)
{
int n = arr.size();
int i, j, temp;
for (i = 1; i < n; ++i)
{
temp = arr[i];
for (j = i; j > 0 && arr[j - 1] > temp; --j)
arr[j] = arr[j - 1];
arr[j] = temp;
}
for(auto&& x : arr)
{
std::cout<< x <<",";
}
std::cout<<std::endl;
}
int main ()
{
insertSort(vector<int>{1,2,3,4,5});
insertSort(vector<int>{1,3,2,4,5});
insertSort(vector<int>{5,4,3,2,1});
insertSort(vector<int>{1,5,2,4,3});
}
4.希尔排序
#include <iostream>
#include <vector>
using std::vector;
void shellSort(vector<int> arr)
{
int n = arr.size();
int i, j , gap, temp;
for(gap = n / 2; gap > 0; gap/=2)
{
for (i = gap; i< n; ++i)
{
temp = arr[i];
for (j = i - gap; j>=0 && temp < arr[j]; j-=gap)
{
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
for(auto&& x : arr)
{
std::cout<< x <<",";
}
std::cout<<std::endl;
}
int main ()
{
shellSort(vector<int>{1,2,3,4,5});
shellSort(vector<int>{1,3,2,4,5});
shellSort(vector<int>{5,4,3,2,1});
shellSort(vector<int>{1,5,2,4,3});
}
5、归并排序
#include <iostream>
#include <vector>
using std::vector;
void merge(vector<int>& arr, int l, int r, int mid)
{
int leftSize = mid - l + 1;
int rightSize = r - mid;
vector<int> left(arr.begin() + l, arr.begin() + mid + 1);
vector<int> right(arr.begin() + mid + 1, arr.begin() + r + 1);
int i =0, j = 0, k = l;
while (i<leftSize && j<rightSize) arr[k++] = left[i] < right[j] ? left[i++] : right[j++];
while (i<leftSize ) arr[k++] = left[i++];
while (j<rightSize ) arr[k++] = right[j++];
}
void mergeSort(vector<int>&arr, int l, int r)
{
if(l == r) return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l , r, mid);
}
void print(vector<int>& arr)
{
for(auto&& x : arr)
{
std::cout<< x <<",";
}
std::cout<<std::endl;
}
int main()
{
vector<int> v1{1,2,3,4,5};
mergeSort(v1,0, v1.size() - 1);
print(v1);
vector<int> v2{1,3,2,4,5};
mergeSort(v2,0, v2.size() - 1);
print(v2);
vector<int> v3{5,4,3,2,1};
mergeSort(v3,0, v3.size() - 1);
print(v3);
vector<int> v4{1,5,2,4,3};
mergeSort(v4,0, v4.size() - 1);
print(v4);
}