# 排序算法
# 概述
算法分类:
十种常见排序算法主要分为两大类:
- 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破 O (nlogn),因此也称为非线性时间比较类排序。
- 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

算法复杂度

# 交换排序
# 1. 冒泡排序
1.1 算法描述
选定一个元素依次和后面的元素进行比较大小,如果大于 (小于) 那么就交换两个数的位置
例如:[2,5,1,4,6,8] 从小到大排序
- 2 比 5 小,满足条件,不用交换
- 5 比 1 大,所以交换顺序变成 [2,1,5,4,6,8]
- 5 比 4 大,所以变成 [2,1,4,5,6,8]
..........
直到全部比较完即可得到最终的排序结果
1.2 代码实现
#include <cstdio>
//冒泡排序
void BubleSort(int ans[],int len){
for(int i=0;i<len;i++){
for(int j=0;j<len-1-i;j++){
if(ans[j]>ans[j+1]){
int q=ans[j+1];
ans[j+1] = ans[j];
ans[j] = q;
}
}
}
}
int main(){
int un[]={3,2,5,1,5,2};
BubleSort(un,6);
for(int i=0;i<6;i++){
printf("%d",un[i]);
}
return 0;
}
# 2. 选择排序
2.1 算法描述
选择排序首先在一个未排序的数组 n 里面找到一个最大 (最小) 元素,然后与第一个元素进行交换位置,再接着寻找从 n 里面寻找第二大数值与第二个元素交换顺序,一直循环往后,直到倒数第二个元素和最后一个元素交换顺序。
2.2 代码实现
// C++ source file
#include <stdio.h>
void selectionSort(int ans[]){
int l=sizeof(ans)-1;
for(int i=0; i<l; i++) {
for(int j=i; j<l; j++) {
if(ans[i]<ans[j]){
int tmp=ans[i];
ans[i]=ans[j];
ans[j]=tmp;
}
}
}
}
int main(){
int ans[]={1,2,3,4,5,6,7};
selectionSort(ans);
int l=sizeof(ans)/sizeof(int);
for(int i=0; i<l; i++) {
printf("%d", ans[i]);
}
return 0;
}
# 3. 插入排序
3.1 算法描述
将未排序数组分为两部分,从第一个元素开始,进行排序,前面为已经排序好数组,以此向后扫描,对已经排序好的部分进行比较小大并插入
3.2 代码实现
// C++ source file
#include <stdio.h>
void insert_sort(int ans[]){
int l=sizeof(ans)-1;
for(int i=1; i<l; i++) {
int key=ans[i];
int j=i-1;
while(j>=0&&key<ans[j]) {
ans[j+1]=ans[j];
j--;
}
ans[j+1]=key;
}
}
int main(){
int ans[]={2,5,2,6,3,1,4};
insert_sort(ans);
int l=sizeof(ans)/sizeof(int);
for(int i=0; i<l; i++) {
printf("%d", ans[i]);
}
return 0;
}
# 4. 希尔排序
算法描述:
希尔排序是对插入排序的一种更高效的排序方法
它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
适用说明
希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好,但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多。
template<typename T>
void shell_sort(T array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
std::swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}