社群資訊
LGG, quick OK
(高顯忠, sjgau4311@gmail.com, 2010-12-24 14:31)
1樓
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void quickSort(int[], int, int);
void show_data(int number[], int left, int right)
{
int i;
printf("\n left= %d, right= %d\n", left, right);
for (i=left;i<=right;i++) {
printf("%3d, ", number[i]);
}
printf("\n");
system("pause");
}// end of show_data()
int main(void) {
int i, j;
srand(time(NULL));
int number[MAX] = {0};
printf("排序前：");
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
quickSort(number, 0, MAX-1);
printf("\n \n \n 排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
// number[5]= 999;
// check data
for (i=0;i<(MAX-1);i++) {
j= i + 1;
// must a[i] <= a[j]
if (number[i] > number[j]) {
printf("\n\n\n *** error in check data(), \n");
printf("number[i]= %d, number[j]= %d\n", number[i], number[j]);
system("pause");
}
}
printf("\n\n\n end of check data, OK!\n");
system("pause");
return 0;
}
void quickSort(int number[], int left, int right) {
if(left < right) {
show_data(number, left, right);
int i = left;
int j = right + 1;
while(1) {
// 向右找
while(i + 1 < MAX && number[++i] < number[left]) ;
// 向左找
while(j -1 > -1 && number[--j] > number[left]) ;
if(i >= j)
break;
SWAP(number[i], number[j]);
}
SWAP(number[left], number[j]);
quickSort(number, left, j-1); // 對左邊進行遞迴
quickSort(number, j+1, right); // 對右邊進行遞迴
}
}