直接插入，简单选择和冒泡排序

,
  • 直接插入排序

insertSort[]数组用来存储我们要排的关键字，n为关键字的个数，temp用来暂时存储我们当前要插入的排序的关键字。
第一个for循环是从i=1开始，是因为我们规定认为初始状态的第0个元素为有序序列，第0个元素之后的元素为无序序列。我们的思路是从无序序列中逐次扫描，与有序序列中的大小进行比较，从而将他们插入到合适的位置中去。
因为箭头总是指向带插入位置的前一个位置，所以我们要arr[j+1]=temp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertSort(int arr[],int n) 
{ 
	int temp,i,j;
	for(i=1;i<n;++i)
	{
		temp=arr[i]；
		j=i-1; //j指向有序序列中的最右边的一个元素
		while(j>=0&&temp<arr[j])
		{
			arr[j+1]=arr[j];
			--j; //j是从右往左扫描有序序列
		}
		arr[j+1]=temp; //将temp中的待排关键字插入

	}
}
  • 简单选择排序

首先这个排序的思想是：首先初始状态是从这个所有元素中选择出最小的元素，将他与这个整体中的第一个元素互换，这样，这个元素就为有序序列，然后再从已经除去被排序好的那个元素的无序序列中再选择出一个最小的元素，将这个元素与当前无序序列的第一个元素交换位置，此时有序序列的长度变为2，以此循环，将其变为有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectSort(int arr[],int n)
{
	int i,j,k;
	int temp;
	for(i=0;i<n;++i)
	{
		k=i; //循环取最值
		for(j=i+1;j<n;++j)
			if(arr[k]>arr[j])
				k=j;//只是用k来存储最小元素在数组中的下标
		temp=arr[i]; //将当前元素的最小值与无序序列中的第一元素互换位置
		arr[i]=arr[k];
		arr[k]=temp;
	}
}
  • 冒泡排序

首先我们从一个序列中依次从左往右扫描，如果当前的元素，比当前元素的前一个元素小的话，那么就交换这两个元素，这样一直扫描到最后，这样一趟扫描下来，目前最大的元素就会被移动到最右边，此时，就将最右边设为有序序列。接着，如此循环，将前面的无序序列的元素扫描，将最大的元素又移动到最右边，并入有序序列。以此即可。
不过我们为了提高效率，发现，如果我们在扫描的时候，如果没有发生元素的交换的话，就说明无序序列也变为有序了。所以我们可以设置一个标记去标记（flag）这种情况是否发生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void bubleSort(int arr[],int n)
{
	int i,j,flag;
	int temp;
	for(i=n-1;i>=1;--i) //无序序列逐渐缩小
	{
		flag=0;
		for(j=1;j<=i;++j)
			if(arr[j-1]>arr[j]])
			{
				temp=arr[j];
				arr[j]=arr[j-1];
				arr[j-1]=temp;
				flag=1;
			}
		if(flag==0)
			return;
	}
}