【C语言数据结构】快速排序（交换排序） | 原理+完整代码

一、原理

1. 首先选一个轴值（即比较的基准)，通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值
2. 分别对这两部分重复上述方法，直到整个序列有序。（递归实现）

思路：

1. 选择轴值：选择第一个元素为轴值
2. i=第一个元素 j=最后一个元素 ，
   当a[i]<a[ j ], j 前移 ; a[ i ] > a[ j ]交换 ，此时 i（轴值）在后面，保证 a[ i ]>a[ j ],否则交换a[ i ]、a[ j ]，直到 i==j完成一次快速排序。

左边子序列（无序）都 ＜轴值； 右边子序列都 >轴值

性能

最好（平均）O（nlog2n）
最坏 O(n*2) 与轴值的选取有关
可以把快排看成 递归二叉树。

二、代码

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

int partitions(int *a,int first,int end)
{
    int i,j,t;
    i=first; j=end;
    while(i<j)
    {
        while(i<j && a[i]<=a[j])        
            j--;
        if(i<j)
        {
            t=a[i]; a[i]=a[j];a[j]=t;
            i++;
        }

        while(i<j &&a[i]<=a[j])
            i++;
        if(i<j)
        {
            t=a[i]; a[i]=a[j];a[j]=t;
            j--;
        }
    }

    return i;
}
void quickSort(int r[],int first,int end)
{
    int pos;
    if(first<end)   //递归出口
    {
        pos=partitions(r,first,end);
        quickSort(r,first,pos-1);
        quickSort(r,pos+1,end);
    }
}
int main()
{
    int i;
    int s[8]={3,7,34,52,85,12,62,65};
    quickSort(s,0,7);
    for(i=0;i<8;i++)
        printf("%d ",s[i]);

    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