C++ 範例程式: 排序程式 (一)

包含三種排序方法 : 插入排序, 氣泡排序(一般, 崗哨法), 選擇排序.

標頭檔(Header)

void insertion_sort(int *, int);
void bubble_sort(int *, int);
void bubble_sort_sentinel(int *, int);
void selection_sort(int *, int);

程式碼實作

void insertion_sort(int *a, int size)
{
	// From left to right : sorted position
	for(int i = 0; i < size; i++)
	{
		// From right to left : move small number to left
		for(int j = i; j > 0; j--)
		{
			if(*(a+j-1) > *(a+j))
			{	// a = a^b; b = a^b; a = a^b;
				*(a+j-1) = *(a+j-1) ^ *(a+j);
				*(a+j)   = *(a+j-1) ^ *(a+j);
				*(a+j-1) = *(a+j-1) ^ *(a+j);
			}
		}
	}
}

void selection_sort(int *a, int size)
{
	// Define min number of each run
	int minpos;
	// Find the x-th small number
	for(int i = 0; i < size-1; i++)
	{
		// Suppose first number is the small number
		minpos = i;

		// From left to right : find the x-th small number
		for(int j = i; j < size; j++)
		{
			if(*(a+j) < *(a+minpos))
				minpos = j;
		}
		// Because using XOR exchange, you must skip this condition.
		// Otherwise you will get 0. The first line of XOR exchange will do it.
		if(minpos == i)
		{
			continue;
		}
		*(a+i)      = *(a+i) ^ *(a+minpos);
		*(a+minpos) = *(a+i) ^ *(a+minpos);
		*(a+i)      = *(a+i) ^ *(a+minpos);
	}
}

void bubble_sort(int *a, int size)
{
	for(int i = size - 1; i > 0; i--)
	{
		for(int j = 0; j < i; j++)
		{
			if(*(a+j) > *(a+j+1))
			{
				*(a+j) = *(a+j) ^ *(a+j+1);
				*(a+j+1) = *(a+j) ^ *(a+j+1);
				*(a+j) = *(a+j) ^ *(a+j+1);
			}
		}
	}
}

void bubble_sort_sentinel(int *a, int size)
{
	// Define the last swap position : sentinel
	int lastswap;
	// Define the position of x-th big number
	for(int i = size - 1; i > 0;)
	{
		// Reset last swap position
		lastswap = 0;
		// From left to right : check each pair of numbers
		for(int j = 0; j < i; j++)
		{
			if(*(a+j) > *(a+j+1))
			{
				*(a+j) = *(a+j) ^ *(a+j+1);
				*(a+j+1) = *(a+j) ^ *(a+j+1);
				*(a+j) = *(a+j) ^ *(a+j+1);
				lastswap = j;
			}
		}
		// Set the last swap position as the border
		// Because numbers at right head had been sorted
		i = lastswap;
	}
}