参照百度百科(冒泡排序)做摘要学习使用。
概念
冒泡排序（Bulle Sort），是一种计算机领域的较简单的排序算法。
它重复的走访要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如果从大到小，首字母从A到A）错误就把他们交换过来，走访元素的工作是重复的进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
算法原理
冒泡排序算法的原理如下：
1、比较相邻的元素，如果第一个比第二个大，就交换他们两个。
2、对每一个相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法分析
- 时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比价次数C和记录移动次数M均达到最小值：
Cmin = n - 1, Mmin = 0。
所以，冒泡排序最好的时间复杂度为O(n)。
如果初始化文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较（1<=i<=n-1），且每次比较必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = (n(n-1))/2 = O(n^2)，Mmax = (3n(n-1)) / 2 = O(n^2)
冒泡排序的最坏时间复杂度为O(n^2)。
综上，因此冒泡排序总的平均时间复杂度为O(n^2)。
- 算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同的元素前后顺序并没有改变，所以冒泡排序是一种稳定的排序算法。
C语言代码
#include <stdio.h>
#define SIZE 8
void bubble_sort(int a[], int n);
void bubble_sort(int a[], int n)
{
int i, j, temp;
for (j = 0; j < n - 1; j++)
for (i = 0; i < n - 1 - j; i++)
{
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
int main()
{
int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
int i;
bubble_sort(number, SIZE);
for (i = 0; i < SIZE; i++)
{
printf("%d\n", number[i]);
}
return 0;
}
另一种可以参考的做法是（在此只给出关键实现部分，其余部分请读者自行实现）,另外请注意item类型。
void refore(item *a,int index1,int index2)
{
item temp_data = a[index2];
a[index2] = a[index1];
a[index1] = temp_data;
return;
}
void bsort(item *a,int index_top)
{
int out_count = 0;
while(out_count != (index_top+1)*(index_top+1)){
int this_index = 0;
while(this_index <= index_top){
if(a[this_index] > a[this_index + 1])
refore(a,this_index,this_index + 1);
this_index++;
}
out_count++;
}
}
Objective-C 代码
for (int i = 0; i<result.count-1; i++) {
for (int j = 0; j<result.count-1-i; j++) {
NSInteger left = [result[j] integerValue];
NSInteger right = [result[j+1] integerValue];
if (left>right) {
[result exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",result);
Swift 代码
func bubbleSort(_ nums: inout [Int]) {
let n = nums.count
for i in 0..<n {
for j in 0..<(n - 1 - i) {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
}
}
}
print(nums)
}
var nums = [1,3,7,8,9]
bubbleSort(&nums)
优化后的代码 以C语言为例
根据flag标识，判断如果数据元素已经为有序的，则可以提前结束比较行为，减少不必要的遍历
/**
☺比较正宗的冒泡排序算法
@param k 传入待排序数据数组
@param n 数组元素个数
*/
void bulleSort(int k[], int n) {
printf("\n\n开始正宗的冒泡排序算法，排序前");
for (int i = 0; i < n; i++) {
printf("%d ", k[i]);
}
int i, j, temp = 0, count1 = 0, count2 = 0, flag;
flag =1;
for (i=0; i<n-1 && flag; i++) {
for (j=1; j<n-i; j++) {
count1++;
flag = 0;
if (k[j-1] > k[j]) {
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
count2++;
flag = 1;
}
}
}
printf("\n排序完成后：\n");
for (int i = 0; i < n; i++) {
printf("%d ", k[i]);
}
printf("+++++++++进行了[%d]次比较，[%d]移动\n", count1, count2);
}
网友评论