iOS 흔 한 알고리즘 및 응용 지식 요약

알고리즘 비교
키워드
2 점귀속
분 치
거 슬러 올라가다
거품 정렬
사상:두 번 의 순환,바깥쪽 은 순환 횟수 의 통제,내부 순환,데이터 간 의 비교,큰 데이터 의 상승(침하)을 실시한다.

#pragma mark - Objective-C
//    
- (void)bubbleSort:(id)array{
  if (!([array isKindOfClass:[NSArray class]] || [array isKindOfClass:[NSMutableArray class]])) {
    NSLog(@"           ");
    return;
  }
  NSMutableArray *tmpArr;
  if ([array isKindOfClass:[NSMutableArray class]]) {
    tmpArr = array;
  }else{
    tmpArr = [array mutableCopy];
  }
  for (int i = 0; i<tmpArr.count; i++) {
    for (int j = 0; j < tmpArr.count -1; j++) {
      if ([tmpArr[j] compare:tmpArr[j+1]] == NSOrderedDescending) {
        [tmpArr exchangeObjectAtIndex:i withObjectAtIndex:j+1];
      }
    }
  }
  NSLog(@"       :%@/n",tmpArr);
}

#pragma mark - C
//    
void bubble_sort(int arr[], const int size){
  for (int i = 0; i < size; i++) {
    for (int j = 0; j<size -1 ; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr[j], arr[j+1]);
      }
    }
  }
}

void swap(int i,int j){
  i = i + j;
  j = i - j;
  i = i - j;
}

빠 른 정렬
사상:(빠 른 정렬 은'2 점'이라는 사상 을 바탕 으로)수열 에서 하나의 요 소 를 기준 으로 하고 수열 을 다시 정렬 합 니 다.모든 요 소 는 기준 치보다 작은 것 을 기준 앞 에 놓 고 모든 요 소 는 기준 치보다 큰 것 을 기준 뒤에 놓 습 니 다.(같은 수 는 임 의 한 쪽 에 놓 을 수 있 습 니 다.이 구역 에서 탈퇴 한 후에...이 기준 은 수열 의 중간 위치 에 있 으 며,재 귀적 으로 기준 치 요소 보다 작은 하위 수열 과 기준 치 요소 보다 큰 하위 수열 을 정렬 합 니 다.

/**
     
 @param array     
 @param low             
 @param high             
 */
- (void)quickSort:(NSMutableArray*)array low:(int)low high:(int)high{
  
  if (array == nil || array.count == 0) {
    return;
  }
  if (low >= high) {
    return;
  }
  //   
  int middle = low + (high - low)/2;
  NSNumber *prmt = array[middle];
  int i = low;
  int j = high;
  
   //    ，  left<prmt   right>prmt
  while (i <= j) {
//    while ([array[i] compare:prmt] == NSOrderedAscending) {
//      i++;
//    }
    while ([array[i] intValue] < [prmt intValue]) {
      i++;
    }
//    while ([array[j] compare:prmt] == NSOrderedDescending)
    while ([array[j] intValue] > [prmt intValue]) {
      j--;
    }
    
    if(i <= j){
      [array exchangeObjectAtIndex:i withObjectAtIndex:j];
      i++;
      j--;
    }
  }
  
  if (low < j) {
    [self quickSort:array low:low high:j];
  }
  if (high > i) {
    [self quickSort:array low:i high:high];
  }
}

//    
int a[101],n;//      ，              
void quicksort(int left,int right)
{
  int i,j,t,temp;
  if(left>right)
    return;
  
  temp=a[left]; //temp        
  i=left;
  j=right;
  while(i!=j){
    //     ，        
    while(a[j]>=temp && i<j)
      j--;
    //     
    while(a[i]<=temp && i<j)
      i++;
    //            
    if(i<j){
      t=a[i];
      a[i]=a[j];
      a[j]=t;
    }
  }
  //        
  a[left]=a[i];
  a[i]=temp;
  
  quicksort(left,i-1);//       ，          
  quicksort(i+1,right);//        ，          
}

정렬 선택
사상:먼저 정렬 되 지 않 은 서열 에서 최소 요 소 를 찾 아 정렬 서열 의 시작 위치 에 저장 한 다음 에 나머지 정렬 되 지 않 은 요소 에서 최소 요 소 를 계속 찾 은 다음 에 정렬 서열 의 끝 에 두 고 이런 식 으로 모든 요소 가 정렬 이 끝 날 때 까지 유추 합 니 다.
큰 칼럼 iOS 흔 한 알고리즘 및 응용 s="line">6

- (void)selectSort:(NSMutableArray *)array
{
  if(array == nil || array.count == 0){
    return;
  }
  
  int min_index;
  for (int i = 0; i < array.count; i++) {
    min_index = i;
    for (int j = i + 1; j<array.count; j++) {
      if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
        [array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
      }
    }
  }
}

삽입 정렬
사상:첫 번 째 요소 부터 이 요 소 는 정렬 되 었 다 고 볼 수 있 습 니 다.다음 요 소 를 꺼 내 고 정렬 된 요소 서열 에서 뒤로 스 캔 할 수 있 습 니 다.만약 에 이 요소(정렬 된)가 새로운 요소 보다 크 면 이 요 소 를 다음 위치 로 옮 기 고 상기 절 차 를 반복 합 니 다.정렬 된 요소 가 새 요소 보다 작 거나 같은 위 치 를 찾 을 때 까지.이 위치 에 새 요 소 를 삽입 합 니 다.

- (void)inserSort:(NSMutableArray *)array
{
  if(array == nil || array.count == 0){
    return;
  }
  
  for (int i = 0; i < array.count; i++) {
    NSNumber *temp = array[i];
    int j = i-1;
    
    while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
      [array replaceObjectAtIndex:j+1 withObject:array[j]];
      j--;
    }
    
    [array replaceObjectAtIndex:j+1 withObject:temp];
  }
}

