0. 测试框架
#include <stdio.h>
void print_array(int arr[],int n){
for(int i=0;i<n;++i){
printf("%d ",arr[i]);
}
printf("\n");
}
int* scanf_array(int arr[],int n){
for(int i=0;i<n;++i){
scanf("%d",&arr[i]);
}
return arr;
}
void swap(int* a,int* b){
int temp = *a;
*a = *b;
*b = temp;
}
int main(){
int n;
scanf("%d",&n);
int arr[n];
scanf_array(arr,n);
sort(arr,n);
print_array(arr,n);
}
或者
// 生成n个数据的随机数列[1,100]
int* createRandArray(int n){
int* arr = malloc(n*sizeof(int));
srand(time(NULL));
for(int i=0;i<n;++i){
arr[i] = rand()%100+1;
}
return arr;
}
// 打印数组
void printArray(int* arr,int n){
for(int i=0;i<n;++i){
printf("%d ",arr[i]);
}
printf("\n");
}
// 判度数组是否是非递减排序
bool isOrder(int* arr,int n){
for(int i=1;i<n;++i){
if(arr[i]>=arr[i-1]){
continue;
}else{
return false;
}
}
return true;
}
测试OJ
1. 冒泡排序
1.1 步骤
- 首先实现一趟冒泡
void bubble(int arr[],int n);
- 再实现多趟冒泡
void bubble_sort(int arr[],int n);
1.2 参考代码
void bubble(int arr[],int n){
for(int i=0;i<n-1;++i){
if(arr[i] > arr[i+1]){
swap(arr+i,arr+i+1);
}
}
}
void bubble_sort(int arr[],int n){
for(int i=n;i>1;i--){
bubble(arr,i);
}
// while(n>1) bubble(arr,n--);
}
1.3 时间复杂度
一共比较次,即
1.4 空间复杂度
随着的增长,排序不需要增加额外空间,空间复杂度为
。
1.5 优化
尝试对已排序的数列冒泡排序
2. 选择排序
2.1 步骤
- 首先实现一趟,找出最大数字的下标
int find_max_index(int arr[],int n);
- 实现多趟将最大数字与最后数字交换
int selection_sort(int arr[],int n);
2.2 参考代码
int find_max_index(int arr[],int n){
int max = arr[0];
int max_index = 0;
for(int i=1;i<n;++i){
if(max < arr[i]){
max = arr[i];
max_index = i;
}
}
return max_index;
}
void selection_sort(int arr[],int n){
for(int i=n;i>1;--i){
int max_index = find_max_index(arr,i);
swap(arr+max_index,arr+i-1);// i是数组长度,最后一个元素下标要减1
}
}
2.3 时间复杂度
一共比较次,即
2.4 空间复杂度
随着的增长,排序不需要增加额外空间,空间复杂度为
。
2.5 优化
同时选择最大值和最小值
3. 插入排序
3.1 步骤
- 实现向有序数列插入一个数字
void insert(int arr[],int n);
- 依次在数组中插入数字
void insertion_sort(int arr[],int n);
3.2 参考代码
void insert(int arr[],int n){
for(int i=n-2;i>=0;--i){
if(arr[i+1]<arr[i]){
swap(arr+i+1,arr+i);
}
}
}
void insertion_sort(int arr[],int n){
for(int i=2;i<=n;++i){
insert(arr,i);
}
}
3.3 时间复杂度
一共比较次,即
3.4 空间复杂度
随着的增长,排序不需要增加额外空间,空间复杂度为
。
3.5 优化
用移动代替交换
void insert(int arr[],int n){ // 最后一个元素是待插入元素
int key=arr[n-1];
int i=0;
for(i=n-1;i>=1&&arr[i-1]>key;--i){
arr[i] = arr[i-1];
}
arr[i] = key;
}
void insertion_sort(int arr[],int n){
for(int i=1;i<n;++i){// 插入元素i操作
insert(arr,i+1); // i+1表示数组长度,最后一个元素表示要插入的
}
}
4. 分析
试一下下面的数据比较次数和交换次数
- 随机
- 正序
- 逆序
5. 提高
- 使用
swap()
和cmp()
替换排序函数中的交换和比较处理。 - 实现向
qsort
一样的排序函数。
例如:void bubble_sort(void* arr[],int n,int size,int (*cmp)(const void*,const void*));
6. 小结
- 排序的稳定性
在待排序的序列中,存在多个相同的关键字记录,经过排序这些记录相对位置保持不变,则这种排序称为稳定的,否则称为不稳定的。

No. | 算法 | Algorithm | Time Complexity | Space Complexity | Stable |
---|---|---|---|---|---|
1 | 冒泡排序 | Bubble Sort | Yes | ||
2 | 插入排序 | Insertion Sort | Yes | ||
3 | 选择排序 | Selection Sort | No |
网友评论