基础数据结构和算法6:简单排序算法

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 步骤

  1. 首先实现一趟冒泡
    void bubble(int arr[],int n);
    
  2. 再实现多趟冒泡
    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 时间复杂度

一共比较n-1+n-2+...+2次,即\sum_{i=2}^{n-1}i = \frac{(2+n-1)\times(n-2)}{2} = \frac{n^2-n-2}{2} = O(n^2)

1.4 空间复杂度

随着n的增长,排序不需要增加额外空间,空间复杂度为O(1)

1.5 优化

尝试对已排序的数列冒泡排序


2. 选择排序

2.1 步骤

  1. 首先实现一趟,找出最大数字的下标
    int find_max_index(int arr[],int n);
    
  2. 实现多趟将最大数字与最后数字交换
    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 时间复杂度

一共比较n-1+n-2+...+2次,即\sum_{i=2}^{n-1}i = \frac{(2+n-1)\times(n-2)}{2} = \frac{n^2-n-2}{2} = O(n^2)

2.4 空间复杂度

随着n的增长,排序不需要增加额外空间,空间复杂度为O(1)

2.5 优化

同时选择最大值和最小值


3. 插入排序

3.1 步骤

  1. 实现向有序数列插入一个数字
    void insert(int arr[],int n);
    
  2. 依次在数组中插入数字
    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 时间复杂度

一共比较n-1+n-2+...+2次,即\sum_{i=2}^{n-1}i = \frac{(2+n-1)\times(n-2)}{2} = \frac{n^2-n-2}{2} = O(n^2)

3.4 空间复杂度

随着n的增长,排序不需要增加额外空间,空间复杂度为O(1)

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. 分析

试一下下面的数据比较次数和交换次数

  1. 随机
  2. 正序
  3. 逆序

5. 提高

  1. 使用swap()cmp()替换排序函数中的交换和比较处理。
  2. 实现向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 O(n^2) O(1) Yes
2 插入排序 Insertion Sort O(n^2) O(1) Yes
3 选择排序 Selection Sort O(n^2) O(1) No
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 总结一下常见的排序算法。 排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序...
    jiangliang阅读 1,376评论 0 1
  • Sort Algorithm(ASC) [TOC] //怎么生成目录,纠结ing 插入排序 每一趟排序都将待排元素...
    一条小袍袍YoY阅读 453评论 0 1
  • /* (无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。 选择排序思路: 1. 比较相邻的元素。如果...
    刘帆_d384阅读 488评论 0 0
  • 真的,我爱过,可能除了这一次,以前说的都不过是逢场作戏吧,我到现在都没谈过恋爱。 真的,她不喜欢我,至少这一次说的...
    我叫李大涛阅读 218评论 0 0
  • 1.目标肌肉:竖脊肌。 2.训练目的:增加目标肌肉力量与耐力。 3.器械名称:竖脊肌训练器。 4.动作名称:坐姿挺...
    古耐Nice阅读 2,532评论 0 3