常见交换排序算法

算法可视化互动网站：ComparisonSort

1.1 冒泡排序（未优化）

基本思想：从左到右依次比较相邻元素，如果左大右小就进行交换

#define _CRT_SECURE_NO_WARNINGS
#include
//从前到后依次比较相邻元素，如果不满足左小右大就进行交换（使用中间变量temp)
void BubbleSort(int a[], int n) {
	int i, j,temp;
	for (i = 1; i <= n; i++)	//控制趟数
	{	
		for ( j = 1; j < n; j++)	//控制每一趟的具体操作
		{
			if (a[j - 1] > a[j])	//不满足左大右小，相邻元素进行交换
			{
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	}
}
int main() {
	//一个待排序数组
	int a[9] = { 10,43,54,45,3,20,22,86 };
	//冒泡排序
	BubbleSort(a, 8);
	//输出排序后的数组
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
 }

1.2 快速排序

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之

基本思想：分治思想，确定一个pivot使得左半区均小于pivot，右半区均大于pivot，重复以上操作直到不满足low

#define _CRT_SECURE_NO_WARNINGS
#include
//划分操作找出枢轴的正确位置并返回其下标
int Partition(int a[], int low, int high) {
	//将某分区的第一个元素定一个枢轴
	int pivot = a[low];
	while (low < high)
	{
		while (low < high && a[high] >= pivot)
			high--;	//循环结束时找到一个右半区内小于pivot的值
		a[low] = a[high]; //将右半区内小于pivot的值移动至此分区左端
		while (lowhigh时，将pivot放至a[low]
	return low;
}

void QuickSort(int a[], int low, int high) {
	if (low
		int pivotpos = Partition(a, low, high);
		QuickSort(a, low, pivotpos - 1);	//递归对左半区进行排序
		QuickSort(a, pivotpos + 1, high);	//递归对右半区进行排序
	}
}
int main() {
	//一个待排序数组
	int a[8] = { 10,43,54,45,3,20,22,86 };
	//快速排序
	QuickSort(a,0,7);
	//输出排序结果
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

常见交换排序算法

C/C++/C#相关栏目本月热门文章