Objective-C实现快速排序

2016-04-08 本文已影响1039人旅行的光

在众多的排序方法中，有一种快速排序。如果你读了我的Objective-C实现冒泡排序,那么你一定会觉得冒泡排序的实现虽然很简单，但是它的效率真的是太慢了。接下来我将介绍一种更为高效的排序方法－－快速排序。

1,什么是快速排序

快速排序由 C. A. R. Hoare(东尼·霍尔,Charles Antony Richard Hoare)在 1960 年提出,之后又有许多人做了进一步的优化。这种排序方法是基于二分的思想来实现的，简单的说就是将一个大的问题通过不断的一分为二化简为较小的问题来解决。通过二分化简了问题的规模来提高解决问题的效率。因此我们将发现快速排序的平均时间复杂度是O(nlogn),最差时间复杂度是O(n^2)。是不是发现快速排序真的很快速呢？

2,快速排序描述

快速排序图解

作者比较懒😂，图片来自《啊哈！算法》

从上面的图片我们可以发现

(1),快速排序的思想就是从无序数组中找出一个基准数，并且设定两个哨兵值分别放置于数组的左右两端。

(2),接下来我们让右边的哨兵值先向左边移动，当我们发现有值小于基准数时我们让哨兵值停下来。(因为我们的基准数找的是最左边的数，因此我们需要先移动右边的哨兵值，否则基准数将无法回到正确的位置。)

(3), 然后我们需要让左边的哨兵值向右移动，当发现数值大于基准数时停下来。

(4), 交换左右哨兵值指向的数值，继续以上的移动直到两个哨兵值指向同一个位置。

(5),将基准数与哨兵值指向的数值进行交换。这样我们就讲基准值放到了正确的位置。

(6),以基准数现在的位置为中心，将数组分为左右两部分，分别设定基准数和哨兵值。重复1到6中描述的步骤。

从以上的步骤描述当中我们将会发现，每次移动我们动能将基准数放到正确的位置，基准数比较的范围变大了，因此也提高了算法的效率。而冒泡排序每次只是比较相邻两个数的大小。

3,Objective-C实现快速排序

- (void) quickSortFromLeft:(NSInteger)leftIndex toRight:(NSInteger)rightIndex {
    
    if (leftIndex >= rightIndex) {
        return;
    }

    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    NSInteger base = [self.mutableArray[leftIndex] integerValue];
    
    
    while (i != j) {
        while ([self.mutableArray[j] integerValue] >= base && i < j) {
            j --;
        }
        while ([self.mutableArray[i] integerValue] <= base && i < j) {
            i ++;
        }
        
        if (i < j) {
            NSInteger temp = [self.mutableArray[j] integerValue];
            self.mutableArray[j] = self.mutableArray[i];
            self.mutableArray[i] = [NSNumber numberWithInteger:temp];

        }
    }
    
    NSInteger temp = [self.mutableArray[j] integerValue];
    self.mutableArray[j] = [NSNumber numberWithInteger:base];
    self.mutableArray[leftIndex] = [NSNumber numberWithInteger:temp];
    
    
    [self quickSortFromLeft:leftIndex toRight:i-1];
    [self quickSortFromLeft:i+1 toRight:rightIndex];
    
    
    
}