八种排序算法

八种排序算法

排序算法的稳定性

 排序算法的世间复杂度

简单说就是程序循环执行的总次数，算法的时间复杂度是一个函数，定量的描述了算法运行的时间用符号O表示，即O（f（n））；

一、插入排序（1、直接插入排序；2、折半插入排序；3、希尔排序）

        插入排序基本思路： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。

二、交换排序（1、冒泡排序；2、快速排序） 三、选择排序（1、简单排序；2、堆排序） 四、归并排序 五、基数排序

 

 1、直接排序

 代码：

#include
using namespace std;

void InsertSort(int* a, int length)
{
	int i = 0, j = 0, temp = 0;
	for (i = 1; i < length; i++)
	{
		temp = a[i];	//将下一个要插入的元素赋值给temp（记录下来）
		for (j = i - 1; j >= 0; j--)//j从他本身的前一个开始，循环找正确的位置，退出循环时，j=-1
		{
			if (temp < a[j])	
				a[j + 1] = a[j];	//如果已经找到小于它的就交换小于他的都向后移位
			else
				break;	//如果要插入的元素已经大于或等于（找到正确位置）直接退出
		}
		a[j + 1] = temp;//此时j=-1
	}
} 

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	InsertSort(array, sizeof(array)/sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]);i++)
		cout<

2、折半插入排序

#include
using namespace std;

void BinInsertSort(int a[], int n,int elem)
{
	int low = 0;
	int high = n - 1;
	int mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (elem >= a[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}
	for (int i = n - 1; i >= high + 1; i--)
		a[i + 1] = a[i];
	a[high + 1] = elem;
}

void InsertSort(int a[], int length)
{
	int i;
	for (i = 1; i < length; i++)
	{
		BinInsertSort(a, i, a[i]);
	}
}

int main()
{
	int array[10] = { 3,8,45,13,20,6,9,11,22,33 };
	InsertSort(array,sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
		cout << array[i] << " ";
	return 0;
}

 

3、希尔排序

希尔排序的原理是先将所有数字序列进行分组，一般是分成length/2个组，然后并行同时进行分组排序，之后再不断分组，一直到每组数据只有一个元素时再交换完之后，就已经将无序序列变成有序序列了。

#include
using namespace std;

void ShellSort(int* a, int length)
{
	int i = 0, j = 0, temp = 0;
	int h = 0;
	for (h = length / 2; h > 0; h /= 2)
	{
		for (i = h; i < length; i++)
		{
			temp = a[i];	//将下一个要插入的元素赋值给temp（记录下来）
			for (j = i - h; j >= 0; j-=h)//j从他本身的前一个开始，循环找正确的位置，退出循环时，j=-1
			{
				if (temp < a[j])
					a[j + h] = a[j];	//如果已经找到小于它的就交换小于他的都向后移位
				else
					break;	//如果要插入的元素已经大于或等于（找到正确位置）直接退出
			}
			a[j + h] = temp;//此时j=-1
		}
	}
} 

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	ShellSort(array, sizeof(array)/sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]);i++)
		cout<

3、冒泡排序

#include
using namespace std;

//冒泡排序
void BubbleSort(int* arr, int length)
{
	while (length)
	{
		int flag = 0;
		for (int i = 1; i < length; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				int temp = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--length;
	}
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	BubbleSort(array, sizeof(array)/sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]);i++)
		cout<

4、快速排序

#include
using namespace std;

