常见算法之排序（基础部分）_冒泡+选择+插入排序_01

最基础的常见排序算法有：

    冒泡排序（Bubble Sort）

    选择排序（Select Sort）

    插入排序（Insert Sort）

这三个的排序算法的时间复杂度都为O（n²），比较慢；空间复杂度都为O（1）。

--------------------------------------------------Java代码------------------------------------------------------------

public class Code_01_Sort 
{
	public static void main(String[] args) 
	{
		//初始化数组
		int len = (int)(Math.random()*20);//随机生成20以内的数组长度
		int[] arr = new int[len];
		for(int i = 0; i < len; i++)//在数组内随机生成1000内的值
		{
			arr[i] = (int)(Math.random()*1000) - (int)(Math.random()*1000);
		}
		
		//bubbleSort(arr);//调用冒泡排序
		//selectSort(arr);//调用选择排序
		//insertSort(arr);//调用插入排序
		mergeSort(arr);//调用归并排序
		
		
		for(int i = 0; i < len; i++)//格式化输出数组
			System.out.printf("%02d:%-+4d\n",i,arr[i]);

	}
	
	public static void bubbleSort(int[] arr)
	{//冒泡排序：每次遍历都会把未确定排序区间的最大值排到后面去
	//具体做法：每次比较的都是相邻的两个元素，如果后面的元素比前面的元素小，则交换位置。
	//每遍历一次，确定排序区间(在数组的后部分)的元素个数+1
		System.out.println("冒泡排序：");
		for(int end = arr.length-1; end > 0; end--)
		{//每遍历一次都会把最大值放到arr[end]的位置上
			for(int i = 0; i < end; i++)//从arr[0]开始往前遍历到arr[end]，arr[i]和相邻下一个的元素做比较
			{
				if(arr[i] > arr[i+1])//若比下一个元素大，则交换位置
				{
					int tmp = arr[i];
					arr[i] = arr[i+1];
					arr[i+1] = tmp;
				}
			}
		}
	}
	
	public static void selectSort(int[] arr)
	{//选择排序：每次遍历都会把未确定排序区间的最小值排到前面去
	//具体做法：每个元素都和未确定排序区间的第一个元素进行比较，若比第一个元素小，则交换位置。
	//每遍历一次，确定排序区间(在数组的前部分)的元素个数+1
		System.out.println("选择排序：");
		for(int i = 0; i < arr.length-1; i++)
		{//每遍历一次都会把最小值放到arr[i]的位置上
			for(int j=i+1; j < arr.length; j++)//从arr[i+1]开始往后遍历，依次和arr[i]比较
			{
				if(arr[i] > arr[j])//如果有比arr[i]小的元素，则与arr[i]交换位置。
				{
					int tmp = arr[i];
					arr[i] = arr[j];
					arr[j] = tmp;
				}
			}
		}
	}
	
	public static void insertSort(int[] arr)
	{//插入排序：类似在玩扑克时调整扑克顺序的做法
	//具体做法：每个元素都依次与他前边所有的元素做比较，如果比前边某个元素小，则交换位置。
	//每遍历一次，确定排序区间(在数组的前部分)的元素个数+1
		System.out.println("插入排序：");
		for(int i = 1; i < arr.length; i++)
		{//每遍历一次都会在已排序区间中找到适合arr[i]元素的位置
			for(int j = i; j >0; j--)//从arr[i]元素开始，往前遍历到arr[i-1]
			{
				if(arr[j] < arr[j-1])//如果发现arr[i]元素比它前面相邻的arr[i-1]元素小，则与前面元素交换位置
				{
					int tmp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = tmp;
				}
			}
		}
	}
	
	
}