数组的排序算法

1.冒泡排序法

原理如下：每次比较数组中相邻的两个数组元素的值，将较小的数排在较大的数前面，可实现数组元素的从小到大排序；每次将较大的数排在较小的数前面，可实现数组元素从大到小排序。

/**每次比较数组相邻的两个元素，将大的元素放在前面**/
//冒泡排序从小到大
void fun(int arr[],int n) //定义一个数组arr[]，次数n;
{
	int i,j,temp;
	for(i = 0; i < n-1; i++) //比较的次数，
	{
		for(j = 0; j < n-1-i; j++)//每次需要的比较两个相邻元素的次数
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}
int main(int argc,char *argv[])
{
	int i;
	int arr[10];
 
	for(i = 0; i < 10; i++)
	{
		scanf("%d",&arr[i]);
	}
	fun(arr,10);
	for(i = 0; i < 10; i++)
    {
        printf("%d ",arr[i]);
    }
	
	printf("\n");
 
	return 0;
}

/**每次比较数组相邻的两个元素，将大的元素放在前面**/
//冒泡排序从大到小
void fun1(int arr[],int n) //定义一个数组arr[]，次数n;
{
	int i,j,temp;
	for(i = 0; i < n-1; i++) //比较的次数，
	{
		for(j = 0; j < n-1-i; j++)//每次需要的比较两个相邻元素的次数
		{
			if(arr[j] < arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}
int main(int argc,char *argv[])
{
	int i;
	int arr[10];
 
	for(i = 0; i < 10; i++)
	{
		scanf("%d",&arr[i]);
	}
	fun1(arr,10);
	for(i = 0; i < 10; i++)
    {
        printf("%d ",arr[i]);
    }
	
	printf("\n");
 
	return 0;
}

2.选则排序法

原理如下：每次在待排序的数组中查找到最大或最小的数组元素，将其值与最前面没有进行过排序的数组元素的值交换；

#include <stdio.h>
 
/**选择排序从小到大排序**/
int main(int argc, char* argv[])
{
	int i, j=0, temp;
	int arr[5] = { 5,3,4,1,2 };
 
	for (i = 0; i< 4; i++)
	{
		for (j = i + 1; j < 5; j++)
		{
			if (arr[i] > arr[j])
			{
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
 
	for (i = 0; i < 5; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

4.快速排序法

原理：从冒泡排序演变来的算法，使用了分治法，

首先确定数组元素第一个位置的元素为基准元素。

第一个元素的位置为L。最后一个元素的位置为R。

先用基准元素从右往左遍历，如果大于就交换，没有大于，R--；

再用基准元素从左往右遍历，如果大于于就交换，没有大于，L++；

最后插入基准值；

在对左右部分重复上述步骤；

void fun(int arr[],int start,int end)
{
	if(start >= end)
	{
		return;
	}
	int left = start; //定义一个指向数组第一个元素的指针
	int right = end; 	//定义一个指向数组最后一个元素的指针
	int pivot = arr[left]; //取出一个基准值，一般为数组第一个值
 
	while(left < right) //左边元素的指针必须小于右边元素的指针
	{
		/**右边放左边**/
		while(arr[right] > pivot && left < right) //如果右边的位置的值大于基准值，并且左边指针小于右边指针
		{                                          
			right--;                              //直到右边位置的值小于或者等于基准值，不再 -
		} 
		if(right > left )
		{
			arr[left] = arr[right];
			left++;
		}
 
		/**左边放右边**/
		while(arr[left] < pivot && left < right)
		{
			left++;
		}
		if(left < right)
		{
			arr[right] = arr[left];
			right--;
		}
	}
	arr[left] = pivot;  //将基准值插入中间,现在left 和 right 都指向基准值的指针
	fun(arr,start,left - 1); //重新排序基准左边
	fun(arr,right+1,end); //重新排序基准值右边
}
 
int main(int argc,char *argv[])
{
	int i;
	int arr[5] = {3,1,2,5,4};
	
	fun(arr,0,sizeof(arr)/sizeof(arr[0]));
	for(i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
 
	return 0;
}

3.插入排序法

5.希尔排序

6.归并排序

6.排序算法的比较