数据结构 C语言实现快速排序_数据结构快速排序c语言

一、快速排序简介

快速排序采用分治的思想，第一趟先将一串数字分为两部分，第一部分的数值都比第二部分要小，然后按照这种方法，依次对两边的数据进行排序。

二、代码实现

#include <stdio.h>


/* 将两个数据交换 */
void swap(int* Ina , int* Inb)
{
    int temp = *Ina;
    *Ina = *Inb;
    *Inb = temp;
}

/* 进行一趟的快速排序，把一个序列分为两个部分 */
int getPartion(int* InArry,int InBegin,int InEnd)
{
    /* 刚开始的分隔线是第一个 */
    int part = InBegin;
    int index = 0;

    if(InEnd >= InBegin)
    {
        part = InBegin;
        for(index = InBegin+1; index <= InEnd; index++)
        {
            if(InArry[InBegin] >= InArry[index])
            {
                /* 交换位置 */
                swap(&InArry[part+1],&InArry[index]);
                part++;
            }
        }

        /* 把第一个数放到part处去 */
        swap(&InArry[InBegin],&InArry[part]);

        return part;
    }

}

/* 快速排序函数
*  InArry:输入的数组
* InBegin:数组的开始
*   InEnd:数组的结束
*/
void quickSort(int* InArry,int InBegin,int InEnd)
{
    if(InArry == NULL || InEnd <= InBegin)
    {
        return;
    }

    int part = 0;
    part = getPartion(InArry,InBegin,InEnd);

    /* 递归调用 */
    quickSort(InArry,0,part-1);
    quickSort(InArry,part+1,InEnd);
}

int main()
{
    int a[] = {49,38,65,97,76,13,27};
    int index = 0;

    int len = sizeof(a)/sizeof(int);

    /* 先遍历打印一下数组的元素 */
    for(index = 0; index < len; index++)
    {
        printf("%d  ",a[index]);
    }
    printf("\n");

    /* 调用快速排序函数 */
    quickSort(a,0,len-1);

    /* 再遍历打印一下数组的元素 */
    for(index = 0; index < len; index++)
    {
        printf("%d  ",a[index]);
    }
    printf("\n");



    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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90