#include "share.h"
#include "graph.h"

/************************************************************************/
/*對一個數組進行排序
/************************************************************************/
void sort(arc * a,int n)//使用快速排序的方法
{
	Qsort(a,0,n-1);
}
/************************************************************************/
/* 對數組進行快速排序
/************************************************************************/
void Qsort(arc* a,int st,int en)
{
	int midd;
	if(st>=en){
		return;
	}else
	{
		midd = pati(a,st,en);//按照中間數據對數組進行調整
		Qsort(a,st,midd-1);//循環調用
		Qsort(a,midd+1,en);
	}
}

/************************************************************************/
/* 將數組中的數據分成兩部分，以期中的一個數位中點
/************************************************************************/
int pati(arc * a,int st,int en)
{
	arc at = a[(st+en)/2];//取一個中間數據
	int i=st;
	int j=en;
	while (true) {
		while (a[i].weight<at.weight) {i++; }//選擇和合適的數據調整位置
		while (a[j].weight>=at.weight) {j--;}
		if (i<j) {
		swap(a,i,j);
		}else break;
	}
	for (int t=st;t<en;t++) {
		if (a[t].weight==at.weight) {//將中間數據調整到合適的位置
			swap(a,i,t);
			break;
		}
	}
	return(i);
}
/************************************************************************/
/*交換數組中兩個數據的位置
/************************************************************************/
void swap(arc* a,int i,int j)
{
	arc temp;
	temp.start = a[i].start;
	temp.end = a[i].end;
	temp.weight = a[i].weight;

	a[i].start = a[j].start;
	a[i].end = a[j].end;
	a[i].weight = a[j].weight;

	a[j].start = temp.start;
	a[j].end = temp.end;
	a[j].weight = temp.weight;

}