快速排序算法，C语言快速排序算法详解

1. 设置两个变量 i、j，排序开始的时候：i=0，j=n–1。
2. 以数组第一个元素为关键数据，赋给变量 key，即 key=A[0]。
3. 从 j 开始向前搜索，即由后开始向前搜索（j--），找到第一个小于 key 的值 A[j]，将 A[j] 和 A[i] 互换。
4. 然后再从 i 开始向后搜索，即由前开始向后搜索（++i），找到第一个大于 key 的 A[i]，将 A[i] 和 A[j] 互换。
5. 重复第 3、4 步，直到 i=j。此时就能确保序列中所有元素都与 key 比较过了，且 key 的左边全部是比 key 小的，key 的右边全部是比 key 大的。

35  12  37  -58  54  76  22

22  12  37  -58  54  76  35

22  12  35  -58  54  76  37

22  12  -58  35  54  76  37

# include <stdio.h>
void Swap(int *, int *);  //函数声明, 交换两个变量的值
void QuickSort(int *, int, int);  //函数声明, 快速排序
int main(void)
{
    int i;  //循环变量
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*引用起来很简单, 0为第一个元素的下标, 20为最后一个元素的下标*/
    printf("最终排序结果为:\n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
void Swap(int *p, int *q)
{
    int buf;
    buf = *p;
    *p = *q;
    *q = buf;
    return;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high说明排序结束了
    {
        return ;
    }
    while (low < high)  //该while循环结束一次表示比较了一轮
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前寻找
        }
        if (key > a[high])
        {
            Swap(&a[low], &a[high]);
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向后寻找
        }
        if (key < a[low])
        {
            Swap(&a[low], &a[high]);
            --high;
        }
    }
    QuickSort(a, i, low-1);  //用同样的方式对分出来的左边的部分进行同上的做法
    QuickSort(a, low+1, j);  //用同样的方式对分出来的右边的部分进行同上的做法
}

# include <stdio.h>
void QuickSort(int *, int, int);  /*现在只需要定义一个函数, 不用交换还省了一个函数, 减少了代码量*/
int main(void)
{
    int i;  //循环变量
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*引用起来很简单, 0为第一个元素的下标, 20为最后一个元素的下标*/
    printf("最终排序结果为:\n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high说明排序结束了
    {
        return ;
    }
    while (low < high)  //该while循环结束一次表示比较了一轮
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前寻找
        }
        if (key > a[high])
        {
            a[low] = a[high];  //直接赋值, 不用交换
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向后寻找
        }
        if (key < a[low])
        {
            a[high] = a[low];  //直接赋值, 不用交换
            --high;
        }
    }
    a[low] = key;  //查找完一轮后key值归位, 不用比较一次就互换一次。此时key值将序列分成左右两部分
    QuickSort(a, i, low-1);  //用同样的方式对分出来的左边的部分进行同上的做法
    QuickSort(a, low+1, j);  //用同样的方式对分出来的右边的部分进行同上的做法
}

总结

5  1  9  3  7  4  8  6  2

1  5  9  3  7  4  8  6  2

四种排序算法的比较

• swoole异步MySQL客户端_PHP基础
• 计算机专业毕业论文设计_PHP基础
• 什么是前后端分离_PHP基础
• 在centos_PHP基础
• php中了解有哪些容易导致漏洞的危险函数_PHP基础
• php中什么代表无穷循环_PHP基础
• 想要学习大数据_PHP基础
• 什么是高温结构陶瓷_PHP基础
• 如何获知PHP程序占用多少内存memory_PHP基础
• cap框架有哪些_PHP基础
• php开源外贸网站注意什么_PHP基础
• xxxcom域名跳转到wwwxxxcom_PHP基础
• 如何在Linux上定期定期执行命令脚本_PHP基础
• 程序员为什么要学数据结构_PHP基础
• 如何评价php7内核剖析这本书_PHP基础
• 请问在PHP中如何计算这个求和公式Sn_PHP基础
• 各个软件开发公司报价差别很大_PHP基础
• it培训都是培训些什么啊_PHP基础
• 菲律宾的披索和比索有什么不同_PHP基础
• 需要分段加密该怎么做_PHP基础