基础数据结构及算法：简单排序算法，包括选择排序、插入排序、冒泡排序

文章目录

- 1. 测试框架
- 2. 选择排序
- 3. 插入排序
- 4. 冒泡排序

1. 测试框架

完成功能：

输入数字 n，生成 n 个 0～n 的随机数
使用 qsort 升序排序
如果数据为升序则输出 1，否则为 0

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示为升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

int cmp(const void* a,const void* b){
        return *(int*)a - *(int*)b;
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        qsort(arr,n,sizeof(int),cmp);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

结果为：

30
18 8 7 9 23 18 20 29 13 16 27 9 29 23 27 10 0 12 23 15 9 12 1 25 3 15 29 0 19 19 
0
0 0 1 3 7 8 9 9 9 10 12 12 13 15 15 16 18 18 19 19 20 23 23 23 25 27 27 29 29 29 
1

2. 选择排序

选择排序排序思路：

找到数组中数据最大的数
把找到的最大的数和最后一个没排好序的数交换位置
除了后面排好的数，剩下的数继续完成上述操作

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示为升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/******************选择排序******************/

//交换
void swap(int* p,int* q){
        int t = *p;
        *p = *q;
        *q = t;
}

//找到数组中最大的数
int FindMax(int* arr,int n){
        int index = 0;
        for(int i=0;i<n;++i){
                if(arr[index] < arr[i]){
                        index = i;
                }
        }
        return index;
}

/*
//把最大数和最后一个没排好序的数交换（递归）
void SelectionSort(int* arr,int n){
        if(0 == n) return;
        int index = FindMax(arr,n);
        swap(arr+index,arr+n-1);
        SelectionSort(arr,n-1);   //递归
}
*/

//把最大数和最后一个没排好序的数交换（迭代）
void SelectionSort(int* arr,int n){
        for(int i=0;i<n;++i){
                int index = FindMax(arr,n-i);   // 要判断n-i次
                swap(arr+index,arr+n-1-i);     //要与第n-1-i个数交换
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        SelectionSort(arr,n);  // 选择排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

结果为：

30
0 12 22 27 29 16 1 10 1 6 4 17 27 12 2 4 25 1 11 8 28 8 27 29 4 18 2 22 23 6 
0
0 1 1 1 2 2 4 4 4 6 6 8 8 10 11 12 12 16 17 18 22 22 23 25 27 27 27 28 29 29 
1

3. 插入排序

插入排序排序思路：

从前往后抽牌，抽到的数要往前面排好序的数字中插
插，有两种方法：

第一种是从前往后，用抽到的数和数组中的数一一比较，找到第一个比抽到的这个数大的数，然后把包括这个数后面的数都向后移，把抽到的数放在这个位置上

第二种是从后往前，用抽到的数和数组中的数一一比较，如果比抽到的这个数大，则直接向后移一位，如果小于或等于抽到的这个数，则把抽到的这个数放在数组数后面一位

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示为升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/*****************插入排序********************/

/*
//从前往后找到数组中第一个大于摸到数，插到该位置上
void Insert(int* arr,int n){
        for(int i=0;i<n-1;++i){
                if(arr[n-1] < arr[i]){    //从前往后找第一个大于arr[n-1]的数
                        int last = arr[n-1];       //存下最后的数
                        for(int j=n-1;j>i;--j){      //后面的数往后一个一个移开
                                arr[j] = arr[j-1];     
                        }
                        arr[i] = last;         //把存下的数放在i位置上
                        break;
                }
        }
}
*/

//从后往前找小于等于摸到数的数，边找边移动，找到就放紧跟的位置
void Insert(int* arr,int n){
        int last = arr[n-1];
        for(int i=n-2;i>=0;--i){     //从后往前找一个小于等于arr[n-1]的数
                if(arr[i] > last){
                        arr[i+1] = arr[i];
                }else{
                        arr[i+1] = last;
                        return;
                }
        }
        arr[0] = last;  //如果整个数组没有比last小的数，要做头插操作
}

//从前往后摸牌操作
void InsertionSort(int* arr,int n){
        for(int i=1;i<=n;++i){
                Insert(arr,i);
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        InsertionSort(arr,n);  // 插入排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

结果为：

30
1 13 25 29 21 9 9 27 3 26 22 13 26 26 15 1 5 15 7 29 6 8 2 14 20 24 29 16 0 17 
0
0 1 1 2 3 5 6 7 8 9 9 13 13 14 15 15 16 17 20 21 22 24 25 26 26 26 27 29 29 29 
1

稳定性：两个相等数据在排序前后是否改变原来的顺序

选择排序–不稳定

插入排序–稳定

冒泡排序–稳定

4. 冒泡排序

冒泡排序排序思路：

从前往后相邻数字依次比较，前面的数比后面的数大则两数交换，否则两数位置不变，这样就可以把最大的数慢慢移到最后
每一轮比较的次数比前一轮的次数少1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示为升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/*****************冒泡排序********************/

//交换
void swap(int* p,int* q){
        int t = *p;
        *p = *q;
        *q = t;
}

//相邻值比较，前大于后，则交换
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);
                }
        }
}

/*
//每一轮比较次数减1（递归）
void BubbleSort(int* arr,int n){
        if(0 == n) return;
        Bubble(arr,n);
        BubbleSort(arr,n-1);
}
*/

//每一轮比较次数减1（迭代）
void BubbleSort(int* arr,int n){
        for(int i=n;i>0;--i){
                Bubble(arr,i);
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        BubbleSort(arr,n);  // 冒泡排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

结果为：

30
8 6 10 23 11 21 1 18 13 21 6 1 19 9 17 29 3 27 5 6 5 21 28 2 26 19 0 0 8 23 
0
0 0 1 1 2 3 5 5 6 6 6 8 8 9 10 11 13 17 18 19 19 21 21 21 23 23 26 27 28 29 
1

简单排序算法总结：

简单的排序算法	时间复杂度	空间复杂度	稳定性	已排好(最好)情况
选择排序 SelectionSort	O(n^2)	O(1)	NO	O(n^2)
插入排序 InsertionSort	O(n^2)	O(1)	YES	O(n)
冒泡排序 BubbleSort	O(n^2)	O(1)	YES	O(n^2)/O(n)

冒泡排序的优化：

如果在一轮比较中没有发生交换的操作，则证明已经排好序，即可终止后续的排序

可以更改为：

//相邻值比较，前大于后，则交换
bool Bubble(int* arr,int n){
        bool ordered = true;   //ordered用于标记
        for(int i=0;i<n-1;++i){
                if(arr[i] > arr[i+1]){
                        ordered = false;      //表示本轮有交换操作
                        swap(arr+i,arr+i+1);
                }
        }
        return ordered;
}

//每一轮比较次数减1（迭代）
void BubbleSort(int* arr,int n){
        for(int i=n;i>0;--i){
                if(Bubble(arr,i)) break;     //没有交换操作直接终止排序
        }
}

基础数据结构及算法：简单排序算法，包括选择排序、插入排序、冒泡排序

文章目录

1. 测试框架

2. 选择排序

3. 插入排序

4. 冒泡排序

继续阅读

开源低带宽语音编解码器

CRC32和CRC8校验代码，C语言版

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

C语言：初学者必定看懂的注释！！！猴子吃桃问题。猴子第一天摘下若干个桃子，每天都吃了前一天剩下的一半零一个，到第10天早上想再吃的时候，就剩下一个桃子. 求第一天共摘多少个桃子。

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

while 循环、do- while 循环和 for 循环之间的那点事C语言自学之三种循环比较

数据结构与算法（27）——排序（二）

结构体：typedef与struct的区别

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希