对于冒泡排序的含义以及图示表示,这里就不再赘述,这篇博客已经说的很明白了. 添加链接描述 于是就用代码实现了一下基于顺序表的冒泡排序 ,因为一直看的时大话数据结构这本书 于是把上面介绍的三种实现方法都在代码中实现一下 具体实现与书中有一些出入.在上述博客给出代码的基础上做出了改进.因为后期还有用到排序算法,后期会对顺序表的基本操作这一块儿进行封装.下面是代码实现,详细已经在代码中做出了声明.
#include<stdio.h> #include<assert.h> #include<iostream> #include<string.h> using namespace std; #define MAX_SIZE 20 /* *代码中多次出现assert()函数 于是查了一下assert函数的用法 *assert的作用是先计算表达式 expression ，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。 */ typedef struct { int a[MAX_SIZE];//用于储存排序数组 int size;//用于记录顺序表的长度 }seqlist; //顺序表初始化 void init_list(seqlist *l) { assert(l);//判断l是否为空 memset(l->a, 0, sizeof(l->a));//初始化数组 l->size = 0; } //尾插 void last_insert(seqlist *l, int n) { assert(l); if (l->size < MAX_SIZE) { l->a[l->size] = n;//由于下标是从0开始的 然后尾部插入法就是将n赋值给a[l->size] l->size++;//总数加1 } else { cout << "空间不足" << " "; } } //尾删 void last_delete(seqlist *l) { assert(l); if (l->size == 0) { cout << "顺序表元素为空" << " "; } if (l->size != 0) l->a[l->size] = 0; l->size--; } //头插 void front_insert(seqlist *l, int n) { assert(l); if (l->size == 0)//如果是空表 那么直接放入到头部位置 也就是a[0]的位置 l->a[l->size] = n; else {//如果不是空表 那么头插法将所有元素后移一位 将a[0]空出来 再赋值 for (int j = l->size; j > 0; j--) l->a[j] = l->a[j - 1]; l->a[0] = n; } l->size++;//总个数加一 } //头删 void front_delete(seqlist *l) { assert(l); if (l->size == 0) { printf("顺序表无元素"); } for (int i = 0; i < l->size; i++) { l->a[i] = l->a[i + 1]; } l->size--; } //读取数组中第n个元素的值 void read(seqlist *l, int n) { assert(l); if (n <= l->size) std::cout << n << ":" << l->a[n - 1] << " "; } //把第i个数改为m void change(seqlist *l, int i, int m) { assert(l); l->a[i - 1] = m; } //打印顺序表 void print(seqlist *l) { assert(l); for (int i = 0; i < l->size; i++) printf("%d ", l->a[i]); } //找到数为n在数组中的下标位置 void find(seqlist *l, int n) { assert(l); for (int i = 0; i < l->size; i++) { if (l->a[i] == n) printf("数组下标为%d的等于%d ", i,n); } } //在第i个位置上插入数字n int insert(seqlist *l, int i, int n) { if (i<1 || i>l->size + 1) { cout << "插入位置不对" << " "; return -1; } if (l->size == MAX_SIZE - 1) { cout << "存储空间不足" << " "; return -1; } for (int j = l->size; j >= i; j--) { //数组整体后移 l->a[j] = l->a[j - 1]; } //把下标位置为i-1的位置空出来 再赋值 l->a[i - 1] = n; l->size++;//总个数再加一 return 0; //return 1和return 0? } //交换数组中下标为i和j的值 void swap(seqlist *l,int i,int j){ int temp=l->a[i]; l->a[i]=l->a[j]; l->a[j]=temp; } //冒泡排序 //最简单的排序 void bubblesort(seqlist *l) { if (l->size == 0) { cout << "顺序表空" << " "; return; } for(int i=0;i<l->size;i++){ for(int j=i+1;j<l->size;j++){ if(l->a[i]>l->a[j]){ swap(l,i,j); } } } } //正宗的冒泡排序 void bubblesort1(seqlist *l){ int i,j; for(i=0;i<l->size;i++){ for(j=l->size-2;j>=i;j--)//注意j是从后往前循环 { if(l->a[j]>l->a[j+1])//若前者大于后者 与上一个算法存在差异 { swap(l,j,j+1); } } } } //冒泡排序的改进算法 void bubblesort2(seqlist *l){ int i,j; bool flag=true;//flag for(i=0;i<l->size&&flag;i++) //若flag为flase 则退出循环 { //这里的意思就是 如果flag为false 说明没有进行位置的移动 //就是可以减少已经是顺序结构是不必须的再比较过程 这样就可以节省时间 flag=false; for(j=l->size-2;j>=i;j--) { if(l->a[j]>l->a[j+1]) { swap(l,j,j+1); flag=true; } } } } int main() { int n; seqlist l; init_list(&l); last_insert(&l, 3); last_insert(&l, 5); last_insert(&l, 4); insert(&l, 2, 7); insert(&l, 3, 8); print(&l); printf("\n"); // bubblesort(&l); // print(&l); //printf("\n"); // bubblesort1(&l); // print(&l); bubblesort2(&l); print(&l); return 0; }main函数中有每种算法的实现.
