冒泡排序

发表于 | 分类于

本篇一起来学习冒泡排序的算法,今天跟大家一起来学冒泡排序算法。本篇将会使用C语言、ObjC和Swift分别来实现冒泡排序，并通过ObjC来举一个模型类冒泡排序的小例子，希望对大家在开发中应用算法有所帮助。

核心思想

算法最讲究的就是算法的思想，只要将算法思想想明白了，就可以通过伪代码来写出算法，那么再使用对应的语言来实现就可以了。

冒泡排序的核心思想就是通过与相邻元素的比较和交换，把小的数交换到最前面。因为这个过程类似于水泡向上升一样，因此被命名为冒泡排序。

举个小例子：对5,3,8,6,4这个无序序列进行冒泡排序。

首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。

其过程大概是这样的：

第一趟：

  1. 5, 3, 8, 6, 4 （开始）
  2. 5, 3, 8, 4, 6 （6和4交换）
  3. 5, 3, 4, 8, 6 （8和4交换）
  4. 5, 3, 4, 8, 6 （3和4不用交换）
  5. 3, 5, 4, 8, 6 （5和3交换）

第二趟：

  1. 3, 5, 4, 6, 8 （8和6交换)
  2. 3, 5, 4, 6, 8 （4和6不用交换）
  3. 3, 4, 5, 6, 8 （5和4交换）
  4. 3, 4, 5, 6, 8 （3和4不用交换）

这里只需要两趟就可以排序完成了。

时间复杂度

从算法思想可知，冒泡排序需要两个循环来控制遍历，也就是需要n * n趟才能判断、交换完成。

冒泡排序的时间复杂度为O(n2)。

伪代码

void bubbleSort(int a[], int len) { 
   for i = 0; i < len - 1; i {     
      for j = len - 1; j > i; --j { 
         if a[j] < a[j - 1] {    
            swap(a, j, j - 1);        
         }                            
      }                               
   }                                  
}                                     

void swap(int a[], int i, int j) {  
   int temp = a[i];                 
   a[i] = a[j];                   
   a[j] = temp;                     
}

C语言版

void bubbleSortUsingC(int arr[], int len) {       
  // 代表走多少趟，最后一趟就不用再走了             
  for (int i = 0; i < len - 1; i) {              
    // 从后往前走，相当于泡从水底冒出来到水面       
    for (int j = len - 1; j > i; --j) {           
      // 如果后面的比前面一个的值还要小，则需要交换 
      if (arr[j] < arr[j - 1]) {              
        swap(arr, j, j - 1);                        
      }                                             
    }                                             
  }                                                 
}                                                   


void swap(int arr[], int i, int j) {             
  int temp = arr[i];                              
  arr[i] = arr[j];                             
  arr[j] = temp;                                  
}

测试一下：

int a[5] = {5,3,8,6,4};                            
bubbleSortUsingC(a, sizeof(a) / sizeof(int));        

for (int i = 0; i < sizeof(a) / sizeof(int); i) {
   NSLog(@"%d", a[i]);                          
}                                                    
// 打印: 3, 4, 5, 6, 8 初步如期效果

ObjC版

  • (void)bubbleSort:(int [])array len:(size_t)len {
    for (size_t i = 0; i < len - 1; i) {
    for (size_t j = len - 1; j > i; –j) { 
    if (array[j] < array[j - 1]) {              
// 交换                                        
int temp = array[j];                         
array[j] = array[j - 1];                   
array[j - 1] = temp;                         
}
    }
    }
    }

测试使用：

int a[5] = {5,3,8,6,4};

[self bubbleSort:a len:sizeof(a) / sizeof(int)];

for (int i = 0; i < sizeof(a) / sizeof(int); i) { 

NSLog(@"%d", a[i]);

}

Swift版

func bubbleSort(var arr: [Int]) ->[Int] {

// 走多少趟

for var i = 0; i < arr.count - 1; i {

// 从后往前
for var j = arr.count - 1; j > i; –j { 

// 后者 < 前者 ？ 交换 ： 不交换        
if arr[j] < arr[j - 1] {            
      let temp = arr[j]                    
      arr[j] = arr[j - 1]                
      arr[j - 1] = temp                    
     }                                        
   }                                          
 }                                            
 return arr

测试使用：

//由于swift中数组也是结构体，是值类型，因此需要接收返回值才能得到排序后的数组                    
  var arr = [5, 3, 8, 6, 4]       
  arr = bubbleSort(arr)             
  print(arr)

尝试给Model排序

  • (void)bubbleSort:(NSMutableArray *)array {

    for (NSUInteger i = 0; i < array.count - 1; i) { 

    for (NSUInteger j = array.count - 1; j > i; --j) {           

 TestModel *modelj = [array objectAtIndex:j];              

 TestModel *modelj_1 = [array objectAtIndex:j - 1];       

 // 前者 < 后者 ？ 交换 ：不交换                            

 if ([modelj.uid compare:modelj_1.uid options:NSCaseInsensitiveSearch] == NSOrderedAscending) {                              
      [array exchangeObjectAtIndex:j withObjectAtIndex:j - 1]; 
     }                           
   }                             
 }

    }

测试： 

NSMutableArray *array = [[NSMutableArray alloc] init];        

 for (NSUInteger i = 0; i < 10; i) {                             

 TestModel *model = [[TestModel alloc] init];                

 model.title = [NSString stringWithFormat:@"[公羽寒](http://cnblogs.com/gongyuhonglou)的技术博客：%ld", 10 - (i + 1)];                              
 model.uid = [NSString stringWithFormat:@"%ld", 10 - (i  1)];                                 
 [array addObject:model];      
 } 

 [self bubbleSort:array]; 

 for (TestModel *model in array)  
 {                                 
   NSLog(@"%@%@", model.uid, model.title);    
}                                 
 // 打印:
0%