关于c++:快速排序算法CC

5次阅读

共计 2735 个字符，预计需要花费 7 分钟才能阅读完成。

算法思维

疾速排序的根本思维：通过一趟排序将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则可别离对这两局部记录持续进行排序，以达到整个序列有序。

实现原理

2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
2.2、整个数组找基准正确地位，所有元素比基准值小的摆放在基准后面，所有元素比基准值大的摆在基准的前面

默认数组的第一个数为基准数据，赋值给 key，即 key=array[low]。
因为默认数组的第一个数为基准，所以从前面开始向前搜寻（high–），找到第一个小于 key 的 array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；完结时 array[high] < key）
此时从后面开始向后搜寻（low++），找到第一个大于 key 的 array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；完结时 array[low] > key）
循环 2-3 步骤，直到 low=high，该地位就是基准地位。
把基准数据赋给以后地位。

2.3、第一趟找到的基准地位，作为下一趟的分界点。
2.4、递归调用（recursive）分界点前和分界点后的子数组排序，反复 2.2、2.3、2.4 的步骤。
2.5、最终就会失去排序好的数组。

动静演示

残缺代码

三个函数
基准插入函数：int getStandard(int array[],int low,int high)
（返回基准地位下标）
递归排序函数：void quickSort(int array[],int low,int high)
主函数：int main()

`#include <stdio.h>
#include <stdlib.h>

void display(int* array, int size) {for (int i = 0; i < size; i++) {printf("%d", array[i]);
    }
    printf("n");
}

int getStandard(int array[], int i, int j) {
    // 基准数据
    int key = array[i];
    while (i < j) {
        // 因为默认基准是从右边开始，所以从左边开始比拟
        // 当队尾的元素大于等于基准数据 时, 就始终向前移动 j 指针
        while (i < j && array[j] >= key) {j--;}
        // 当找到比 array[i] 小的时，就把前面的值 array[j] 赋给它
        if (i < j) {array[i] = array[j];
        }
        // 当队首元素小于等于基准数据 时, 就始终向后移动 i 指针
        while (i < j && array[i] <= key) {i++;}
        // 当找到比 array[j] 大的时，就把后面的值 array[i] 赋给它
        if (i < j) {array[j] = array[i];
        }
    }
    // 跳出循环时 i 和 j 相等, 此时的 i 或 j 就是 key 的正确索引地位
    // 把基准数据赋给正确地位
    array[i] = key;
    return i;
}

void QuickSort(int array[], int low, int high) {
    // 开始默认基准为 low
    if (low < high) {
        // 分段地位下标
        int standard = getStandard(array, low, high);
        // 递归调用排序
        // 右边排序
        QuickSort(array, low, standard - 1);
        // 左边排序
        QuickSort(array, standard + 1, high);
    }
}

// 合并到一起疾速排序
// void QuickSort(int array[], int low, int high) {//     if (low < high) {
//         int i   = low;
//         int j   = high;
//         int key = array[i];
//         while (i < j) {//             while (i < j && array[j] >= key) {
//                 j--;
//             }
//             if (i < j) {//                 array[i] = array[j];
//             }
//             while (i < j && array[i] <= key) {
//                 i++;
//             }
//             if (i < j) {//                 array[j] = array[i];
//             }
//         }
//         array[i] = key;
//         QuickSort(array, low, i - 1);
//         QuickSort(array, i + 1, high);
//     }
// }

int main() {int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    int size    = sizeof(array) / sizeof(int);

    // 打印数据
    printf("%d n", size);
    QuickSort(array, 0, size - 1);
    display(array, size);

    // int size      = 20;
    // int array[20] = {0};                 // 数组初始化
    // for (int i = 0; i < 10; i++) {       // 数组个数
    //     for (int j = 0; j < size; j++) { // 数组大小
    //         array[j] = rand() % 1000;    // 随机生成数大小 0~999
    //     }
    //     printf("原来的数组：");
    //     display(array, size);
    //     QuickSort(array, 0, size - 1);
    //     printf("排序后数组：");
    //     display(array, size);
    //     printf("n");
    // }

    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25
*   26
*   27
*   28
*   29
*   30
*   31
*   32
*   33
*   34
*   35
*   36
*   37
*   38
*   39
*   40
*   41
*   42
*   43
*   44
*   45
*   46
*   47
*   48
*   49
*   50
*   51
*   52
*   53
*   54
*   55
*   56
*   57
*   58
*   59
*   60
*   61
*   62
*   63
*   64
*   65
*   66
*   67
*   68
*   69
*   70
*   71
*   72
*   73
*   74
*   75
*   76
*   77
*   78
*   79
*   80
*   81
*   82
*   83
*   84
*   85
*   86
*   87
*   88
*   89
*   90
*   91
*   92
*   93
*   94
*   95
*   96
*   97
*   98
*   99
*   100
*   101
*   102