75 lines
1.7 KiB
C++
75 lines
1.7 KiB
C++
|
/* file name: quickSort.c */
|
|||
|
|
/* <20>ֳt<D6B3>Ƨ<EFBFBD> */
|
|||
|
|
|
|||
|
|
#include <stdio.h>
|
|||
|
|
void quickSort(int[], int, int, int);
|
|||
|
|
void printDashLine(void);
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
int data[20];
|
|||
|
|
int size = 0, i;
|
|||
|
|
printf("\n<EFBFBD>п<EFBFBD><EFBFBD>J<EFBFBD><EFBFBD><EFBFBD><EFBFBD>(<28><><EFBFBD>J 0 <20><><EFBFBD>ܵ<EFBFBD><DCB5><EFBFBD>): ");
|
|||
|
|
/* <20>n<EFBFBD>D<EFBFBD><44><EFBFBD>J<EFBFBD>Ʀr<C6A6><72><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>J<EFBFBD>Ʀr<C6A6><72> 0 */
|
|||
|
|
do {
|
|||
|
|
scanf("%d", &data[size]);
|
|||
|
|
} while(data[size++] != 0);
|
|||
|
|
|
|||
|
|
printDashLine();
|
|||
|
|
quickSort(data, 0, size-2, size);
|
|||
|
|
printDashLine();
|
|||
|
|
|
|||
|
|
printf("<EFBFBD>Ѥp<EFBFBD>ܤj<EFBFBD>Ƨǫ᪺<EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ");
|
|||
|
|
for (i = 0; i < size-1; i++)
|
|||
|
|
printf("%d ", data[i]);
|
|||
|
|
printf("\n");
|
|||
|
|
|
|||
|
|
return 0;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
void quickSort(int data[], int left, int right, int size)
|
|||
|
|
{
|
|||
|
|
/* left <20>P right <20><><EFBFBD>O<EFBFBD><4F><EFBFBD><EFBFBD><EFBFBD>ƧǸ<C6A7><C7B8>ƨ<EFBFBD><C6A8><EFBFBD> */
|
|||
|
|
int lbase, rbase, temp, i;
|
|||
|
|
if (left < right) {
|
|||
|
|
lbase = left+1;
|
|||
|
|
while(data[lbase] < data[left])
|
|||
|
|
lbase++;
|
|||
|
|
rbase = right;
|
|||
|
|
while(data[rbase] > data[left])
|
|||
|
|
rbase--;
|
|||
|
|
|
|||
|
|
/* <20>Ylbase<73>p<EFBFBD><70>rbase<73>A<EFBFBD>h<EFBFBD><68><EFBFBD><EFBFBD><EFBFBD>ƹ<EFBFBD><C6B9><EFBFBD> */
|
|||
|
|
while (lbase < rbase) {
|
|||
|
|
temp = data[lbase];
|
|||
|
|
data[lbase] = data[rbase];
|
|||
|
|
data[rbase] = temp;
|
|||
|
|
lbase++;
|
|||
|
|
while(data[lbase] < data[left])
|
|||
|
|
lbase++;
|
|||
|
|
rbase--;
|
|||
|
|
while (data[rbase] > data[left])
|
|||
|
|
rbase--;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/* <20><><EFBFBD><EFBFBD>lbase<73>j<EFBFBD><6A>rbase<73>A<EFBFBD>hrbase<73><65><EFBFBD><EFBFBD><EFBFBD>ƻP<C6BB>Ĥ@<40><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
|
|||
|
|
temp = data[left];
|
|||
|
|
data[left] = data[rbase];
|
|||
|
|
data[rbase] = temp;
|
|||
|
|
printf("Processing: ");
|
|||
|
|
for (i = 0; i < size-1; i++)
|
|||
|
|
printf("%3d ", data[i]);
|
|||
|
|
printf("\n");
|
|||
|
|
quickSort(data, left, rbase-1, size);
|
|||
|
|
quickSort(data, rbase+1, right, size);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
void printDashLine()
|
|||
|
|
{
|
|||
|
|
for(int i = 0; i < 62; i++)
|
|||
|
|
printf("-");
|
|||
|
|
printf("\n");
|
|||
|
|
}
|
|||
|
|
|