C语言算法：快速排序-2020-08-24-周一

简介

在排序算法中，快速排序可以说是知名度最高的，很容易就能遇到，晚上的文章也很多。
C语言实现----快速排序

1. 交换

需要调整元素顺序，就涉及到数组元素的交互。
下面的函数就是数组中两个不同下标元素的交换。

// 交换数组不同下标对应的两个值
void swap(int array[], int i, int j) {
    int temp = array[I];
    array[i] = array[j];
    array[j] = temp;
}

2. 元素划分

以第1个元素为基准，进行元素划分：

• 大于基准的元素到右边；

• 小于基准的元素到左边；

• 基准元素的排序就完成了；一次元素划分，就能排好一个元素。

// 一次数据划分：以第1个元素为基准，大的放右边，小的放左边，返回分界点的位置；
int patition (int array[], int low, int high) {
    // 以第1个元素作为基准
    int base = array[low];
    
    // 这里的low、high是形参，数值改变不影响实参本身
    while (low < high) {
        // 大于基准的数放右边
        while ((low < high) && base <= array[high]) {
            high--;
        }
        swap(array, low, high);
        
        // 小于基准的数放左边
        while ((low < high) && base >= array[low]) {
            low++;
        }
        swap(array, low, high);
    }
    
    // 返回数据划分之后，基准数所在的下标。时low == high
    return low;
}

3. 递归

完成了一次元素划分之后，对于左右两个子数组继续进行元素划分，直到排序完成。

// 快速排序
void quickSort(int array[], int low, int high) {
    // 递归调用
    // 退出条件：low == high，意味着所有元素都排好了
    if (low < high) {
        // 调用1次划分，就排好了1个元素。返回基准数所在的下标，用来划分左右子数组
        int baseIndex = patition(array, low, high);
        // 分而治之，左边
        quickSort(array, low, baseIndex - 1);
        // 分而治之，右边
        quickSort(array, baseIndex + 1, high);
    }
}

测试代码

- (IBAction)quickButtonTouched:(id)sender {
    int a[10] = {30, 20, 60, 40, 90, 30, 80, 10, 50, 80};
    int low = 0;
    int high = 9;
    quickSort(a, low, high);
    for (int i = 0; i < 10; i++) {
        printf("%d,", a[I]);
    }
}

打印结果

image.png

demo地址

https://gitee.com/zhangxusong888/ObjectCDemo/tree/master/AlgorithmDemo/AlgorithmDemo/Ctype