oc 中组合排序算法,oc组合排序算法

- (NSMutableArray *)zuHeSuanFa:(NSMutableArray *)array chooseCount:(int)m
{
    int n = (int)[array count];

    if (m > n)
    {
        return nil;
    }

//    NSLog(@"从1到%d中取%d个数的组合。。。",n,m);

    NSMutableArray *allChooseArray = [[NSMutableArray alloc] init];
    NSMutableArray *retArray = [array copy];

    // (1,1,1,0,0)
    for(int i=0;i < n;i++)
    {
        if (i < m)
        {
            [array replaceObjectAtIndex:i withObject:@"1"];
        }
        else
        {
            [array replaceObjectAtIndex:i withObject:@"0"];
        }
    }

    NSMutableArray *firstArray = [[NSMutableArray alloc] init];

    for(int i=0; i<n; i++)
    {
        if ([[array objectAtIndex:i] intValue] == 1)
        {
            //            [firstArray addObject:[NSString stringWithFormat:@"%d",i+1]];
            [firstArray addObject:[retArray objectAtIndex:i]];
//            NSLog(@"%d ",i+1);
        }
    }

    [allChooseArray addObject:firstArray];
    //    [firstArray release];
//    NSLog(@"============");

    int count = 0;
    for(int i = 0; i < n-1; i++)
    {
        if ([[array objectAtIndex:i] intValue] == 1 && [[array objectAtIndex:(i + 1)] intValue] == 0)
        {
            [array replaceObjectAtIndex:i withObject:@"0"];
            [array replaceObjectAtIndex:(i + 1) withObject:@"1"];

            // i = 2, (1,1,0,1,0)

            for (int k = 0; k < i; k++)
            {
                if ([[array objectAtIndex:k] intValue] == 1)
                {
                    count ++;
                }
            }
            if (count > 0)
            {
                for (int k = 0; k < i; k++)
                {
                    if (k < count)
                    {
                        // k = 1, (1,1,0,1,0)
                        [array replaceObjectAtIndex:k withObject:@"1"];
                    }
                    else
                    {
                        [array replaceObjectAtIndex:k withObject:@"0"];
                    }
                }
            }

            NSMutableArray *middleArray = [[NSMutableArray alloc] init];

            for (int k = 0; k < n; k++)
            {
                if ([[array objectAtIndex:k] intValue] == 1)
                {
//                    NSLog(@"%d ",k+1);
                    //                    [middleArray addObject:[NSString stringWithFormat:@"%d",k + 1]];
                    [middleArray addObject:[retArray objectAtIndex:k]];
                }
            }

            [allChooseArray addObject:middleArray];
            //            [middleArray release];

//            NSLog(@"============");

            i = -1;
            count = 0;
        }
    }

    return allChooseArray;
}

 

中组合排序算法,oc组合排序算法 –
(NSMutableArray *)zuHeSuanFa:(NSMutableArray *)array chooseCount:( int
)m{ int n = ( int )[array count]; if (m n) { return nil; }…

一 冒泡排序

冒泡排序:原理:冒泡顾名思义,就像气泡从水底冒出一样,它的排序方式是:研究了一下,它给人的感觉是像近视眼一样,它只能看见自己和紧挨着自己的下一个数字,所以它的排序方式也就是将比较元素和紧挨着自己的元素比较看是否交换位置,然后持续这个过程,比较的一直都是紧挨着的两个元素。下面看代码吧,再代码里面再详细解释。

冒泡排序(Bubble
Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,故名。

由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。

冒泡排序的复杂程度:n2   算法非常稳定

-(void)buddding{

NSMutableArray * titles =[NSMutableArray
arrayWithObjects:@”23″,@”67″,@”9″,@”10″, nil];

for (int i = 0; i < titles.count; i++) {

for (int j = 0; j < titles.count – i – 1; j++) {

if ([titles[j] integerValue] > [titles[j+1] integerValue]) {

[titles exchangeObjectAtIndex:j withObjectAtIndex:j+1];

}

}

}

}

算法的优化: 我们判定上一次有没有进行排序 如果没有则说明已经排序完成

-(void)bubbling{

BOOL flag = NO;    //记录是否存在交换

NSMutableArray * titles = [NSMutableArray
arrayWithObjects:@”2″,@”3″,@”34″,@”56″,@”12″,@”22″, nil];

for (int i = 0; i < titles.count; i++) {

flag = NO ;

for (int j = 0; j < titles.count – i – 1; j++) {

if ([titles[j] integerValue] >[titles[j+1] integerValue]) {

flag = YES ;

[titles exchangeObjectAtIndex:j withObjectAtIndex:j+1];

}

}

if (flag == NO) {//退出排序

break ;

}

}

NSLog(@”–===%@”,titles);

}

2、选择排序:

实现思路:

1. 设数组内存放了n个待排数字,数组下标从1开始,到n结束。

2. i=1

3. 从数组的第i个元素开始到第n个元素,寻找最小的元素。(具体过程为:先设arr[i]为最小,逐一比较,若遇到比之小的则交换)

4. 将上一步找到的最小元素和第i位元素交换。

5. 如果i=n-1算法结束,否则回到第3步

复杂度:

平均时间复杂度:O(n^2)

平均空间复杂度:O(1)

– (void)selectionAscendingOrderSortWithArray:(NSMutableArray
*)ascendingArr

{

for (int i = 0; i < ascendingArr.count; i ++) {

for (int j = i + 1; j < ascendingArr.count; j ++) {

if ([ascendingArr[i] integerValue] > [ascendingArr[j]
integerValue]) {

int temp = [ascendingArr[i] intValue];

ascendingArr[i] = ascendingArr[j];

ascendingArr[j] = [NSNumber numberWithInt:temp];

  } }}

NSLog(@”选择升序排序后结果:%@”, ascendingArr);

}

3、快速排序:

实现思路:

1. 从数列中挑出一个元素,称为 “基准”(pivot),

2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。

3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序是基于分治模式处理的,对一个典型子数组A[p…r]排序的分治过程为三个步骤:

1.分解:

A[p..r]被划分为俩个(可能空)的子数组A[p ..q-1]和A[q+1 ..r],使得

A[p ..q-1] <= A[q] <= A[q+1 ..r]

2.解决:通过递归调用快速排序,对子数组A[p ..q-1]和A[q+1 ..r]排序。

3.合并。

递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

复杂度:

平均时间复杂度:O(n^2)

平均空间复杂度:O(nlogn)       O(nlogn)~O(n^2)

#pragma mark – 快速升序排序

– (void)quickAscendingOrderSort:(NSMutableArray *)arr
leftIndex:(NSInteger)left rightIndex:(NSInteger)right

{

if (left < right) {

NSInteger temp = [self getMiddleIndex:arr leftIndex:left
rightIndex:right];

[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp – 1];

[self quickAscendingOrderSort:arr leftIndex:temp + 1
rightIndex:right];

}

NSLog(@”快速升序排序结果:%@”, arr);

}

– (NSInteger)getMiddleIndex:(NSMutableArray *)arr
leftIndex:(NSInteger)left rightIndex:(NSInteger)right

{

NSInteger tempValue = [arr[left] integerValue];

网站地图xml地图