/*******************************快速排序 start**********************************/
//随即取 当前取第一个，首先找到第一个的位置，然后分成left和right两组子集 ，分别对left和right继续执行分割(同上操作)-(void)QuickSort:(NSMutableArray *)list StartIndex:(NSInteger)startIndex EndIndex:(NSInteger)endIndex{ if(startIndex >= endIndex)return; NSNumber * temp = [list objectAtIndex:startIndex]; NSInteger tempIndex = startIndex; //临时索引 处理交换位置(即下一个交换的对象的位置) for(int i = startIndex + 1 ; i <= endIndex ; i++){ NSNumber *t = [list objectAtIndex:i]; if([temp intValue] > [t intValue]){ tempIndex = tempIndex + 1; [list exchangeObjectAtIndex:tempIndex withObjectAtIndex:i]; } } [list exchangeObjectAtIndex:tempIndex withObjectAtIndex:startIndex]; [self QuickSort:list StartIndex:startIndex EndIndex:tempIndex-1]; [self QuickSort:list StartIndex:tempIndex+1 EndIndex:endIndex];}/*******************************快速排序 end**********************************//*******************************冒泡排序 start**********************************///取第一个 与其邻接的对比，若大则交换-(void)BubbleSort:(NSMutableArray *)list{ for (int j = 1; j<= [list count]; j++) { for(int i = 0 ;i < j ; i++){ if(i == [list count]-1)return; NSInteger a1 = [[list objectAtIndex:i] intValue]; NSInteger a2 = [[list objectAtIndex:i+1] intValue]; if(a1 > a2){ [list exchangeObjectAtIndex:i withObjectAtIndex:i+1]; } } } }/*******************************冒泡排序 end**********************************//*******************************直接插入排序 start**********************************///从无序表中取出第一个元素，插入到有序表的合适位置，使有序表仍然有序-(void)InsertSort:(NSMutableArray *)list{ for(int i = 1 ; i < [list count] ; i++){ int j = i; NSInteger temp= [[list objectAtIndex:i] intValue]; while (j > 0 && temp < [[list objectAtIndex:j - 1]intValue]) { [list replaceObjectAtIndex:j withObject:[list objectAtIndex:(j-1)]]; //list[j] = list[j-1]; j--; } [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:temp]]; //list[j] = temp; } }/*******************************直接插入排序 end**********************************//*******************************折半插入排序 start**********************************///从无序表中取出第一个元素，利用折半查找插入到有序表的合适位置，使有序表仍然有序-(void)BinaryInsertSort:(NSMutableArray *)list{ //索引从1开始 默认让出第一元素为默认有序表 从第二个元素开始比较 for(int i = 1 ; i < [list count] ; i++){ //binary search start NSInteger temp= [[list objectAtIndex:i] intValue]; int left = 0; int right = i - 1; while (left <= right) { int middle = (left + right)/2; if(temp < [[list objectAtIndex:middle] intValue]){ right = middle - 1; }else{ left = middle + 1; } } //binary search end //移动3,5,6,[4] 4是当前目标对象 利用binarysearch 找到4应该在有续集{3,5,6}的位置，然后向后移动即{3,5,6,[4]}-->{3,[4],5,6} for(int j = i ; j > left; j--){ [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-1]]; } [list replaceObjectAtIndex:left withObject:[NSNumber numberWithInt:temp]]; } }/*******************************折半插入排序 end**********************************//*******************************希尔排序 start**********************************///对直接插入排序优化，创造一个gap 来对表进行分割，对分割后的每个子集进行直接插入排序 知道gap＝＝1结束-(void)shellSort:(NSMutableArray *)list{int gap = [list count] / 2;
while (gap >= 1) { for(int i = gap ; i < [list count]; i++){ NSInteger temp = [[list objectAtIndex:i] intValue]; int j = i; while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) { [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]]; j -= gap; } [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:temp]]; } gap = gap / 2; }}
/*******************************希尔排序 end**********************************/
/*******************************堆排序 start**********************************/
//创建最大堆heap 最大／最小优先级队列-(void)CreateBiggestHeap:(NSMutableArray *)list Count:(NSInteger)count{ //int count = [list count]; int lastParentIndex = (count - 2)/2; for(int i = lastParentIndex; i >= 0 ; i--){ NSInteger parentIndex = i; NSInteger parentNode = [[list objectAtIndex:parentIndex] intValue]; //获取左子结点为当前子结点 int currentChildIndex = 2*i + 1; // while (currentChildIndex <= count - 1) { NSInteger leftChildNode = [[list objectAtIndex:(currentChildIndex)] intValue]; if((currentChildIndex + 1) <= count-1){//表示存在右子结点 //读取右子结点 int rightChildIndex =currentChildIndex + 1; NSInteger rightChildNode = [[list objectAtIndex:(rightChildIndex)] intValue]; //如果右子结点为最大 if(rightChildNode > leftChildNode && rightChildNode > parentNode){ [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:rightChildIndex]; currentChildIndex = rightChildIndex;//右子结点为当前子结点 继续循环 //左子结点最大 }else if(leftChildNode > rightChildNode && leftChildNode > parentNode){ [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:currentChildIndex]; } }else{ if(leftChildNode > parentNode){ [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:currentChildIndex]; } } //更新父结点和下一个子结点 parentIndex = currentChildIndex; currentChildIndex = 2*currentChildIndex + 1; } } }//每次执行最大堆(索引要前移动 即排除已经排好的最大堆头元算 交换到list尾部的这个元素)-(void)HeapSort:(NSMutableArray *)list{ for(int i = [list count] ; i > 0; i--){ [self CreateBiggestHeap:list Count:i]; //NSLog(@"%@",list); [list exchangeObjectAtIndex:(i-1) withObjectAtIndex:0]; } } /*******************************堆排序 end**********************************//*******************************直接选择排序 start**********************************/
//在对象集中选出最小的 若不是第一个 则与第一个交换 在剩余的对象集中选出最小的 执行前面的步骤-(void)SelectSort:(NSMutableArray *)list{ for(int i = 0 ; i<[list count]; i++){ int k = i; for(int j = i+1 ; j<[list count]; j++){ NSInteger jvalue = [[list objectAtIndex:j] intValue]; NSInteger kvalue = [[list objectAtIndex:k] intValue]; if(jvalue < kvalue){ k = j; } } if(k != i){ [list exchangeObjectAtIndex:i withObjectAtIndex:k]; } } }/*******************************直接选择排序 end**********************************/