qsort.cpp

快速排序算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define LEN_INT(a) (sizeof(a)/sizeof(int))

void swap(int *a, int i, int j);
void print(int *a, int n);
/*
 * 库函数qsort调用。
 */
int compare(const void *arg1, const void *arg2);

/*
 * q_sort 以a[0]为基准，从两边向中间搜索，使左边的数据比a[0]小
 *        右边的数据比a[0]大，最后更换a[0]位置。
 */
void q_sort(int *a, int left, int right);
/*
 * quicksort 以a[0]为基准，从左向右搜索，以索引nless=0.
 *           使比a[0]小的数据与a[++nless]交换。然后交换a[0]和a[nless]
 *           ,完成后，对于任何0<=i<nless,都有a[i]<a[nless].
 *			 ,完成后，对于任何nless<i<len(a),都有a[nless]<a[i].
 */
void quicksort(int *a, int n);

int main()
{
	//clock_t begin;
	//begin = clock();
	int array[20] = {15, 13, 3, 18, 4, 8, 34, 12, 11, 45
					,6, 7, 29, 57, 19, 14, 33, 17, 2, 9};

	//for (int n = 0; n < 1000000; n++)
		//qsort(array, LEN_INT(array), sizeof(int), compare);
		q_sort(array, 0, LEN_INT(array)-1);
		//quicksort(array, LEN_INT(array));

	print(array, LEN_INT(array));
	//system("pause");
	//double dval = clock() - begin;
	//printf("the time is %.3f sec\n", dval/CLOCKS_PER_SEC);
	return 0;
}
void quicksort(int *a, int n)
{	
	if (n <= 1) return; 

	int i;
	int nless = 0;
	for (i = 1; i < n; i++)
	{
		if (a[i] < a[0])
			swap(a, ++nless, i); 
	}
	swap(a, 0, nless);
#ifdef _DEBUG
	print(a, n);
#endif
	quicksort(a, nless);
	quicksort(a+nless+1, n-nless-1);
}
void q_sort (int *a, int left, int right)
{
	if (left >= right)
		return;

	int i = left + 1;
	int j = right;
	int pivot = a[left];
	int npivot;

	for (; i < j; i++, j--)
	{
		while (a[i]<pivot && i<j)
			i++;
		while (a[j]>pivot && i<j)
			j--;

		if (i >= j)
			break;
		else
			swap(a, i, j);
	}
	
	if (a[i] < pivot)
		npivot = i;
	else
		npivot = i -1;

	swap(a, left, npivot);
#ifdef _DEBUG
	print(a, 20);
	printf("\n");
#endif
	q_sort(a, left, npivot-1);
	q_sort(a, npivot+1, right);
}

void swap(int *a, int i, int j)
{
	int temp;
	temp = a[i];
	a[i] = a[j];	
	a[j] = temp;
}
void print(int * a, int n)
{
	for (int t = 0; t < n; t++)
	{
		printf ("%d ", a[t]);
	}
	printf("\n");
}

int compare(const void *arg1, const void *arg2)
{
	/* Compare all of both strings: */
	int a, b;
	a = *(int *)arg1;
	b = *(int *)arg2;

	if (a > b)
		return 1;
	else if (a == b)
		return 0;
	else 
		return -1;
}