c语言链表排序算法 比较排序之冒泡排序及优化

通过比较两个相邻的元素来将小的数交换到前面，最后选出最小的数放在最前面；排序步骤就是比较相邻元素并将较大的往后移。c语言链表排序算法c语言链表排序算法每扫描一轮，将确定一个元素的；

冒泡排序的时间复杂度为O(n^2)；

二、基本算法实现

1.基本函数构建

//构建随机数组

void builk_art(int* a,int n,int m) {

int i = 0;

for (; i < n; i++) {

*a++ = rand()% m;

}

}

//数据交换

void _swap(int *a,int *b) {

int temp = *a;

*a = *b;

*b = temp;

}

2.冒泡排序C语言实现

//冒泡排序

void bubbke_sort(int *a,int n) {

for (int i = 0; i < n; i++) { //外层循环??

for (int j = n - 1; j >= i+1; j--) {//内层循环

if (a[j] > a[j - 1]) { _swap(&a[j],&a[j - 1]); }//数据向前移动

}

}

}

3.冒泡排序第一层优化—提前终止

//标志位记录该次是否发生了交换，如果没有则退出，排序完成

void bubbke_sort1(int *a, int n) {

int flag = 0;

for (int i = 0; i < n; i++) {

if (flag == 1)break;

for (int j = n - 1; j >= i+1; j--) {

if (a[j] > a[j - 1]) { _swap(&a[j], &a[j - 1]); flag = 0; }

else {flag = 1; }

}

}

}

3.冒泡排序第三层优化

//进一步优化 记录上一次最后交换的位置 下次交换到该位置即可停止比较

void bubbke_sort2(int *a, int n) {

int i = n;

int flag = i;//记录上一次交换的位置

while (flag > 0) {

i = flag;//内层循环终止位置

flag = 0;//默认该次循环不交换 即完成排序 若进行了交换则更新

for (int j = 1; j < i; ++j) {

if (a[j] > a[j - 1]) { _swap(&a[j], &a[j - 1]); flag = j; }//记录本次内层循环最后交换的位置

}

}

}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-80536-1.html