快速排序

快速排序的核心思路

• 快速排序利用了分治算法的思想。分治算法即分而治之，将一个大问题分解成小的子问题并逐个解决，小的子问题解决了，大问题也就解决了。
• 快速排序的核心思路：在要排序的数组中下标p到r的数据。我们则选择p到r的之间的任意一个数据作为pivot（分区点），然后遍历p到r的数据，将小于pivot的放在左边，将大于或等于pivot的放在右边，将pivot放在中间。经过这一步骤的操作后，就将p到r的数据分成了3个部分。假设pivot的坐标为q，则p到q-1的下标的数据都小于pivot，中间是pivot，q+1到r的数据都大于或等于pivot。将分割开的两个数据继续用这样的操作进行分区，直到待排序区间大小为1，则数据中所有的数据都有序了。

快速排序的操作流程

• 假设我们要对一个数组a[10]的数据进行排序。首先先选择一个分区点pivot，我们可以选择数组的第一个元素为pivot.i表示数组的第一个元素的下标0，j表示数组最后一个元素的下标n-1，即9.
• 取a[i]与pivot进行比较，如果a[i]<=pivot,则i++,继续取a[i]与pivot进行比较。如果a[i]>pivot，则将a[i]和a[j]进行位置交换。
• 交换之后取a[j]与pivot进行比较，如果a[j]>=pivot,则j--，继续取a[j]和pivot进行比较。如果a[j]<pivot，则将a[j]和a[i]进行位置交换。
• 交换之后继续按照步骤二和步骤三的要求进行操作。直到i=j,将pivot放置再a[i]的位置。则第一次的分区完成。此时数组分为了三部分a[0..i-1],a[i],a[i+1...n-1]。
• 再分别对前后两部分的数组进行选择分区点，比较大小交换位置的操作。直到分出来的前后两个部分都只有1个元素时，排序就结束了。

快速排序的相关

• 快速排序是原地排序算法，不是稳定排序算法。
• 快速排序的平均时间复杂度是O(nlogn)。
• 快速排序算法的优化主要是在选择合理的分区点上。如果分区点选择的不合理，快速排序的时间复杂度会退化成O(n²)。因此选择合理的分区点是比较重要的。主要有两种方式选择分区点。1.三数取中法。即从区间首，尾，中分别取一个数据，比较大小，取中间值为分区点。也可以五数取中，十数取中。2.随机法。即随机取一个元素作为分区点。
• 快速排序是用递归实现的。要警惕递归堆栈溢出。如何避免递归层次过深导致堆栈溢出，一般有两种方法。1.限制递归深度，一旦超过事先设定的递归深度阈值，就停止递归，改为其他排序方法。2.自己模拟实现一个函数调用栈，手动模拟递归压栈，出栈的过程。

快速排序的代码简单实现

- (void)quickSort
{
    NSMutableArray *numberArray = [NSMutableArray arrayWithArray:@[@5,@1,@6,@2,@4,@3]];
    
    NSLog(@"排序之前的结果:%@",numberArray);
    
    [self quickwithArray:numberArray withLow:0 withHigh:(int)numberArray.count-1];
    
    
    NSLog(@"排序之后的结果:%@",numberArray);
}

- (void)quickwithArray:(NSMutableArray *)array withLow:(int)low withHigh:(int)high
{
    if (low<high) {
        
        int pivot = [self quickPartitionwithArray:array withLow:low withHigh:high];
        
        [self quickwithArray:array withLow:low withHigh:pivot-1];
        
        [self quickwithArray:array withLow:pivot+1 withHigh:high];
        
    }
}

- (int)quickPartitionwithArray:(NSMutableArray *)array withLow:(int)low withHigh:(int)high
{
    NSNumber *pivotKey = array[low];
    
    while (low<high) {

        while (low<high && [array[high] intValue] >= [pivotKey intValue]) {
            
            high--;
        }
        
        array[low] = array[high];
        
        while (low<high && [array[low] intValue] <= [pivotKey intValue]) {
            
            low++;
        }
        
        array[high] = array[low];

    }
    
    array[low] = pivotKey;
    
    return low;
}