【排序算法】快速排序

快速排序（Quick Sort）是一种常用的排序算法，它采用分而治之的策略来对一个序列进行排序。快速排序的基本思想是选择一个基准元素（通常是序列中的第一个元素），然后将序列中的其他元素分为两个子序列，一个子序列中的所有元素都比基准元素小，另一个子序列中的所有元素都比基准元素大。然后对这两个子序列递归地进行快速排序，直到所有子序列都变为有序的，此时整个序列也就变得有序了。

快速排序的步骤如下：

1. 选择基准：在数据集之中，选择一个元素作为"基准"（pivot）。
2. 分区操作：将数组进行分区（partition），将小于基准的元素移到基准的左边，将大于基准的元素移到基准的右边。分区完成后，基准元素所处的位置就是最终排序后它的位置。
3. 递归排序：递归地将小于基准元素的子序列和大于基准元素的子序列排序。

快速排序的效率在平均状况下是非常高的，其时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。最坏情况通常是由于基准元素的选择不当造成的，例如序列已经是有序的情况下，选择第一个元素作为基准。为了提高效率，有时会采用随机选择基准或者选择中位数作为基准的策略。

快速排序是一个不稳定的排序算法，因为在排序过程中，相等的元素的顺序可能会改变。

1. 找枢轴 

#include <stdio.h>
void quickSort(int * p,int low,int high)
{
    int flag = p[low];
    while(low < high)
    {
        while(p[high]>= flag && low <high)
            high--;
        if(low <high)
        {
            p[low]=p[high];
            low ++;
        }
        while(p[low]<=flag && low <high)
        low++;
        if(low <high)
        {
            p[high]=p[low];
            high--;
        }
    }
    p[low]=flag;
    printf("枢轴位置为:%d\n",low);
}

void showArr(int *p,int n)
{
    int i;
    for(i = 0;i < n;i++)
    {
        printf("%d ",p[i]);
    }
    printf("\n");
}

int main(int argc, const char *argv[])
{
    int b[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    showArr(b,15);
    quickSort(b,0,14);
    showArr(b,15);
    return 0;
}

2.快速排序最终版

#include <stdio.h>
//low 和 high 代表数组中进行快排区间段的起始和终止下标
void quickSort(int* p, int low, int high)
{
    //1.将区间段的起始位置元素作为镖旗
    int i = low;//用i保存low的值
    int j = high;//用j保存high的值
    int flag = p[low];
    //2.找枢轴
    while(low < high)
    //当循环结束的时候 low == high,此时low和high的值也就是下标位置,就是枢轴
    {
        //(1)从右向左扫描,只要p[high] >= flag,就执行high--
        while(p[high] >= flag && low < high)
            high--;
        if(low < high)
        {
            //(2)循环结束,说明遇到了p[high] < flag,需要将较小的数p[high],移动到左边
            p[low] = p[high];
            //(3)移动过来之后,从左向右扫描,执行low++,因为刚移动过来的,没必要再和flag比较
            low++;
        }
        //(4)继续从左向右扫描,只要p[low] <= flag,就执行low++
        while(p[low] <= flag && low < high)
            low++;
        if(low < high)
        {
            //(5)上面的循环结束后,说明遇到了p[low] > flag,遇到较大的数,需要移动到右侧
            p[high] = p[low];
            //(6)移动之后,从右向左扫描,执行high--,因为刚移动过来的,没必要再和flag比较
            high--;
        }
    }
    //3.将flag放在枢轴位置
    p[low] = flag;//或者 p[high] == flag
    printf("枢轴是%d %d\n",low,high);//low和high的值相等
    //4.递归对枢轴的左侧和右侧进行同样的操作
    if(i < low-1)
        quickSort(p, i, low-1);//对起始下标到枢轴-1进行递归
    if(low+1 < j)
        quickSort(p, low+1, j);//对枢轴+1到终止下标进行递归
}

void showArray(int* p, int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        printf("%d ",p[i]);
    }
    printf("\n");
}

int main(int argc, const char *argv[])
{
    int a[8] = {32, 2, 54, 6, 78, 23, 17, 76};
    showArray(a,8);
    quickSort(a,0,7);
    showArray(a,8);
    return 0;
}

结语

以上结束快速排序的基本使用，本次代码分享到此结束，后续还会分享数据结构与算法的有关知识。最后的最后，还请大家点点赞，点点关注，谢谢大家！