美文网首页
基础数据结构和算法6:简单排序算法

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

作者: jdzhangxin | 来源:发表于2019-05-02 10:06 被阅读0次

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

相关文章

网友评论

      本文标题:基础数据结构和算法6:简单排序算法

      本文链接:https://www.haomeiwen.com/subject/wfeqiqtx.html