博客

对数组内的值从小到大进行排序

1、选择排序

原理：数组内第0个元素与第一个元素进行比较，如果第0个元素大于第一个元素，则交换位置，否则不变。第0个位置元素再与第2个元素进行比较，若第0个元素比较大，交换位置，否则不变，依此类推，直至第0个元素与最后一个元素进行比较。比较的结果是第0位存放的是数组内的最小值。

第0个元素比较结束后，进行第1个元素的比较，步骤如第0个元素一样，比较结束数组第1个位存放的是第二小的值，依此类推，完成比较，即可对数组内容进行排序。

public static void selectSort(int[] arr)
{
	for(int x=0; x<arr.length-1; x++)
	{
		for(int y=x+1; y<arr.length; y++)
		{
			if(arr[x]>arr[y])
			{
				int tmp = arr[x];
				arr[x] = arr[y];
				arr[y] = tmp;
			}
		}
	}
}

2、选择排序法（优化）

如1所述，当第0个数与其他数进行比较时，若第0个数比较大，则每次比较都需要交换位置，可以对代码进行优化。若定义两个变量，一个初始化为第0个数，一个为值对应的角标，用第一个变量和其他数进行比较，此变量记录比较过程中的最小值，另一个变量记录所对应的角标。比较完成后，将得到的最小值和第0个数进行交换位置。将数组第1个值赋给变量，再进行比较，得到第二小的值，和数组内第1个数交换位置，依此循环。这样的话，每轮比较只会对数组进行一次交换位置，避免过多对堆内存进行操作，速度相对于第1种比较快。

public static void selectSort_2(int[] arr)
{
	for(int x=0; x<arr.length-1; x++)
	{
		int num = arr[x];
		int index = x;
		for(int y=x+1; y<arr.length; y++)
		{
			if(num>arr[y])
			{
				num = arr[y];
				index = y;
			}
		}
		if(index!=x)
		{
			int tmp = arr[x];
			arr[x] = arr[index];
			arr[index] = tmp;
		}
	}
}

3、冒泡排序法

原理：数组内第0个数和第1个数进行比较，若第0个数比较大，则交换位置，然后第1个数和第2个数进行比较，若大则交换位置，否则不变，依此类推，倒数第二个数和最后一个数进行比较，若大则交换位置，这样比较下来，最后一个数必定是最大值。下一轮比较最后一个不用参加比较了。

再从第0个数开始和第1个进行比较，若大则交换位置，第1个数和第2个数进行比较，依此类推，倒数第二个位置的数一定是第二大的数。按照这个规律进行，完成数组的排序。

public static void bublleSort(int[] arr)
{
	for(int x=0; x<arr.length; x++)
	{
		for(int y=0; y<arr.length-1-x; y++)
		{
			if(arr[y]>arr[y+1])
			{
				int tmp = arr[y];
				arr[y] = arr[y+1];
				arr[y+1] = tmp;
			}
		}
	}
}