作者：zhangwenkaii_555 | 来源：互联网 | 2023-09-03 10:55
学习与整理留存。
七大排序算法分析
| 排序算法 |
时间复杂度（平均） |
空间复杂度 |
稳定性 |
| 冒泡排序 |
O(n^2) |
O(1) |
稳定 |
| 插入排序 |
O(n^2) |
O(1) |
稳定 |
| 选择排序 |
O(n^2) |
O(1) |
不稳定 |
| 快速排序 |
O(nlog n) |
O(log n) |
不稳定 |
| 希尔排序 |
O(nlog n) |
O(1) |
不稳定 |
| 归并排序 |
O(nlog n) |
O(n) |
稳定 |
| 堆排序 |
O(nlog n) |
O(1) |
不稳定 |
亲测好用C/C++实现汇总：
#include
#include
#include
#define NUM 50
using namespace std;
//交换函数
void swap(int *a,int i,int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
//输出函数
void print(int *a)
{
for(int i=0;i= high || high <= 0 || low <0)
return;
bool flag = true;
for(int i=0; ia[j+1])
{
swap(a,j,j+1);
flag = true;
}
}
}
}
//选择排序
void select_sort(int *a,int low,int high)
{
if(a == NULL || low >= high || high <= 0 || low <0)
return;
int minpos;
for(int i=0;i= high || high <= 0 || low <0)
return;
int tmp;
for(int i=1;i=0;--j)
{
if(a[j]>tmp)
a[j+1]=a[j];
else
break;
}
if(j+1 != i)
a[j+1]=tmp;
}
}
//快速排序
int partition(int *a,int low,int high)
{
int pivot = a[low];
while(low=pivot)
--high;
a[low]=a[high];
while(low= high || high <= 0 || low <0)
return;
int pos;
while(low= high || high <= 0 || low <0)
return;
int mid = (low+high)>>1;
merge_sort(a,low,mid);
merge_sort(a,mid+1,high);
merge(a,low,mid,high);
}
//堆排序
void adjust(int *a,int low,int high)//大顶堆
{
int tmp=a[low];
for(int i=(low<<1)+1;i=a[i])
break;
a[low]=a[i];
low=i;
}
a[low]=tmp;
}
void heap_sort(int *a,int low,int high)
{
if(a == NULL || low >= high || high <= 0 || low <0)
return;
for(int i=high>>1;i>=0;--i)
adjust(a,i,high);
for(int i=high;i>0;--i)
{
swap(a,0,i);
adjust(a,0,i);
}
}
//希尔排序
void shell_sort(int *a,int low,int high)
{
if(a == NULL || low >= high || high <= 0 || low <0)
return;
/*设置增量*/
int d = high+1;
while (d > 1)
{
d = (d + 1)>>1;
for (int i = d; i <= high; ++i)
{
/*要插入的元素*/
int tmp = a[i];
/*从已有序序列尾向前寻找合适位置*/
int j = i-d;
for (; j >= low; j-=d)
{
if (a[j] > tmp)
a[j + d] = a[j];
else
break;
}
a[j + d] = tmp;
}
}
}
int main()
{
int a[NUM],b[NUM];
clock_t start,end;
srand(time(0));
cout<<"original array:";
for(int i=0;i
测试：
original array:295 233 178 260 312 24 81 106 220 184 243 109 383 178 184 325 10 370 363 2 26 314 129 366 8 118 384 152 137 224 292 385 9 23 245 274 399 278 380 219 62 175 280 398 353 64 275 315 34 238
bubble_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:12ms
select_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:8ms
insert_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:4ms
quick_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:5ms
merge_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:8ms
heap_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:5ms
shell_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399
time:7ms
京公网安备 11010802041100号