資料結構作業八之一:QUICK SORT
#include<iostream>
#include<time.h>
using namespace std;
#define gStackSize 100
#define gLimit StackSize -1
int gSP = 0;
int stack[gStackSize];
void CreateDataArray(int *DataArray, int Input);
bool QuickSort(int *DataArray, int n);
void main(void)
{
int Input;
int *DataArray;
cout << "Please input the number of node: ";
cin >> Input;
DataArray = new int[Input];
CreateDataArray(DataArray, Input);
for(int i= 0; i<Input; i++)
{
cout << DataArray[i] << " ";
}
cout << endl;
QuickSort(DataArray, Input);
for(int i= 0; i<Input; i++)
{
cout << DataArray[i] << " ";
}
cout << endl;
}
void PUSH(int data)
{
stack[gSP] = data;
gSP++;
}
int POP(void)
{
int data;
gSP--;
data = stack[gSP];
return data;
}
void CreateDataArray(int *DataArray, int Input)
{
int n, i, Data;
for(n = 0; n < Input; n++)
{
time_t t;
tm NOW;
while(1)
{
int Flag = 0;
time(&t);
localtime_s(&NOW, &t);
Data = ((rand()<<15) | rand() * NOW.tm_sec) % 100;
for(i = 0; i <n; i++)
{
if(DataArray[i] == Data)
Flag = 1;
}
if (!Flag)
break;
}
DataArray[n] = Data;
}
}
bool QuickSort(int *DataArray, int n)
{
int Left, Right, Scan, Counter, RPosition, NRight1, NRight2, NLeft;
int temp1, temp2;
Left = 0;
Right = n-1;
PUSH(Left);
PUSH(Right);
PASS1:
if(gSP < 0)
return false;
Right = POP();
Left = POP();
if(Left == Right)
goto PASS1;
Counter = 0;
Scan = Left + 1;
do
{
if(DataArray[Left] >= DataArray[Scan])
Counter++;
Scan++;
}while(Scan <= Right);
RPosition = Left + Counter;
if(!(RPosition <= Left))
{
NRight1 = RPosition - 1;
PUSH(Left);
PUSH(NRight1);
}
NLeft = RPosition +1;
if(!(NLeft > Right))
{
NRight2 = Right;
PUSH(NLeft);
PUSH(NRight2);
}
if(!(RPosition == Right))
{
if(!(RPosition == Left))
{
temp1 = DataArray[Left];
DataArray[Left] = DataArray[RPosition];
DataArray[RPosition] = temp1;
Scan = Left;
} else {
goto PASS1;
}
} else {
int temp;
temp = DataArray[Left];
DataArray[Left] = DataArray[RPosition];
DataArray[RPosition] = temp;
goto PASS1;
}
do
{
if(!(Scan < RPosition))
{
if(Scan > RPosition)
{
if(DataArray[RPosition] >= DataArray[Scan])
{
temp2 = POP();
temp1 = DataArray[temp2];
DataArray[temp2] = DataArray[Scan];
DataArray[Scan] = temp1;
}
}
} else {
if(!(DataArray[RPosition] >= DataArray[Scan]))
PUSH(Scan);
}
Scan++;
}while(!(Scan > Right));
goto PASS1;
}
=============================================
Please input the number of node: 15
24 4 16 60 28 0 76 56 12 84 64 96 52 8 80
0 4 8 12 16 24 28 52 56 60 64 76 80 84 96
請按任意鍵繼續 . . .
=============================================
Previous in This Category: 搞死人的資料結構作業七:BST(Add / Del) Next in This Category: 資料結構作業八之二:WINNER TREE(SELECTION TREE)

