ios:oc实现排序算法
下面是我用oc实现的快速排序，冒泡排序，直接插入排序和折半插入排序，希尔排序，堆排序，直接选择排序
/*******************************快速排序start**********************************/
//随即取当前取第一个，首先找到第一个的位置，然后分成left和right两组子集，分别对left和right继续执行分割(同上操作)
-(void)QuickSort:(NSMutableArray*)listStartIndex:(NSInteger)startIndexEndIndex:(NSInteger)endIndex{
if(startIndex>=endIndex)return;
NSNumber*temp=[listobjectAtIndex:startIndex];
NSIntegertempIndex=startIndex;//临时索引处理交换位置(即下一个交换的对象的位置)
for(inti=startIndex+1;i<=endIndex;i++){
NSNumber*t=[listobjectAtIndex:i];
if([tempintValue]>[tintValue]){
tempIndex=tempIndex+1;
[listexchangeObjectAtIndex:tempIndexwithObjectAtIndex:i];
}
}
[listexchangeObjectAtIndex:tempIndexwithObjectAtIndex:startIndex];
[selfQuickSort:listStartIndex:startIndexEndIndex:tempIndex-1];
[selfQuickSort:listStartIndex:tempIndex+1EndIndex:endIndex];
}
/*******************************快速排序end**********************************/
/*******************************冒泡排序start**********************************/
//取第一个与其邻接的对比，若大则交换
-(void)BubbleSort:(NSMutableArray*)list{
for(intj=1;j<=[listcount];j++){
for(inti=0;i<j;i++){
if(i==[listcount]-1)return;
NSIntegera1=[[listobjectAtIndex:i]intValue];
NSIntegera2=[[listobjectAtIndex:i+1]intValue];
if(a1>a2){
[listexchangeObjectAtIndex:iwithObjectAtIndex:i+1];
}
}
}
}
/*******************************冒泡排序end**********************************/
/*******************************直接插入排序start**********************************/
//从无序表中取出第一个元素，插入到有序表的合适位置，使有序表仍然有序
-(void)InsertSort:(NSMutableArray*)list{
for(inti=1;i<[listcount];i++){
intj=i;
NSIntegertemp=[[listobjectAtIndex:i]intValue];
while(j>0&&temp<[[listobjectAtIndex:j-1]intValue]){
[listreplaceObjectAtIndex:jwithObject:[listobjectAtIndex:(j-1)]];
//list[j]=list[j-1];
j--;
}
[listreplaceObjectAtIndex:jwithObject:[NSNumbernumberWithInt:temp]];
//list[j]=temp;
}
}
/*******************************直接插入排序end**********************************/
/*******************************折半插入排序start**********************************/
//从无序表中取出第一个元素，利用折半查找插入到有序表的合适位置，使有序表仍然有序
-(void)BinaryInsertSort:(NSMutableArray*)list{
//索引从1开始默认让出第一元素为默认有序表从第二个元素开始比较
for(inti=1;i<[listcount];i++){
//binarysearchstart
NSIntegertemp=[[listobjectAtIndex:i]intValue];
intleft=0;
intright=i-1;
while(left<=right){
intmiddle=(left+right)/2;
if(temp<[[listobjectAtIndex:middle]intValue]){
right=middle-1;
}else{
left=middle+1;
}
}
//binarysearchend
//移动3,5,6,[4]4是当前目标对象利用binarysearch找到4应该在有续集{3,5,6}的位置，然后向后移动即{3,5,6,[4]}-->{3,[4],5,6}
for(intj=i;j>left;j--){
[listreplaceObjectAtIndex:jwithObject:[listobjectAtIndex:j-1]];
}
[listreplaceObjectAtIndex:leftwithObject:[NSNumbernumberWithInt:temp]];
}
}
/*******************************折半插入排序end**********************************/
/*******************************希尔排序start**********************************/
//对直接插入排序优化，创造一个gap来对表进行分割，对分割后的每个子集进行直接插入排序知道gap＝＝1结束
-(void)shellSort:(NSMutableArray*)list{
intgap=[listcount]/2;
while(gap>=1){
for(inti=gap;i<[listcount];i++){
NSIntegertemp=[[listobjectAtIndex:i]intValue];
intj=i;
while(j>=gap&&temp<[[listobjectAtIndex:(j-gap)]intValue]){
[listreplaceObjectAtIndex:jwithObject:[listobjectAtIndex:j-gap]];
j-=gap;
}
[listreplaceObjectAtIndex:jwithObject:[NSNumbernumberWithInt:temp]];
}
gap=gap/2;
}
}
/*******************************希尔排序end**********************************/
/*******************************堆排序start**********************************/
//创建最大堆heap最大／最小优先级队列
-(void)CreateBiggestHeap:(NSMutableArray*)listCount:(NSInteger)count{
//intcount=[listcount];
intlastParentIndex=(count-2)/2;
for(inti=lastParentIndex;i>=0;i--){
NSIntegerparentIndex=i;
NSIntegerparentNode=[[listobjectAtIndex:parentIndex]intValue];
//获取左子结点为当前子结点
intcurrentChildIndex=2*i+1;
//
while(currentChildIndex<=count-1){
NSIntegerleftChildNode=[[listobjectAtIndex:(currentChildIndex)]intValue];
if((currentChildIndex+1)<=count-1){//表示存在右子结点
//读取右子结点
intrightChildIndex=currentChildIndex+1;
NSIntegerrightChildNode=[[listobjectAtIndex:(rightChildIndex)]intValue];
//如果右子结点为最大
if(rightChildNode>leftChildNode&&rightChildNode>parentNode){
[listexchangeObjectAtIndex:parentIndexwithObjectAtIndex:rightChildIndex];
currentChildIndex=rightChildIndex;//右子结点为当前子结点继续循环
//左子结点最大
}elseif(leftChildNode>rightChildNode&&leftChildNode>parentNode){
[listexchangeObjectAtIndex:parentIndexwithObjectAtIndex:currentChildIndex];
}
}else{
if(leftChildNode>parentNode){
[listexchangeObjectAtIndex:parentIndexwithObjectAtIndex:currentChildIndex];
}
}
//更新父结点和下一个子结点
parentIndex=currentChildIndex;
currentChildIndex=2*currentChildIndex+1;
}
}
}
//每次执行最大堆(索引要前移动即排除已经排好的最大堆头元算交换到list尾部的这个元素)
-(void)HeapSort:(NSMutableArray*)list{
for(inti=[listcount];i>0;i--){
[selfCreateBiggestHeap:listCount:i];
//NSLog(@"%@",list);
[listexchangeObjectAtIndex:(i-1)withObjectAtIndex:0];
}
}
/*******************************堆排序end**********************************/
/*******************************直接选择排序start**********************************/
//在对象集中选出最小的若不是第一个则与第一个交换在剩余的对象集中选出最小的执行前面的步骤
-(void)SelectSort:(NSMutableArray*)list{
for(inti=0;i<[listcount];i++){
intk=i;
for(intj=i+1;j<[listcount];j++){
NSIntegerjvalue=[[listobjectAtIndex:j]intValue];
NSIntegerkvalue=[[listobjectAtIndex:k]intValue];
if(jvalue<kvalue){
k=j;
}
}
if(k!=i){
[listexchangeObjectAtIndex:iwithObjectAtIndex:k];
}
}
}
/*******************************直接选择排序end**********************************/
相关推荐
要知道时间复杂度只是描述一个增长趋势，复杂度为O的排序算法执行时间不一定比复杂度为O长，因为在计算O时省略了系数、常数、低阶。实际上，在对小规模数据进行排序时，n2的值实际比 knlogn+c还要小。