快速排序(OC和C语言)

原理分析(从小到大)：

首先取出一个key，一般取第一个元素
从后往前遍历，如果数组中的数据小于了key，那么就将从前往后未比较过的第一个位置即fisrt位置替换为该数据
然后从前往后遍历，如果数组中的数据大于了key，那么就将从后往前的第一个比较过数据位置替换
直到左右两边的位置重合，说明key就找到了正确的位置，每次循环就能找到一个数的正确位置
然后将key左右两边的数据分为两组，递归调用自己。

OC语言


- (void)viewDidLoad {
    [super viewDidLoad];

   NSLog(@"快速%@",[self quickSortWithArray:mutArr.copy]);
}

- (NSArray *)quickSortWithArray:(NSArray *)array {
    if (!array) {
        return @[];
    }
    if (array.count == 0 || array.count == 1) {
        return array;
    }
   
    NSInteger baseNumberIndex = random() % array.count;
    NSLog(@"基准数是%ld",baseNumberIndex);
    
    NSNumber *baseNumber = array[baseNumberIndex];
    NSMutableArray *unsortedArray = [array mutableCopy];
    // 移除基准数
    [unsortedArray removeObjectAtIndex:baseNumberIndex];
    NSMutableArray *leftArray = [NSMutableArray array];
    NSMutableArray *rightArray = [NSMutableArray array];
    
    for (NSNumber *curNumber in unsortedArray) {
        if (curNumber.integerValue < baseNumber.integerValue) {
            [leftArray addObject:curNumber];
        } else {
            [rightArray addObject:curNumber];
        }
    }
    
    NSMutableArray *sortedArray = [NSMutableArray array];
    [sortedArray addObjectsFromArray:[self quickSortWithArray:[leftArray copy]]];
    [sortedArray addObject:baseNumber];
    [sortedArray addObjectsFromArray:[self quickSortWithArray:[rightArray copy]]];
    
    return sortedArray;
    
}

 快速(
    1,
    7,
    10,
    15,
    37,
    90
)

C语言

#include <stdio.h>
void quickSort(int arr[], int low, int high);

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    int i;
    int a[10] = {3, 1, 11, 5, 8, 2, 0, 9, 13, 81};

    for(i = 0; i < 10; i++)
        printf("%d ", a[i]);
    printf("\n");

    quickSort(a, 0, 9);

    for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
    printf("\n");
 
    return 0;
}

void quickSort(int arr[], int low, int high)
{
    int first = low;
    int last  = high;
    int key = arr[first];
    if(low >= high)
        return;
    while(first < last)
    {
        while(first < last && arr[last] > key)
        {
            last--;
        }
        arr[first] = arr[last];

        while(first < last && arr[first] < key)
        {
            first++;
        }
        arr[last] = arr[first];
    }
   //  直到first=last，说明这个位置是基准数据的正确索引位置
    arr[first] = key;

    quickSort(arr, low, first-1);
    quickSort(arr, first+1, high);
}

Hello, World!
3 1 11 5 8 2 0 9 13 81 
0 1 2 3 5 8 9 11 13 81

参考一

参考二

最后编辑于：2020.10.26 10:03:48