快速排序算法

源码

#define _CRT_SECURE_NO_WARNINGS //处理scanf报错问题
#include 
#include 

#define DEBUG_SWITCH 1
#if DEBUG_SWITCH
#define DEBUG_INFO(format, ...) printf("LINE: %d: "format"\n", __LINE__, ##__VA_ARGS__)
#else
#define DEBUG_INFO(format, ...) 
#endif

#define TRUE  1
#define FALSE 0

typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned long int uint32_t;
typedef unsigned long long int uint64_t;

#define ARR_SIZE(arr,type) (sizeof(arr)/sizeof(type))

static void quick_sort(int *arr, int low, int high, uint8_t monotonicity)
{
	if (low < high)
	{
		int i = low;
		int j = high;
		int k = arr[low];
		while (i < j)
		{
			while ((i < j) && ((monotonicity) ? (arr[j] >= k) : (arr[j] <= k)))     // 从右向左找第一个小于k的数
			{
				j--;
			}

			if (i < j)
			{
				arr[i++] = arr[j];
			}

			while ((i < j) && ((monotonicity) ? (arr[i] < k) : (arr[i] > k)))      // 从左向右找第一个大于等于k的数
			{
				i++;
			}

			if (i < j)
			{
				arr[j--] = arr[i];
			}
		}

		arr[i] = k;

		// 递归调用
		quick_sort(arr, low, i - 1, monotonicity);     // 排序k左边
		quick_sort(arr, i + 1, high, monotonicity);    // 排序k右边
	}
}


int main()
{
	static int arr[20];
	for (uint32_t i = 0; i < ARR_SIZE(arr, int); i++)
	{
		arr[i] = rand();
		printf("%d ", arr[i]);
	}
	printf("\r\n");

	quick_sort(arr, 0, ARR_SIZE(arr, int) - 1, TRUE);
	for (uint32_t i = 0; i < ARR_SIZE(arr, int); i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\r\n");

	quick_sort(arr, 0, ARR_SIZE(arr, int) - 1, FALSE);
	for (uint32_t i = 0; i < ARR_SIZE(arr, int); i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\r\n");
}


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

验证