写于: 2016年06月06日
自学算法 ing ...
感谢iOS路上不可替代的小伙伴JXT (......)
加油, 努努! (ps:夜深人静想点事情也方便.有点矫情了喔, 嘿_)
冒泡排序
原理
俩俩比较 相邻记录的排序码, 若发生逆序, 则交换; 有两种方式进行冒泡, 一种是先把小元素的冒泡到前边去(常用), 另一种是把大的元素冒泡到后边.
实现步骤, 请前往下一篇:Take my word for it 看完这些 你会彻底理解排序算法看视频喔!
性能
时间复杂度为O(N^2), 空间复杂度为O(1). (ps:不懂的自行百度喔)
排序是稳定的, 排序比较次数与初始序列无关, 但交换次数与初始序列有关.
==废话不说, 看代码==
#include <stdio.h>
void swap(int *a, int *b);
int main () {
int arr[10] = {15, 226, 34, 49, 6, 78, 523, 312, 8, 99};
for (int i = 0; i < 10; i++) { //每一次由底至上地上升
for (int j = 9; j> i; j--) {
if (arr[j] < arr[j-1]) {
swap(&arr[j], &arr[j-1]);
}
}
}
for (int i = 0; i < 10; i++) {
printf("%d ",arr[i]);
}
return 0;
}
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
结果:
优化
比如{2,1,3,4,5,6,7,8,9},除了第一次循环交换,后面都会排好的无序在交换. 即初始序列就是排序好的, 对于冒泡排序任然还要比较O(N^2)次, 但无交换次数. 可根据这个进行优化, 设置一个标记变量flag, 标记数列中的数是否在循环结束前就已经排好序. 当在一趟序列中没有发生交换, 则该序列已排序好, 但优化后排序的时间复杂度 没有发生量级的改变.
==呈上代码==
#include <stdio.h>
void swap(int *a, int *b);
int main() {
int arr[10] = {2, 1, 3, 4, 5, 6, 7, 8 ,9, 10};
int flag = 1; //设置标记变量
for (int i = 0; i < 10 && flag; i++) {
flag = 0; //只要flag在下一次外循环条件检测的时候值为0, 就说明已经排好序,不用继续循环
for (int j = 9; j > i; j--) {
if (arr[j] < arr[j-1]) {
swap(&arr[j], &arr[j-1]);
flag = 1; //如果有交换, 就将标记变量赋1
}
}
}
for (int i = 0; i < 10; i++) {
printf("%d ",arr[i]);
}
return 0;
}
void swap(int *a, int *b);
int temp;
temp = *a;
*a = *b;
*b = temp;
