冒泡排序和快速排序算法简述

一、冒泡排序

1、冒泡排序（Bubble Sort），是一种较简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，所以命名为冒泡排序。

2、稳定性：稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

3、时间复杂度：

最优：O(n)

最差：O(n^2)

平均：O(n^2)

4、代码实现

//冒泡排序
- (void)bubbleSort:(NSMutableArray *)mutArray {
    
    NSUInteger count=[mutArray count];
    
    for(int i=0;i<count;i++){
        
        for (int j=0; j<count-i-1;j++) {
            
            if ([mutArray[j] integerValue]>[mutArray[j+1] integerValue]) {
            
                NSString *temp=mutArray[j];
                
                mutArray[j]=mutArray[j+1];
                
                mutArray[j+1]=temp;
                
            }
        }
    }
    
    for (NSInteger i=0; i<[mutArray count]; i++) {
        
        NSLog(@"冒泡排序:%@",mutArray[i]);
    }
}

5、测试代码

NSMutableArray *dataArray = [[NSMutableArray alloc] initWithObjects:@"18",@"20",@"3",@"12",@"1",@"99",@"28", nil];
    
[self bubbleSort:dataArray];
    
NSLog(@"冒泡排序:%@",dataArray);

打印结果为：
冒泡排序:(
    1,
    3,
    12,
    18,
    20,
    28,
    99
)

二、快速排序

1、快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

（1）先从数列中取出一个数作为基准数。
（2）分区过程，将比这个数大的数全放到它的右边，小于或等于它 的数全放到它的左边。
（3）再对左右区间重复第二步，直到各区间只有一个数。

2、稳定性：不稳定

这里解释一下不稳定的原因：
排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

快速排序有两个方向，
初始时，i=0，j=数组元素总个数减去1（也就是数组最后一个元素的下标），X=a[i],(i是X在数组中的下标，一般X取为数组第0个元素),其中X作为基准数。
首先从j开始向前找一个比X小或等于X的数，当a[j] > X，右边的j下标就一直往左走，
当走到a[j] <= X，并且i < j，此时交换a[i]和a[j],i++。然后，从i开始向后找一个大于X的数
当a[i] <= X，此时左边的i下标就一直往右走，当走到a[i] >= X，并且i < j，此时交换a[i]和a[j], j—。
然后再从j开始，重复上面的过程，直到i >= j，完成一趟快速排序。

但是在a[i]和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 2 3 8 9 7 10，
假如此时a[i]等于5（下标i为0）和a[j]等于3（下标j为4）交换就会把元素3的稳定性打乱，
所以快速排序是一个不稳定的排序算法，不稳定发生在当前a[i]和a[j] 交换的时刻。

3、时间复杂度：

最优：O(nlog(n))

最差：O(n^2)

平均：O(nlog(n))

4、代码实现

//快速排序
- (void)quickSort:(NSMutableArray *)mutArray startIndex:(NSInteger)start endIndex:(NSInteger)end  {
    
    if (start<end) {
        
        NSInteger keyValue=[mutArray[start] integerValue];
        
        NSInteger left=start,right=end;
        
        while (start<end) {
            
            //从后往前找，如果后面的数值大于基准值，递减
            
            while (start<end&&[mutArray[end] integerValue]>keyValue) {
                
                end--;
                
            }
            
            //小于基准值的时候，给数组中索引为start赋值
            
            if (start<end) {
                
                mutArray[start]=mutArray[end];
                
                start=start+1;
                
            }
            
            //从前往后找，如果数值小于基准值，递增
            
            while (start<end&&[mutArray[start] integerValue]<keyValue) {
                
                start++;
                
            }
            
            //大于基准值，给数组中索引为end的数据赋值
            
            if (start<end) {
                
                mutArray[end]=mutArray[start];
                
                end=end-1;
                
            }
            
        }
        
        //退出的时候值start和end相等
        
        mutArray[start]=[NSString stringWithFormat:@"%ld",keyValue];
        
        [self quickSort:mutArray startIndex:left endIndex:end-1];//处理左边
        
        [self quickSort:mutArray startIndex:end+1 endIndex:right];//处理右边
    }
}

5、测试代码

NSMutableArray *dataArray = [[NSMutableArray alloc] initWithObjects:@"18",@"20",@"3",@"12",@"1",@"99",@"28", nil];
    
[self quickSort:dataArray startIndex:0 endIndex:[dataArray count]-1];

NSLog(@"快速排序:%@",dataArray);

打印结果为：
快速排序:(
    1,
    3,
    12,
    18,
    20,
    28,
    99
)