基本排序（C语言实现）

# 基本排序（C语言实现）

`

• 一、冒泡排序
• 二、快速排序
• 二、堆排序

代码如下：
#include 
void BubbleSort(int arr[], int sz)	   //int arr[]----int* arr----数组首元素的地址
{
	//冒泡排序的趟数
	int i = 0;
	for (i = 0; i < sz-1; i++) //外层循环是比较的轮数，数组内有10个数，
	                           //那就应该比较9轮。
	{
		//一趟冒泡排序
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)//内层循环比较的是当前一轮的比较次数。
			                          //若元素个数为10---趟数--9次
								      //第一趟对比9次，第二趟8次，第三趟7...            
		{
			//冒泡排序的实现
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j ] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
}
//打印数组								   
void PrintfArr(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)   // 
		printf("%d ", arr[i]);
	}
	printf("n");
}
int main()
{
	//创建一个逆数组
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	//计算数组元素个数的大小
	int sz = sizeof(arr) / sizeof(arr[0]);
	//创建打印数组函数
	PrintfArr(arr, sz);
	//创建一个冒泡排序函数---将数组arr排成升序
	BubbleSort(arr, sz);
	//创建打印数组函数
	PrintfArr(arr, sz);
	return 0;
}

主要思想：
1.从序列中，任选一个记录k作为轴值 pivot
选择策略：
第一个元素
最后一个元素
中间元素
随机选择
2.将剩余的元素，分割成左子序列L和右子序列R
3.L 中所有元素都 < k，R 中所有元素都 > k
4.对L和R递归进行快排，直到子序列中有 0 个或者1个元素,退出。
代码如下：

#include 
	if (left < right)
	{
		int i = left;
		int j = right;
		int k = arr[left];	   //取最左边的元素作为基值
		while (i < j)
		{
			while (i < j && arr[j] >= k) //右指针向左移动
			{
				j--;					
			}
			if (i < j)				    //小于key的放左边
			{
				arr[i++] = arr[j];		
			}
			while (i < j && arr[i] < k)	 //左针向右移动
			{
				i++;
			}
			if (i < j)
			{							 //大于key的放右边
				arr[j--] = arr[i];
			}
		}
		arr[i] = k;                      //最终将key放入i == j处
		//然后左右两部分分别在递归
		QuickSort(arr,left,i-1);		  //左边递归
		QuickSort(arr,i+1,right);		  //右边递归
	}
}

void PrintArr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
}
int main()
{
	int arr[10] = { 1,3,5,7,8,2,4,6,10,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSort(arr, 0, sz - 1);
	PrintArr(arr, sz);
	return 0;
}

代码如下：