kris_qsort.c

来自「可能是最快的排序算法.源代码和演示文件.」· C语言 代码 · 共 63 行

#include <stdio.h>
#include <conio.h>
#define MAX 20

void quick_sort(int darr[MAX], int lb, int ub)
{
int a;              /* key holder */
int up, down;
int temp;           /* temporary variable, used in swapping */

if (lb >= ub)
    return;

a = darr[lb];
up = ub;
down = lb;

while (down < up)
{
    while (darr[down] <= a)         /* scan the keys from left to right */
        down++;
    while (darr[up] > a)             /* scan the keys from right to left */
        up--;
    if (down < up)
    {
        temp = darr[down];          /* interchange records */
        darr[down] = darr[up];
        darr[up] = temp;
    }
}

darr[lb] = darr[up];                /* interchange records */
darr[up] = a;

quick_sort(darr, lb, up-1);         /* recursive call - sort first subtable */
quick_sort(darr, up+1, ub);         /* recursive call - sort second subtable */
}

main()
{
int arr[MAX];       /* main table containing keys */
int i;              /* looping variables */
int n;              /* user input (size of the table) */
int lb = 0, ub;     /* upper and lower bound variables */

printf("How many keys would you like to enter : ");
scanf("%d", &n);

ub = n;
printf("Now enter the elements separated by <space> or <enter> : \n");
fflush(stdin);
for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

quick_sort(arr, lb, ub);
printf("\nSorted table is : \n");
for (i = 0; i < n; i++)
    printf("%2d ", arr[i]);

printf("\n\nProgram over. Press any key to exit...");
getch();
}