CExercise_13_1排序算法_3快速排序算法，包括单向分区以及双向分区

题目：

请手动实现快速排序算法，包括单向分区以及双向分区：

// 单向分区快速排序算法
void quick_sort_one_way(int arr[], int len);
//双向分区快速排序算法
void quick_sort_two_way(int arr[], int len);

关键点

分析：

：

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))

#define SWAP(arr, i, j){ \
int tmp = arr[i]; \
arr[i] = arr[j]; \
arr[j]=tmp; \
}

void print_arr(int arr[], int len) {
	printf("[ ");

	for (int i = 0; i < len; i++) {
		printf("%d", arr[i]);
		if (i != len - 1) {
			printf(", ");
		}
		else {
			printf("]\n");
		}
	}
}
// 函数。函数就是分区的。 然后让左边比枢纽值小；右边比它大。 
// 最后返回枢纽值的最终下标。 
int partition(int arr[], int left, int right) {
	int pivot_index = left;
	int pivot_value = arr[pivot_index];

	// 将 pivot_index 换到右边了。 
	SWAP(arr, pivot_index, right);
	//  0     1   2   3   4    5     6
	//  11    8   9   7   12   16   17
	//                  c_left      c_right

	// pivot_index = 0;  pivot_value = 12
	int cur_left = left;
	int cur_right = right;

	while (cur_left < cur_right) {
		// 上来先找左边，找左边的比pivot 大的，弄到后面去。 
		while (cur_left < cur_right && arr[cur_left] < pivot_value) {
			cur_left++;
		}
		if (cur_left < cur_right) {
			arr[cur_right] = arr[cur_left];
		}

		while (cur_left < cur_right && arr[cur_right] > pivot_value) {
			cur_right--;
		}

		if (cur_left < cur_right) {
			arr[cur_left] = arr[cur_right];
		}
	}

	arr[cur_left] = pivot_value;
	return cur_left;
}

void partition_recursive(int arr[], int left, int right) {
	if (left >= right) {
		// 没数据，或者只有一个数据了。 这时候，我们认为递归结束。 
		return;
	}
	// 核心的代码，其实是 partition。
	int partition_index = partition(arr, left, right);

	partition_recursive(arr, left, partition_index - 1);
	partition_recursive(arr, partition_index + 1, right);
}


void quick_sort(int arr[], int len) {
	// 基本思路： 首先，找到一个枢纽值。 
	// 然后将比枢纽值小的数， 放在左边； 比枢纽值大的数，放在右边。 
	// 枢纽的位置，是正确的。  紧接着，继续处理左边的小数组，和右边的小数组。 
	partition_recursive(arr, 0, len - 1);
}



int main(void) {
	int arr[10] = { 16,1,45,23,99,2,18,67,42,10 };

	print_arr(arr, ARR_LEN(arr));

	quick_sort(arr, ARR_LEN(arr));

	print_arr(arr, ARR_LEN(arr));

	return 0;
}
	

解决方案总结：

：