冒泡排序基本思想
基本思想：对元素个数为N的的待排序序列进行排序时，共进行N-1次循环。在第K次循环中，对于从第1到k-1个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素(相等的时候不交换，这也是为什么冒泡是稳定的)，则两者交换位置，否则保持位置不变。这样一次循环下来，就把第k大的元素移动到第N-k个位置上，称为第k趟的冒泡。整个过程一共进行N-1趟冒泡，直到第1个和第2个元素比较完成，最终剩余最小的元素，留在第1个位置上，排序结束
动画演示：
冒泡排序代码
SortHelper.h存放相关工具函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127#ifndef ALGORITHM_SORTHELPER_H
#define ALGORITHM_SORTHELPER_H
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
int *generateRandomArray(int n, int rangeL, int rangeR)
{
int * arr = NULL;
int i;
if (n > 0 && rangeL <= rangeR)
{
arr = (int *) malloc(sizeof(int) * n); // 用malloc 分配数组 是因为不用malloc的话 随着此函数的结束 数组空间会被释放掉
srand(time(NULL));
for (i = 0; i < n; ++i)
{
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL; // 注意区间是[rangeL, rangeR]
}
}
return arr;
}
// 交换两个数位置
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// 生成近乎有序的数组 n数据个数 swapTimes:交换次数 最多只有2*交换次数个元素无序
int * generateNearlyOrderArray(int n, int swapTimes)
{
int i;
int *arr = NULL;
if (n > 0)
{
arr = (int *) malloc(sizeof(int) * n);
for (i = 0; i < n; ++i)
{
arr[i] = i;
}
srand(time(NULL));
for (i = 0; i < swapTimes; ++i)
{
int x = rand() % n;
int y = rand() % n;
swap(&arr[x], &arr[y]);
}
}
return arr;
}
// 生成近乎倒序的数组 n数据个数 swapTimes:交换次数 最多只有2*交换次数个元素无序 左闭右开
int * generateNearlyReverseOrderArray(int n, int swapTimes)
{
int i;
int *arr = NULL;
if (n > 0)
{
arr = (int *) malloc(sizeof(int) * n);
for (i = 0; i < n; ++i)
{
arr[i] = n-1-i;
}
srand(time(NULL));
for (i = 0; i < swapTimes; ++i)
{
int x = rand() % n;
int y = rand() % n;
swap(&arr[x], &arr[y]);
}
}
return arr;
}
// 插入排序
void InsertionSort(int * arr, int left, int right)
{
int i, j;
for (i = left + 1; i <= right; ++i)
{
int temp = arr[i];
for (j = i; j > left && arr[j-1] > temp; j--)
{
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
// 打印数组
void printArray(int *arr, int n)
{
int i;
for (i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void testSort(char * sortName, void(*sort)(int* , int ), int * arr, int n)
{
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
printf("%s cost: %lfs\n",sortName, (double)(endTime - startTime) / CLOCKS_PER_SEC);
}
// 拷贝arr数组
int * copyArray(int *arr, int n)
{
int i;
int *arr2 = (int *) malloc(sizeof(int) * n);
for (i = 0; i < n; ++i)
{
arr2[i] = arr[i];
}
return arr2;
}
#endif //ALGORITHM_SORTHELPER_H
BubbleSort.c冒泡排序源码如下：
1 | #include <stdio.h> |
Clion运行结果如下：
双向冒泡排序
1 | // 双向冒泡：奇数趟，从前往后比较相邻元素，关键字最大的放在序列尾 |
总结
时间复杂度：O(n^2) 指的是平均时间复杂度空间复杂度：O(1) 拿bubbleSort2来说 只开辟了p,i,flag等常数个空间
稳定性 ： 稳定的 元素关键字相等的两个元素进行比较时并不会发生交换，即相对位置不会发生变化
冒泡排序最坏的情况下(序列时逆序排序的)，每次比较都需要进行交换，时间复杂度O(N^2)
冒泡排序最好的情况下(序列已经有序)，这时由于用了flag标志只要进行O(N)次比较就可以从循环跳出来.看上面运行结果图在几乎有序的情况下，未经flag优化的运行时间。
pS: 源代码链接