四种查找方法——冒泡、选择、查找、快速

1：冒泡排序法

冒泡排序，是最简单也是最基础的排序法，一定要牢记

如果理解不了，可以直接记住结构

for(i=1; i 
冒泡排序还能进行优化，比如，设一个变量flag初始化为0，每一次交换时，都把flag赋值为1。当某一轮循环后，flag的值没有变，意味着数组已经排序完成，直接结束循环。以下是优化代码
 
#include
#include
int main(int argc, const char *argv[])
{
	int arr[] = {198, 289, 98, 357, 85, 170, 232, 110};  //定义一个数组
	int i,j;
	int flag = 0;
	int temp = 0;
	for(i=1; i<8; i++)
	{
		flag = 0;
		for(j=0; j<8-i; j++)       //冒泡排序法
		{
			if(arr[j] > arr[j+1]) 
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = 1;
			}
		}
		if(flag == 0)
		{
			break;
		}
	}
    //遍历输出
	for(i=0; i<8; i++)
	{
		printf("%5d",arr[i]);
	}
	printf("n");
	return 0;
}
 
 
2:选择排序法
 
选择排序法相比于冒泡排序法，每一轮遍历，只需要交换一次变量值，减少了运算量
 
它的实现原理，以升序为例
 
假设第一个值为最小值，赋值给变量min，记录其下标为index。遍历数组，当找到一个值arr[k]比它小时，把arr[k]的值赋给min，同时把下标赋值给index。一轮遍历完成后，检查index的值是否变化，如果变化，则交换第一个位置与下标为index位置的值。此时，第一个为值的元素为最小值，第二轮循环，从第二个值开始，直到结束。
 
以下是代码实现
 
#include
#include
int main(int argc, const char *argv[])
{
	int i, j;
	int index=0;
	int min;
	int arr[] = {198, 289, 98, 357, 85, 170, 232, 110};
	for(i=0; i<8; i++)
	{
		index = i;
		min = arr[index];
		for(j=i; j<8; j++)
		{
			if(min > arr[j])
			{
				min = arr[j];
				index = j;
			}
		}
		if(arr[i] != arr[index])
		{
			arr[i] ^= arr[index];
			arr[index] ^= arr[i];
			arr[i] ^= arr[index];
		}
	}
//遍历输出
	for(i=0; i<8; i++)
	{
		printf("%5d",arr[i]);
	}
	printf("n");
	return 0;
}
 
3：插入排序法（升序）
 
从第一个位置开始往后遍历，每次记录当前位置的值为temp，当它的值arr[i]小于前一个值arr[i-1]时，选中这个值也就是temp，往前遍历，找到第一个小于temp的值arr[k]的位置，将这个值之后的元素逐个后移，并将temp的值赋给 arr[k]，此时前i个元素就完成了升序排列。然后从第i+1个值开始继续往后遍历，重复以上操作即可完成排序
 
以下是代码实现
 
#include
#include
int main(int argc, const char *argv[])
{
	int i, j;       //循环变量
	int temp;        //临时变量
	int arr[] = {198, 289, 98, 357, 85, 170, 232, 110};
	for(i=1; i<8; i++)
	{
		int temp = arr[i];
		for(j=i; j>0 && temp
 
4：快速排序法
 
顾名思义，是速度最快的排序法。原理很简单，我们每次选一个值作为基准值，记录下来，它所在的位置就相当于空出来了。接下来，我们数列第一个位置 i，以及最后一个位置 j，开始分别向前向后遍历。首先是 j 向前遍历，当发现比基准值小的值时，将那个位置的值直接赋给原本基准值所在的位置，此时，它原先的位置也相当于空了出来；再把 i 向后遍历，当发现比基准值大的值时，将那个位置的值赋给 j 所在的位置，此时 i 所在的位置也相当于空了出来，此时再把 j 向前移动……直到 i 与 j 交错，此时，所有比基准值小的值，都在基准值左边，比它大的值，都在它的右边，我们将此时基准值所在的位置返回给另一个函数，在另一个函数中，采用递归的方式，不断调用自己与排序模块，直到每一个分块只剩下一个元素。
 
以下是代码实现以及注释
 
//一趟快速排序函数
int part(int *arr, int low, int high)
{
	int x = arr[low];    //选定基准
	while(low < high)           //low=x && low 
由此我们可以看出来，快速排序法处理最慢的序列，即把原本升序的序列降序，以及原本降序的序列升序。