排序算法

排序

一.冒泡排序bubbleSort

int main()
{
	int a[5] = { 3,1,2,5,2 };
	int size = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

二.选择排序

每次把最小的找出来跟第一个数值换位置

#include<stdio.h>

int main()
{
	int a[] = { 9,8,10,7,2,14,6 };
	int i, j, temp;
	int min;
	int length = sizeof(a) / sizeof(a[0]);

	for (i = 0; i < length - 1; i++)
	{
		min = i;
		for (j = i + 1; j < length; j++)
		{
			if (a[min] > a[j])
				min = j;
		}
		if (min != i)
		{
			temp = a[min];
			a[min] = a[i];
			a[i] = temp;
		}
	}

	for (i = 0; i < length; i++)
		printf("%d\n", a[i]);

	return 0;
}

三.快速排序

#include<stdio.h>

void quickSort(int* a, int low, int high);
int findPos(int* a, int low, int high);

int main(void)
{
	int a[6] = { 2, 1, 0, 5, 4, 3 };
	int i;
	quickSort(a, 0, 5);

	for (i = 0; i < 6; i++) { printf("%d", a[i]); }

	return 0;
}

void quickSort(int* a, int low, int high)
{
	int pos;
	if (low < high)
	{
		pos = findPos(a, low ,high);
		quickSort(a, low, pos - 1);
		quickSort(a, pos + 1, high);
	}
}

int findPos(int* a, int low, int high)
{
	int val = a[low];
	while (low < high)
	{
		while (low < high && a[high] >= val)
			--high;
		a[low] = a[high];
		while (low < high && a[low] <= val)
			++low;
		a[high] = a[low];
	}
	a[low] = val;
	return low;
}

四.插入排序+二分法

#include<stdio.h>

int main()
{
	int a[] = { 0,5,4,8,1,4,10,7 };
	int i, j, temp;
	int low, high,mid;
	int l = sizeof(a) / sizeof(a[0]);

	if (a[1] > a[2])
	{
		temp = a[2];
		a[2] = a[1];
		a[1] = temp;
	}
	for (i = 3; i < l; i++)
	{
		a[0] = a[i];
		low = 1;
		high = i - 1;
		mid = (high + low) / 2;
		while (a[mid] != a[0] && high != low)
		{
			mid = (high + low) / 2;
			if (a[mid] > a[0])
				high = mid - 1;
			if (a[mid] < a[0])
				low = mid + 1;
		}
		if (a[mid] == a[0])
		{
			for (j = i; j >= mid + 2; j--)
			{
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
			a[mid + 1] = a[0];
		}
		else if (high == low)
		{
			if (a[low] < a[0])
			{
				for (j = i; j > low+1; j--)
				{
					temp = a[j];
					a[j] = a[j - 1];
					a[j - 1] = temp;
				}
				a[low + 1] = a[0];
			}
			else if (a[high] > a[0])
			{
				for (j = i; j >= high + 1; j--)
				{
					temp = a[j];
					a[j] = a[j - 1];
					a[j - 1] = temp;
				}
				a[high] = a[0];
			}
		}
	}
	for (i = 1; i < l; i++)
		printf("%d\n", a[i]);

	return 0;
}