算法-冒泡排序和快速排序

简介:

冒泡和递归一样,不管大家水平怎么样,基本上都能凑合的写写,快速排序其实主要的也是数据的交换,都算是交换排序,不过快排需要了解分治思想,实现的时候需要递归一下,导致很多时候看快排的时候都看的云里雾里。假设有一个无序的整型数组

索引  0     1     2    3     4      5     6

数值  15   32    8    99   12  17  36,

①取出0位的15作为基准值,然后倒序从后往前找小于15的,将12赋值给0位;

②从前往后找大于15的将32放置到位置4;

③位置1空出来,然后继续倒序找小于15的,正序找大于15的,最后索引到大3的时候重复以上过程。

冒泡排序

冒泡基本上没有什么好说的,直接看代码吧,新建了Sort类处理排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
//  Sort.h
//  Algorithm
//http://www.cnblogs.com/xiaofeixiang
//  Created by keso on 15/3/15.
//  Copyright (c) 2015年 keso. All rights reserved.
//
 
#import <Foundation/Foundation.h>
 
@interface  Sort :  NSObject
 
@property  ( nonatomic ,strong) NSMutableArray  *dataSource;
 
-( void )bubbleSort:( NSMutableArray *)dataSource;
 
-( void )quickSort:( NSInteger )start endIndex:( NSInteger )end;
 
@end

 Sort.m中的bubbleSort实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//冒泡排序
-( void )bubbleSort:( NSMutableArray *)dataSource{
     
     NSUInteger  count=[dataSource count];
     for ( int  i=0;i<count;i++){
         
         for  ( int  j=0; j<count-i-1;j++) {
             
             if  ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {
                 
                 
                 NSString   *temp=dataSource[j];
                 
                 dataSource[j]=dataSource[j+1];
                 
                 dataSource[j+1]=temp;
             }
         }
     }
     for  ( NSInteger  i=0; i<[dataSource count]; i++) {
         NSLog (@ "排序--%@" ,dataSource[i]);
     }
}

 冒泡排序比较稳定,但是每次只是移动两个数字比较慢,如果是正序的话时间复杂度是O(n),如果是逆序的需要弄成正序的,那么事件复杂度O(n*n),会经过n(n-1)/2次比较,平均事件复杂度O(n*n),这里面其实有一个问题就是无法通过以上代码理解冒泡最好情况情况的时间复杂度为O(n),其实加一个标记为就可以啦:

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
-( void )bubbleSort:( NSMutableArray *)dataSource{
     
     NSUInteger  count=[dataSource count];
     NSInteger  test=0;
     Boolean swapflag;
     NSInteger  swapCount=0,moveCount=0;
     for ( int  i=0;i<count;i++){
         swapflag= false ;
         for  ( int  j=0; j<count-i-1;j++) {
           
             //关键字移动的次数,如果你知道是正序的,那么代码不应该这么写
             swapCount++;
             if  ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {
                 moveCount+=3;
                 
                 NSString   *temp=dataSource[j];
                 
                 dataSource[j]=dataSource[j+1];
                 
                 dataSource[j+1]=temp;
                 
                 swapflag= true ;
                 
             }
         }
         
         if  (swapflag== false ) {
             NSLog (@ "比较次数:%ld,移动次数:%ld" ,swapCount,moveCount);
             return ;
         }
         
     }
 
}

快速排序

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

1.先从数组中取出一个数作为基准数值,也可以理解为中间变量。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。

 快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,也算是出门居家必备的算法了,理解比较好理解,具体的实现能写出来基本上算是理解的,至于更深的就要看工作中实际的操作过程啦。

Sort.h中定义了一个QuickSort方法,还有一个NSMutabArray是为了保存最后的结果的,具体实现:

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

 主函数中的调用如下:

1
2
3
4
5
6
7
8
9
10
11
NSMutableArray  *data=[[ NSMutableArray  alloc] initWithObjects:@ "10" ,@ "88" ,@ "97" ,@ "33" ,@ "8" ,@ "73" ,@ "18" nil ];
  
  [sort bubbleSort:data];
  sort.dataSource=data;
  
  [sort quickSort:0 endIndex:[data count]-1];
  
  for  ( int  i=0; i<[data count]; i++) {
      NSLog (@ "排序:%@" ,data[i]);
  }
  return  0;

 本文转自Fly_Elephant博客园博客,原文链接:http://www.cnblogs.com/xiaofeixiang/p/4340615.html,如需转载请自行联系原作者

相关文章
|
2月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
22 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
2月前
|
搜索推荐 Java
经典排序算法---冒泡排序
这篇文章详细介绍了冒泡排序算法的基本思想、比较轮数和次数,并提供了Java语言实现冒泡排序的代码示例,展示了如何通过相邻元素的比较和交换来达到排序的目的。
经典排序算法---冒泡排序
|
2月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
3月前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
51 3
|
3月前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
25 1
|
4月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
38 3
|
4月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
4月前
|
算法 搜索推荐 JavaScript
算法学习:快速排序
算法学习:快速排序
40 1
|
3月前
|
算法 搜索推荐 C#
|
4月前
|
搜索推荐 算法 大数据
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
下一篇
无影云桌面