힐(셸)정렬
사상:먼저 전체 대기 기록 서열 을 여러 개의 하위 서열 로 나 누 어 각각 정렬 을 직접 삽입 하고 전체 서열 의 기록 이'기본 질서'가 있 을 때 전체 에 대해 직접 정렬 을 삽입 합 니 다.
최적화:힐 정렬 은 정렬 을 삽입 하 는 다음 과 같은 두 가지 특성 을 바탕 으로 하 는 개선 방법 입 니 다.
(1)삽입 정렬 은 거의 정렬 된 데이터 작업 을 할 때 효율 이 높 고 선형 정렬 의 효율 도 달성 할 수 있다.
(2)그러나 정렬 을 삽입 하 는 것 은 일반적으로 비효 율 적 입 니 다.정렬 을 삽입 할 때마다 데 이 터 를 한 명 만 이동 할 수 있 기 때 문 입 니 다.
OC 코드 구현:

//    ,   dk  array.count/2
- (void)ShellSort:(NSMutableArray *)array dk:(int)dk
{
  
  if(array == nil || array.count == 0||dk>=array.count){
    return;
  }
  
  for (int i = 0; i < array.count; i ++) {
    NSNumber *temp = array[i];
    int j = i - dk;
    
      //  i     i-1  ，    。    ，        
      while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
        [array replaceObjectAtIndex:j+dk withObject:array[j]];
        j-=dk;
      }
      [array replaceObjectAtIndex:j+dk withObject:temp];
    
  }
  
  while (dk>=1) {
    dk = dk/2;
    [self ShellSort:array dk:dk];
  }
}

실제 응용
압축 그림

+(NSData *)compressImage:(UIImage *)image toByte:(NSUInteger)maxLength
{
  // Compress by quality
  CGFloat compression = 1;
  NSData *data = UIImageJPEGRepresentation(image, compression);
  if (data.length < maxLength) return data;
  //         
  CGFloat max = 1;
  CGFloat min = 0;
  for (int i = 0; i < 6; ++i) {
    compression = (max + min) / 2;
    data = UIImageJPEGRepresentation(image, compression);
    if (data.length < maxLength * 0.9) {
      min = compression;
    } else if (data.length > maxLength) {
      max = compression;
    } else {
      break;
    }
  }
  UIImage *resultImage = [UIImage imageWithData:data];
  if (data.length < maxLength) return data;
  
  // Compress by size
  NSUInteger lastDataLength = 0;
  while (data.length > maxLength && data.length != lastDataLength) {
    lastDataLength = data.length;
    CGFloat ratio = (CGFloat)maxLength / data.length;
    CGSize size = CGSizeMake((NSUInteger)(resultImage.size.width * sqrtf(ratio)),
                 (NSUInteger)(resultImage.size.height * sqrtf(ratio))); // Use NSUInteger to prevent white blank
    UIGraphicsBeginImageContext(size);
    [resultImage drawInRect:CGRectMake(0, 0, size.width, size.height)];
    resultImage = UIGraphicsGetImageFromCurrentImageContext();
    UIGraphicsEndImageContext();
    data = UIImageJPEGRepresentation(resultImage, compression);
  }
  
  return data;
}

+(NSData *)compressImage:(UIImage *)image
{
  NSData *data=UIImageJPEGRepresentation(image, 1.0);
  if (data.length>300*1024) {
    
    if (data.length>1024*1024) {//1M    
      
      data=UIImageJPEGRepresentation(image, 0.5);
      
    }else if (data.length>300*1024) {//0.5M-1M
      
      data=UIImageJPEGRepresentation(image, 0.8);
      
    }
  }
  return data;
}

이상 은 이번 소개 의 모든 지식 포인트 내용 입 니 다.여러분 의 학습 과 우리 에 대한 지지 에 감 사 드 립 니 다.