Objective-C中的快速排序

从小到大排序

1.假设6，1，2，7，9，3，4，5，10，8 随便找一个数，作为基数。找6作为基数。目标是将6挪到中间的某个位置k。k 就是分界点，左边都是小于6的。右边都是大于6的。交换，6和身边的数交换，如果比6大，二者就交换位置。分别记录起始位置和最终位置i和j。

2.先从右往左找到一个小于6的数，在从左往右找到一个大于6的数，然后二者交换位置。第一次是7和5换位置，所得到的新的队列是6 1 2 5 9 3 4 7 10 8 。

3.右边的j继续想前移动，发现4的时候，停下来，然后左边的i开始移动，移动到9的时候停下来，这个时候，发生第二次交换，交换的结果是 6 1 2 5 4 3 9 7 10 8

4.右边的j继续移动，发现3比6小，停下来，左边的i开始移动，结果i和j相遇了，表示此次探测结束。将基准数6和3交换，变成3 1 2 5 4 6 9 7 10 8 。

5.这个时候就是以基准数6为分界点，6左边的都小于等于6 ，6右边的都大于等于6。

6.整个过程就是j寻找基准书小于6的数，i寻找基准书大于6的数。直到i和j碰头位置。

7.此时已经将原来的序列拆分成两个序列。左边是3 1 2 5 4 ，右边是 9 7 10 8 。

8.然后处理接下来的两个序列。左边的序列，左边的序列以3为基准数，进行调整。

9.设置i在起始位置，j在末尾，j先开始向左移动，寻找小于3的数，当在2位置是，停止移动。i开始向右移动，寻找大于三的数。没有找到，结果在2的位置与j相遇了，表示此次探测结束。将基准数和2调换位置。编程2 1 3 5 4。

10.然后在处理左边的2和1 。把2作为基准数作为调整，需要调换位置编程，同理右边也是，就变成了 1 2 3 4 5 9 7 10 8 。

11.然后在对右边的9 7 10 8 进行调整，调整之后的结果是 1 2 3 4 5 6 7 8 9 10。

代码如下

  self.quickSortArray = [NSMutableArray    arrayWithObjects:@6,@1,@2,@7,@9,@3,@4,@5,@10,@8, nil];
 self.num = self.quickSortArray.count -1;
 [self quickSort:0 Right:self.num];

- (void)quickSort:(NSInteger)left Right:(NSInteger)right{
    NSInteger i = left;
    NSInteger j = right;
    if (left > right)
        return;
    NSNumber * temp = self.quickSortArray[left];
    
    while (i !=j) {
        while (self.quickSortArray[j]>=temp && i < j) {
            j--;
        }
        while (self.quickSortArray[i]<=temp && i < j) {
            i++;
        }
        NSNumber * t;
        t = self.quickSortArray[j];
        self.quickSortArray[j] = self.quickSortArray[i];
        self.quickSortArray[i] = t;
    }
    self.quickSortArray[left] = self.quickSortArray[i];
    self.quickSortArray[i] = temp;
    
    [self quickSort:left Right:i-1];
    [self quickSort:i+1 Right:right];
    
}

打印出来的结果：

2016-04-21 09:55:57.442 RLMZ[3268:180946] (
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10
)

从大到小排序###

以上面的为例，还是6，1，2，7，9，3，4，5，10，8.
1.以6为基准数，起始位置和结束为止分别用i,j来标记。首先把6基准数归位到中间的位置，把大于6的数，放到基准数的左边，小于6的数，放到基准数的右边。i,j相遇的时候，一次探测结束。结果是 9 8 10 7 6 3 4 5 2 1
2.以6为分界点，把数列分为两列，左边是大于6 。右边是小于6的。左边在以9 为基准点，继续探测。最后结果为10 9 8 7 6 。同理左边为5 4 3 2 1 。最终结果是10，9，8，7，6，5，4，3，2，1
快速排序代码从大到小代码如下：

 self.quickSortArray = [NSMutableArray arrayWithObjects:@6,@1,@2,@7,@9,@3,@4,@5,@10,@8, nil];
    self.num = self.quickSortArray.count -1;
   // [self quickSort:0 Right:self.num];
    [self quickSortLargestToSmallest:0 Right:self.num];

- (void)quickSortLargestToSmallest:(NSInteger)left Right:(NSInteger)right{
    NSInteger i = left;
    NSInteger j = right;
    if (left > right)
        return;
    NSNumber * temp = self.quickSortArray[left];
    while (i != j) {
        while (self.quickSortArray[j] <= temp && i < j) {
            j--;
        }
        while (self.quickSortArray[i] >= temp && i < j) {
            i++;
        }
        NSNumber * t;
        t = self.quickSortArray[i];
        self.quickSortArray[i] = self.quickSortArray[j];
        self.quickSortArray[j] = t;
    }
    self.quickSortArray[left] = self.quickSortArray[i];
    self.quickSortArray[i]= temp;
    
    [self quickSortLargestToSmallest:left Right:i-1];
    
    [self quickSortLargestToSmallest:i+1 Right:right];
}

打印结果：

2016-04-21 11:01:42.243 RLMZ[3570:236014] (
    10,
    9,
    8,
    7,
    6,
    5,
    4,
    3,
    2,
    1
)