//冒泡排序
void QuickSort(int* arr,int start, int end)
{
	if (start >= end)
		return;
	int x = start;
	int y = end;
	int base = arr[start];
	while (x < y)
	{
		while (arr[y] > base && x < y)
		{
			y--;
		}
		if (x < y)
		{
			arr[x] = arr[y];
			x++;
		}
		while (arr[x] < base && x < y)
		{
			x++;
		}
		if (x < y)
		{
			arr[y] = arr[x];
			y--;
		}
	}
	arr[x] = base;
	QuickSort(arr, start, x - 1);
	QuickSort(arr, x + 1, end);
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	QuickSort(array,0, sizeof(array)/sizeof(array[0])-1);
	for (int i = 0; i < sizeof(array) / sizeof(array[0]);i++)
		cout<

5、简单选择排序

#include
using namespace std;

void SelectSort(int* a, int length)
{
	int i = 0, j = 0, temp = 0, index = 0;
	for (i = 0; i < length - 1; i++)
	{
		temp = a[i];
		index = i;//记录下标
		for (j = i + 1; j < length; j++)
		{
			if (a[j] < temp)
			{
				temp = a[j];
				index = j;

			}
		}
		if (index != i)
		{
			a[index] = a[i];
			a[i] = temp;
		}
	}
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	SelectSort(array, sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
		cout << array[i] << " ";
	return 0;
}

6、堆排序

#include
using namespace std;

void AdjustHeapSort(int* a, int root, int last)
{
	int child, temp = a[root];
	for (;2*root+1<=last;root=child)
	{
		child = 2 * root + 1;
		if (child + 1 <= last && a[child] < a[child + 1])
			child++;
		if (a[child] > a[root])
		{
			a[root] = a[child];
			a[child] = temp;
		}
	}
}

void swap(int* x, int* y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

void HeapSort(int* a, int length)
{
	//构建大顶堆
	int i = 0;
	for (i = length / 2 - 1; i >= 0; i--)
	{
		AdjustHeapSort(a, i, length - 1);
	}
	for (i = length - 1; i > 0; i--)
	{
		swap(&a[0],&a[i]);
		AdjustHeapSort(a, 0, i-1);
	}
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	HeapSort(array, sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
		cout << array[i] << " ";
	return 0;
}

7、归并排序

#include
#include
using namespace std;

void Merge(int* a, int start, int mid, int end)
{
	int llength = mid - start + 1;
	int rlength = end - mid;

	int* L = (int *)malloc(sizeof(int) * llength);
	int* R = (int *)malloc(sizeof(int) * rlength);

	int i=0, j=0, k=0;
	for (i = 0, k = start; i < llength; i++, k++)
		L[i] = a[k];
	for (j = 0; j < rlength; j++, k++)
		R[j] = a[k];
	for (i = 0, j = 0, k = start; i < llength && j < rlength; k++)
	{
		if (L[i] < R[j])
			a[k] = L[i++];
		else
			a[k] = R[j++];
	}
	if (i < llength)
		for (; i < llength; i++, k++)
			a[k] = L[i];
	if (j < rlength)
		for (; j < rlength; j++, k++)
			a[k] = R[j];

	free(L);
	free(R);
}

void MergeSort(int* a, int start, int end)
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	MergeSort(a, start, mid);
	MergeSort(a, mid + 1, end);

	Merge(a, start, mid, end);
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	MergeSort(array, 0,sizeof(array) / sizeof(array[0])-1);
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
		cout << array[i] << " ";
	return 0;
}

8、基数排

#include
#include
using namespace std;



void TadixSort(int* a, int length)
{
	int i = 0, max = a[0], base = 1;
	for (i = 1; i < length; i++)
	{
		if (a[i] > max)
			max = a[i];
	}

	int* t = (int*)malloc(sizeof(int) * length);
	while (max / base > 0)
	{
		int bucket[10] = { 0 };
		for (i = 0; i < length; i++)
		{
			bucket[a[i] / base % 10]++;
		}
		for (i = 1; i < 10; i++)
			bucket[i] += bucket[i - 1];
		for (i = length - 1; i >= 0; i--)
		{
			t[bucket[a[i] / base % 10] - 1] = a[i];
			bucket[a[i] / base % 10]--;
		}
		for (i = 0; i < length; i++)
			a[i] = t[i];
		base = base * 10;
	}
}

int main()
{
	int array[10] = { 3,8,10,13,16,6,9,11,22,33 };
	TadixSort(array,sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
		cout << array[i] << " ";
	return 0;
}

2021/12/12