快速排序详解

谁践踏了优雅 2022-09-25 13:21 138阅读 0赞

**基本概念：**  
快速排序是一种分治的排序算法，由C. A. R. Hoare在1962年提出。  
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
  
  
**如何切割成两部分：**  
a) 假设有两个指针low和high,它们的初值分别为low和high  
b) 设关键值为key（通常取第一个值，但选点也会影响效率，可以用头尾中三个值的中间值作为取点）  
c) 首先从high所指位置起往前搜索找到第一个比key小的值，和key交换  
d) 然后从low所指位置起往后搜索找到第一个比key大的值，和key交换  
e) 重复c/d这两步直至low=high为止

**复杂度：**

最差时间复杂度 **(n²)**

最优时间复杂度 **(nlogn)**

平均时间复杂度 **(nlogn)**

平均空间复杂度**（logn）**  
  
**动态图：**  
![20160911001451670][]  
  
  
**简单例子：  
  
  
切割流程：**  
![20160911001412807][]  
  
  
**源码：**

#include <stdio.h>
    
    /* 切分数组 */
    int partition(int a[], int first, int last)
    {
        int i = first;
        int j = last;
    
        int key = a[first]; /* 用第一个值作为关键值 */
        printf("the key is %d; ", key);
    
        while (i < j) {
            /* 从右往左比较 */
            while (i < j && a[j] >= key) {
                --j; /* 向前找 */
            }
            a[i] = a[j]; /* 将比关键值小的移到低端 */
    
            /* 从左往右比较 */
            while (i < j && a[i] <= key) {
                ++i; /* 向后找 */
            }
            a[j] = a[i]; /* 将比关键值大的移到高端 */
        }
    
        /* 此时i == j，更改为关键值 */
        a[i] = key;
    
        /* 打印合并后的数据 */
        int k;
        for (k = first; k <= last; ++k)
            printf("%d ", a[k]);
        printf("\n");
    
        return i; /* 返回关键值位置 */
    }
    
    /* 递归方式 */
    void sort(int a[], int first, int last)
    {
        if (a != NULL && first < last) {
            int key = partition(a, first, last);
            sort(a, first, key-1);
            sort(a, key+1, last);
        }
    }
    
    int main()
    {
        int arr[] = {49, 38, 65, 97, 76, 13, 27};
        int size = sizeof(arr) / sizeof(int);
    
        //sort
        sort(arr, 0, size - 1);
    
        //print
        int i = 0;
        printf("end sort: ");
        for (i; i < size; ++i) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    
        return 0;
    }

**编译运行：**  
![SouthEast][]  
  
  
  
原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52498220][http_blog.csdn.net_daiyudong2020_article_details_52498220]  
  
  
  
End;

[20160911001451670]: /images/20220717/ffe1fa55721443eb8382c420a706c338.png
[20160911001412807]: /images/20220717/b23f6498c3cf42d5806d389358209e33.png
[SouthEast]: /images/20220717/8ea473e66ee04a24826c683ddac997b3.png
[http_blog.csdn.net_daiyudong2020_article_details_52498220]: http://blog.csdn.net/daiyudong2020/article/details/52498220