Demo

1************ 2****

3****

4****

• ni (1 <= i <= n)``i

n``i (1 = i <= n)

1. i = 1``i``i > 1``i / 2
2. 2i > n``i``i``2i
3. 2i + 1 > n``i``2i + 1

0

(Priority Queue)

3. ()

typedef NSComparisonResult(^JXPriorityQueueComparator)(id obj1, id obj2);

@interface JXPriorityQueue : NSObject

/// 
@property (nonatomic, copy) JXPriorityQueueComparator comparator;

/// 
- (void)enQueue:(id)element;

/// 
- (id)deQueue;

@end

- (void)enQueue:(id)element {
    // 
    [self.data addObject:element];
    
    // 
    [self swimIndex:self.tailIndex];
}

/// 
- (void)swimIndex:(NSInteger)index {
    // 
    id temp = self.data[index];
    
    // parent1/2
    for (NSInteger parentIndex = index / 2; parentIndex >= 1; parentIndex /= 2) {
        // parent
        if (self.comparator(temp, self.data[parentIndex]) != NSOrderedDescending) {
            break;
        }
        // parent
        self.data[index] = self.data[parentIndex];
        // 
        index = parentIndex;
    }
    // 
    self.data[index] = temp;
}

() 1. 2. 3. 4.

- (id)deQueue {
    if (self.count == 0) {
        return nil;
    }
    // 
    id element = self.data[1];
    // 
    [self swapIndexA:1 indexB:self.tailIndex];
    [self.data removeLastObject];
    
    if (self.data.count > 1) {
        // 
        [self sinkIndex:1];
    }
    return element;
}

/// 
- (void)swapIndexA:(NSInteger)indexA indexB:(NSInteger)indexB {
    id temp = self.data[indexA];
    self.data[indexA] = self.data[indexB];
    self.data[indexB] = temp;
}

/// 
- (void)sinkIndex:(NSInteger)index {
    // 
    id temp = self.data[index];
    
    // maxChildIndex*2
    for (NSInteger maxChildIndex = index * 2; maxChildIndex <= self.tailIndex; maxChildIndex *= 2) {
        // 
        if (maxChildIndex < self.tailIndex && (self.comparator(self.data[maxChildIndex], self.data[maxChildIndex + 1]) == NSOrderedAscending)) {
            // 
            ++ maxChildIndex;
        }
        // child
        if (self.comparator(temp, self.data[maxChildIndex]) != NSOrderedAscending) {
            break;
        }
        // 
        // 
        self.data[index] = self.data[maxChildIndex];
        // 
        index = maxChildIndex;
    }
    // 
    self.data[index] = temp;
}

(Heap Sort)

n``nlogn

NSMutableArray+JXHeapSort.h

typedef NSComparisonResult(^JXSortComparator)(id obj1, id obj2);
typedef void(^JXSortExchangeCallback)(id obj1, id obj2);
typedef void(^JXSortCutCallback)(id obj, NSInteger index);

@interface NSMutableArray (JXHeapSort)

// 
- (void)jx_heapSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback didCut:(JXSortCutCallback)cutCallback;

@end

NSMutableArray+JXHeapSort.m

@implementation NSMutableArray (JXHeapSort)

/// 
- (void)jx_heapSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback didCut:(JXSortCutCallback)cutCallback {
    // 0
    [self insertObject:[NSNull null] atIndex:0];
    
    // 
    // 
    // 
    for (NSInteger index = self.count / 2; index > 0; index --) {
        // 
        [self sinkIndex:index bottomIndex:self.count - 1 usingComparator:comparator didExchange:exchangeCallback];
    }
    
    // 
    // 
    for (NSInteger index = self.count - 1; index > 1; index --) {
        // 
        [self jx_exchangeWithIndexA:1 indexB:index didExchange:exchangeCallback];
        if (cutCallback) {
            cutCallback(self[index], index - 1);
        }
        // 
        [self sinkIndex:1 bottomIndex:index - 1 usingComparator:comparator didExchange:exchangeCallback];
    }
    
    // 
    [self removeObjectAtIndex:0];
}

/// 
- (void)sinkIndex:(NSInteger)index bottomIndex:(NSInteger)bottomIndex usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
    for (NSInteger maxChildIndex = index * 2; maxChildIndex <= bottomIndex; maxChildIndex *= 2) {
        // 
        if (maxChildIndex < bottomIndex && (comparator(self[maxChildIndex], self[maxChildIndex + 1]) == NSOrderedAscending)) {
            // 
            ++ maxChildIndex;
        }
        // 
        if (comparator(self[maxChildIndex], self[index]) == NSOrderedAscending) {
            break;
        }
        // 
        // 
        [self jx_exchangeWithIndexA:index indexB:maxChildIndex didExchange:exchangeCallback];
        // 
        index = maxChildIndex;
    }
}

/// 
- (void)jx_exchangeWithIndexA:(NSInteger)indexA indexB:(NSInteger)indexB didExchange:(JXSortExchangeCallback)exchangeCallback {
    id temp = self[indexA];
    self[indexA] = self[indexB];
    self[indexB] = temp;
    
    if (exchangeCallback) {
        exchangeCallback(temp, self[indexA]);
    }
}

@end

DemonodeArray``UILabel

@property (nonatomic, strong) NSMutableArray<UILabel *> *nodeArray;

dispatch_semaphore_t sema = dispatch_semaphore_create(0);
    
// 
NSTimer *timer = [NSTimer scheduledTimerWithTimeInterval:0.6 repeats:YES block:^(NSTimer * _Nonnull timer) {
    dispatch_semaphore_signal(sema);
}];

[self.nodeArray jx_heapSortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    // 
    return [self compareWithNodeA:obj1 nodeB:obj2];
} didExchange:^(id obj1, id obj2) {
    // 
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);
    [self exchangeNodeA:obj1 nodeB:obj2];
} didCut:^(id obj, NSInteger index) {
    // 
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);
    [self cutNode:obj index:index];
}];

UI

JXPriorityQueue JXHeapSort : JXSort