2023王道C语言训练营（冒泡排序-快速排序-插入排序）

//冒泡排序
void BubbleSort1(ElemType A[], int n)
{
	int i, j,flag;//flag为哨兵
	for(i=0;i
		flag = 0;
			for (j = n - 1; j > i; j--)//内层控制比较，交换
			{
				if (A[j - 1] > A[j])
				{
					swap(A[j - 1], A[j]);
					flag = 1;
				}
			}
			if (0 == flag)
			{
				break;
			}
	}
	

}

//快速排序 交换法
//有相同值不影响
int Partition(int* arr, int left, int right)
{
	int k, i;
	for (k = i = left; i < right; i++)
	{
		if (arr[i] < arr[right])
		{
			swap(arr[i], arr[k]);
			k++;
		}
	}
	swap(arr[k], arr[right]);
	return k;
}
//递归实现
void QuickSort(ElemType A[], int low, int high)
{
	if (low < high)
	{
		int pivotpos = Partition(A, low, high);//分割点左边的元素都比分割点小，右边的元素都比分割点大
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1, high);
	}
}

#include
#include
#include
#include
typedef int ElemType;
typedef struct {
	ElemType* elem;//存储元素的起始地址
	int TableLen;//元素个数
}SSTable;
void ST_Init(SSTable& ST, int len)
{
	ST.TableLen = len;
	ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
	int i;
	srand(time(NULL));//随机数生成，每一次执行代码就会得到随机的10个数
	for ( i = 0; i < ST.TableLen; i++)
	{
		ST.elem[i] = rand()%100;//生成的都是0-99
	}
}
void ST_print(SSTable ST)
{
	for (int i = 0; i < ST.TableLen; i++)
	{
		printf("%d ", ST.elem[i]);
	}
	printf("n");
}
void swap(ElemType& a, ElemType& b)
{
	ElemType tmp;
	tmp = a;
	a = b;
	b = tmp;
}
//冒泡排序
void BubbleSort1(ElemType A[], int n)
{
	int i, j,flag;//flag为哨兵
	for(i=0;i
		flag = 0;
			for (j = n - 1; j > i; j--)//内层控制比较，交换
			{
				if (A[j - 1] > A[j])
				{
					swap(A[j - 1], A[j]);
					flag = 1;
				}
			}
			if (0 == flag)
			{
				break;
			}
	}
	

}

//快速排序
int Partition(int* arr, int left, int right)
{
	int k, i;
	for (k = i = left; i < right; i++)
	{
		if (arr[i] < arr[right])
		{
			swap(arr[i], arr[k]);
			k++;
		}
	}
	swap(arr[k], arr[right]);
	return k;
}
//递归实现
void QuickSort(ElemType A[], int low, int high)
{
	if (low < high)
	{
		int pivotpos = Partition(A, low, high);//分割点左边的元素都比分割点小，右边的元素都比分割点大
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1, high);
	}
}

//冒泡排序与快速排序
int main()
{
	SSTable ST;
	ElemType A[10] = { 64,94,95,79,69,84,18,22,12,78 };
	ST_Init(ST, 10);//初始化
	//使用memcpy用确定的数组降低测试难度，排序算法写好之后注释即可
	//memcpy(ST.elem, A, sizeof(A));//内存copy接口，当你copy整型数组或者浮点型的疏忽要用memcpy
	ST_print(ST);
	//BubbleSort1(ST.elem,10);//冒泡排序
	QuickSort(ST.elem, 0, 9);//快速排序
	ST_print(ST);
	system("pause");

}

//插入排序，从小到大排序，升序
void InsertSort(ElemType A[], int n)
{
	int i, j;
	for (i = 2; i <= n; i++)//第0个元素是哨兵,第二个元素开始拿，往前面插
	{
		if (A[i] < A[i - 1])
		{
			A[0] = A[i];//放到暂存的位置，A[0]是暂存也是哨兵
			for (j = i - 1; A[0] < A[j]; --j)
				A[j + 1] = A[j];
			A[j + 1] = A[0];
		}
	}
}