算法_快速排序算法C/C++

逃离我推掉我的手 2023-01-11 03:49 109阅读 0赞

**目录**

快速排序

1. 算法思想

2. 实现原理

3. 动态演示

4. 完整代码

5. 结果展示

6. 算法分析

--------------------

# 快速排序 #

## 1. 算法思想 ##

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

## 2. 实现原理 ##

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

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

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

## 3. 动态演示 ##

![在这里插入图片描述][20200214160149573.gif]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 4. 完整代码 ##

三个函数  
基准插入函数：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]; // 每一次执行该函数，为一个key找到正确的位置
        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;
    }

## 5. 结果展示 ##

（递归调用，不好展示每次排序结果）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

## 6. 算法分析 ##

![20210125213517781.png][]

[20200214160149573.gif]: /images/20221119/333cd92ec2b04e489918c54898546189.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190612224215809.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200319120706331.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[20210125213517781.png]: https://img-blog.csdnimg.cn/20210125213517781.png