快速排序,冒泡排序,选择排序

zhouu

- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *array = [NSMutableArray array];
//int x = arc4random() % 100;---- 表示 [0, 100)
static int num = 100;
for (int i = 0;i < num; i++) {
u_int32_t x = arc4random() % num;
NSNumber *num = [[NSNumber alloc] initWithInt:x];
[array addObject:num];
}
[self sort:array left:0 right:array.count - 1];
NSLog(@"%@",array);
}




- (void)sort:(NSMutableArray *)arr left:(NSInteger)left right:(NSInteger)right {
if (left >= right) {
return;
}
NSInteger i = left;
NSInteger j = right;
NSInteger point = [arr[left] integerValue];  // 取最左边的元素
while(i != j){
while (i < j && point <= [arr[j] integerValue]) {
j --;
}
while (i < j && point >= [arr integerValue]) {
i ++;
}
if (i < j) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
[arr exchangeObjectAtIndex:i withObjectAtIndex:left]; // i++变化了
[self sort:arr left:left right:i - 1];
[self sort:arr left:i + 1 right:right];
}

• 步骤
  
  
  
  • 参数：可变数组，left0,right count-1
    
  • i = left j = right point = arr[left]
    
  • while （i != j）
    
    
    
    • while(i<j && point <=arr[j])
      
      
      
      • j—
        
      
      
    • while(i<j && point >= arr)
      
      
      
      • i++
        
      
      
    • if i<j
      
      
      
      • arr exchange i,j
        
      
      
    
    
  • arr exchange i left
    
  • self 调用这个方法 left i+1 right :right
    
  • self 调用这个方法 left left right：i-1
    
  • if(left >=right)return
    
  • 
    
    
  • 参考　　http://developer.51cto.com/art/201403/430986.htm
    
    
  • 参考　　http://www.jianshu.com/p/bfa34c56ffaa
    
    
  
  

　　冒泡排序和选择排序:
　　冒泡:



- (void)bubleSort:(NSMutableArray *)arr{ // j j 比较
for (int i = 0; i < arr.count; i ++) {
for (int j = 0; j < arr.count - 1; j++) {
if (arr[j] >= arr[j+1]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡排序-%@",arr);
}
　　选择:



- (void)selectSort:(NSMutableArray *)arr { // i j比较
for (int i = 0 ; i < arr.count; i ++) {
for (int j = i+1; j < arr.count; j++) {
NSInteger temp = [arr integerValue];
if (arr >= arr[j]) {
arr = arr[j];
arr[j] = [NSNumber numberWithInteger:temp];
}
}
}
NSLog(@"选择排序-%@",arr);
}
　　区别在于:
　　冒泡排序比较   j 和 j+1
　　选择排序比较   i 和 j
　　冒泡排序内层遍历条件 for(int j = 0;j<count -1;j++) 因为比较的是j和j+1 ,小于count -1就行了
　　选择排序内层遍历条件for(int j = i+1; j<count; j++) 因为比较的是i和j