快速排序#

算法思维#

快速排序是对起泡排序的一种改进
快速排序的基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，一部分的元素均小于另一部分的元素，然后再对两部分进行快速排序，直到整个序列有序

算法设计#

用递归可以更快速、清晰地实现快速排序
设两个索引变量 i 和 j，分别作为数组左、右端的索引
当 i < j 时进行下面的操作
从数组右边索引 j 开始往左遍历，直到找到与 i 索引顺序错误的元素，或直到 i = j
如果此时 i < j，交换两个元素
从数组左边索引 i 开始往右遍历，直到找到与 j 索引顺序错误的元素，或直到 i = j
如果此时 i < j，交换两个元素
重复 3，直到 i >= j
对以 i 或 j 为界的两边子序列进行快速排序，直到整个序列有序

算法实现#

1
// 快速排序
2
/*
3
mode: 非0：升序， 0：降序
4
*/
5
void sort_quickSort(int *arr, int len, int mode)
6
{
7
    sort_quickSort_main(arr, 0, len-1, mode);
8
}
9

10
// 快速排序递归函数
11
void sort_quickSort_main(int *arr, int i, int j, int mode)
12
{
13
    int tmp;
14
    int s = i;
15
    int e = j;
16

17
    if(i >= j) return;
18

19
    while(i < j)
20
    {
21
        // arr[j] >= arr[i]
22
        while(!sort_judgeWithMode(arr[j], arr[i], mode) && (i < j))
23
        {
24
            j--;
25
        }
26

27
        if(i < j)
28
        {
29
            tmp = arr[i];
30
            arr[i] = arr[j];
31
            arr[j] = tmp;
32
        }
33

34
        while(!sort_judgeWithMode(arr[j], arr[i], mode) && (i < j))
35
        {
36
            i++;
37
        }
38

39
        if(i < j)
40
        {
41
            tmp = arr[i];
42
            arr[i] = arr[j];
43
            arr[j] = tmp;
44
        }
45
    }
46

47
    sort_quickSort_main(arr, s, i-1, mode);
48
    sort_quickSort_main(arr, i+1, e, mode);
49
}

运算结果#

测试代码

1
#define N 8
2

3
int main()
4
{
5
    int arr[N] = {49,38,65,97,76,13,27,49};
6

7
    printf("升序排列结果:\n");
8
    sort_quickSort(arr, N, 1);
9
    utils_print_arr(arr, N, "%d ");
10

11

12
    printf("\n\n降序排列结果:\n");
13
    sort_quickSort(arr, N, 0);
14
    utils_print_arr(arr, N, "%d ");
15

16

17
    return 0;
18
}

运行结果

原文链接：CSDN