3、排序

一、选择排序(selectionSort)

 

基本思想：

    每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

 

二、冒泡排序(bubbleSort)

 

基本思想：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 冒泡和选择很相似，每一轮比较都是找出最值，不同的是找最值的方式不同

三、插入排序(insertSort)

 

基本思想：

    始终保证前面的数是有序的，然后将后面一个数 x 取出，依次向前比较，直到大于等于前面某个数，或者到头了，那么这时的位置就是x应该放的位置，再重复操作

 

四、快速排序(quickSort)

 

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

 

快速排序的基本思想：

    设当前待排序的无序区为R[left..right]，利用分治法可将快速排序的基本思想描述为：

a,分解

1. 在R[left..right]中任选一个记录作为基准(Pivot)，
2. 以此基准将当前无序区划分为左、右两个较小的子区间R[left..pivotpos-1)和R[pivotpos+1..right]，
3. 并使左边子区间中所有记录的关键字均小于等于基准记录pivot
4. 右边的子区间中所有记录的关键字均大于等于pivot
5. 而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序
6. 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(pivot=R[pivotpos])

b，求解

通过递归调用快速排序对左、右子区间R[left..pivotpos-1]和R[pivotpos+1..right]快速排序。

c，组合

因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作

 

以下是具体代码：

class SortDemo 
{
	public static void main(String[] args) 
	{
		int[] arr = new int[]{5,3,6,8,4,6,9,2};
		//选择排序
		//selectionSort(arr);
		//冒泡排序
		//bubbleSort(arr);
		//插入排序
		//insertSort(arr);
		//快速排序
		quickSort(arr,0,arr.length-1);
		for(int x=0;x<arr.length-1;x++)
		{
			System.out.print(arr[x]+",");
		}
		System.out.println(arr[arr.length-1]);
	}
	//选择排序
	public static void selectionSort(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])
				{
					swap(arr,x,y);
				}
			}
		}
	}
	//冒泡排序
	public static void bubbleSort(int[] arr)
	{
		for(int x=0;x<arr.length-1;x++)//只需要比较arr.length-2次
		{
			//-x是因为每次比较后最后一个都是最值，不用再比较了  -1是为了防止角标越界
			for(int y=0;y<arr.length-x-1;y++)
			{
				if(arr[y]>arr[y+1])
				{
					swap(arr,y,y+1);
				}
			}
		}
	}
	//插入排序
	public static void insertSort(int[] arr)
	{
		//从1开始，因为为0时只有一个数，无需比较
		for(int x=1;x<arr.length;x++)
		{
			//用temp记录要插入的数，相当于留一个空位
			int temp = arr[x];
			//x-1是有序数据的最大角标，插入就在有序的数据中插入
			int y = x-1;
			for(;y>=0 && arr[y]>temp;y--)
			{
				//如果y>=0，并且arr[y]大于temp就把arr[y]向后移一位
				arr[y+1] = arr[y];
			}
			//比较完成后y+1就是temp该放的位置
			arr[y+1] = temp;
		}
	}
	//快速排序
	public static void quickSort(int[] arr,int left,int right)
	{
		//对arr[left,right]快速排序
		int pivotpos;//划分后的基准的记录位置
		//仅当区间长度大于1时才排序
		if(left < right)
		{
			//对arr[left,right]做划分
			pivotpos = partition(arr,left,right);
			quickSort(arr,left,pivotpos-1);//对左区间递归排序
			quickSort(arr,pivotpos+1,right);//对右区间递归排序
		}
	}
	//取得基准位置，划分区域
	private static int partition(int[] arr,int left,int right)
	{
		//取区间最左边的数最为基准数
		int pivot = arr[left];
		int pivotpos;//记录pivot所在的位置
		int x = left;
		int y = right;
		while(x < y)
		{
			//先从右边开始找第一个小于pivot的数，要保证 x<y
			//因为比如说第一个数是最小的，那么没有x<y那么y--最后就会等于-1
			while(arr[y] >= pivot && x < y)
				y--;
			//x = y的时候不用交换
			if(x < y)
				swap(arr,x,y);
			//再从左边开始找第一个大于pivot的数，要保证 x<y
			while(arr[x] <= pivot && x < y)
				x++;
			if(x < y)
				swap(arr,x,y);
		}
		//一轮比较后x的值就是pivotpos也就是pivot所在的位置
		pivotpos = x;
		return pivotpos;
	}
	//交换数组中两个数的位置
	public static void swap(int[] arr,int x,int y)
	{
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
}

 

五、Arrays.sort(arr);//java中已经定义好的一种排序方式，开发中，对数组排序，要使用该句代码