#include <stdio.h>
#include <stdlib.h>
#include "排序元素.h"

/*
	快速排序算法

  两个指针指向头尾，以第一个为例子，存到临时存储，因为选的第一个也就是头指针位置，所以从尾指针开始比较，
 
	1. 如果尾指针所指数据 < temp, 则将尾指针数据放到头指针中，头指针 ++

		* 如果尾指针所指数据 > temp, 尾指针数据不动，尾指针--，重复1
	
	2. 接着比较头指针，如果 头指针数据 > temp,  头指针数据放到尾指针中，尾指针--

		* 如果头指针数据 < temp, 头指针数据不动，头指针 ++，重复2


  当头尾指针相等时，就是比较数据temp的位置
  */

// 分区排序 
// @param head 头指针位置
// @param rear 尾指针位置
int partitionSort(SortList list, int head, int rear) {
	list[0] = list[head];
	while(head < rear) { // >=结束
		while(head < rear && list[rear].key >= list[0].key) {
			rear--;
		}
		if(head < rear) { // 再次判断, 防止rear == head，head<rear代表最后的rear<list[0]
			list[head] = list[rear];
			head++;
		}
		while(head < rear && list[head].key <= list[0].key) {
			head++;
		}
		if(head < rear) { // 再次判断, 防止head == rear，head<rear代表最后的head>list[0]
			list[rear] = list[head];
			rear--;
		}
	}
	// 最后head == rear
	list[head] = list[0];
	return head;
}

void fastSort(SortList list, int head, int rear) {
	int p;
	if(head < rear) {
		p = partitionSort(list, head, rear);
		// 排序左区间
		fastSort(list, head, p - 1);
		// 排序右区间
		fastSort(list, p + 1, rear);
	}
}




int partitionSort111(SortList sortList, int head, int rear) {
	if(head >= rear) {
		return head;
	}
	sortList[0] = sortList[head];
	while(head < rear) {
		while(head < rear && sortList[rear].key > sortList[0].key) {
			rear--;
		}
		if(head < rear) {
			sortList[head] = sortList[rear];
			head++;
		}
		while(head < rear && sortList[head].key < sortList[0].key) {
			head++;
		}
		if(head < rear) {
			sortList[rear] = sortList[head];
			rear--;
		}
	}
	sortList[head] = sortList[0];
	return head;
}

void fastSort111(SortList sortList, int head, int rear) {
	int middle;
	if(head >= rear) {
		return;
	}
	middle = partitionSort111(sortList, head, rear);
	fastSort111(sortList, head, middle - 1);
	fastSort111(sortList, middle + 1, rear);
}

int main44() {

	int n = 8;
	SortList list = {
		{0}, {46}, {39}, {17}, {23}, {28}, {55}, {46}, {18}
	};
	printSortList(list, 1, n);

	//fastSort(list, 1, n);
	fastSort111(list, 1, n);

	printSortList(list, 1, n);
	return 0;
}