快速算法

一、排序算法

1、冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来

1.1 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

- (void)algorithm {
    [self bubbleSort];
    [self quickSort];
    [self selectSort];
    [self heapSelectSort];
    [self insertSort];
}

/// 冒泡算法

- (void)bubbleSort {
  NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23, @13, @42, @59, @10, @12, @18, @29, @2, @5, @30, @50]];
  for (int i = 0; i < array.count - 1; i++) {
      

      for (int j = 0; j < array.count - 1 - i; j++) {
          NSLog(@"%d  %d", i, j);
          if ([array[j] integerValue] > [array[j+1] integerValue]) {
              [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
          }
      }

  }
  NSLog(@"%@", array);
  }

/// 快速排序算法

- (void)quickSort {
  NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23, @13, @42, @59, @10, @12, @18, @29, @2, @5, @30, @50]];
  [self quickSortArray:array leftIndex:0 rightIndex:array.count - 1];
  }

- (void)quickSortArray:(NSMutableArray *)array leftIndex:(NSInteger)left rightIndex:(NSInteger)right {
  if (left > right) {
      return;
  }
  //记录比较基准数
  NSInteger temp = [array[left] integerValue];
  NSInteger i = left;
  NSInteger j = right;

  while (i < j)
  {
      /**** 首先从右边j开始查找比基准数小的值 ***/
      while ([array[j] integerValue] >= temp && i < j)
      {
          j--;
      }
      /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
      while([array[i] integerValue] <= temp && i < j)
      {
          i++;
      }

      if (i < j)
      {
          [array exchangeObjectAtIndex:j withObjectAtIndex:i];
      }

  }
  //将基准数放到正确位置
  [array exchangeObjectAtIndex:i withObjectAtIndex:left];

  /**** 递归排序 ***/
  //排序基准数左边的
  [self quickSortArray:array leftIndex:left rightIndex:i - 1];
  //排序基准数右边的
  [self quickSortArray:array leftIndex:i+1 rightIndex:right];
  NSLog(@"%@", array);
  }
  /// 直接选择排序01

- (void)selectSort {
  NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23, @13, @42, @59, @10, @12, @18, @29, @2, @5, @30, @50, @42]];
  for (int i = 0; i < array.count - 1; i++) {
      for (int j = i + 1; j < array.count; j++) {
          if ([array[i] integerValue] > [array[j] integerValue]) {
              [array exchangeObjectAtIndex:i withObjectAtIndex:j];
          }
      }
  }
  NSLog(@"%@", array);
  }

/// 直接选择排序02(堆栈二叉树)

- (void)heapSelectSort {
  NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23, @13, @42, @59, @10, @12, @18, @29, @2, @5, @30, @50, @42]];
  //循环建立初始堆
  for (NSInteger i = array.count * 0.5; i >= 0; i--) {
      [self heapAdjustWithArray:array parentIndex:i length:array.count];
  }
  //进行n-1次循环，完成排序
  for (NSInteger j = array.count - 1; j > 0; j--) {
      //最后一个元素和第一个元素进行交换
      [array exchangeObjectAtIndex:j withObjectAtIndex:0];
      //筛选R[0]结点，得到i-1个结点的堆
      [self heapAdjustWithArray:array parentIndex:0 length:j];
  }
  NSLog(@"堆排序升序结果是--->%@",array);
  }

- (void)heapAdjustWithArray:(NSMutableArray *)array
      parentIndex:(NSInteger)parentIndex
           length:(NSInteger)length {
  NSInteger temp = [array[parentIndex] integerValue]; //temp保存当前父结点
  NSInteger child = 2 * parentIndex + 1; //先获得左孩子

  while (child < length) {
      //如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
      if (child + 1 < length && [array[child] integerValue] < [array[child + 1] integerValue]) {
          child++;
      }
      

      //如果父结点的值已经大于孩子结点的值，则直接结束
      if (temp >= [array[child] integerValue]) {
          break;
      }
      
      //把孩子结点的值赋值给父结点
      array[parentIndex] = array[child];
      
      //选取孩子结点的左孩子结点，继续向下筛选
      parentIndex = child;
      child = 2 * child + 1;

  }
  array[parentIndex] = @(temp);
  }
  /// 插入排序

- (void)insertSort {
  NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23, @13, @42, @59, @10, @12, @18, @29, @2, @5, @30, @50, @42]];
  NSInteger j;
  for (NSInteger i = 1; i < array.count; i++) {
  //取出每一个待插入的数据，从array[1]开始查找
  NSInteger temp = [array[i] integerValue];
  for (j = i - 1; j >= 0 && temp < [array[j] integerValue]; j--) {
          //如果之前的数比temp大，就将这个数往后移动一个位置，留出空来让temp插入，和整理扑克牌类似
          array[j + 1] = array[j];
          array[j] = @(temp);
      }
  }
  NSLog(@"插入排序结果是--->%@",array);
  }