[数据结构与算法]常见的排序算法——选择排序，冒泡排序，插入排序，快速排序，归并排序

太久没看代码了，最近打算复习一下java，又突然想到了排序算法，就把几种常见的排序算法用java敲了一遍，这里统一将无序的序列从小到大排列。

选择排序
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在下一个位置，直到待排序元素个数为0。

选择排序代码如下：

	public void Select_sort(int[]  arr) {
		int temp,index;
		for( int i=0;i<10;i++) {
			index = i;
			for(int j = i + 1 ; j < 10 ; j++) {
				if(arr[j] < arr[index])
					index = j;
			}
			/*
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
			*/
			swap(arr,i,index);
		}
		System.out.print("经过选择排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr[i] +" ");
		System.out.println("");
	}

冒泡排序
冒泡排序是一种比较基础的排序算法，其思想是相邻的元素两两比较，较大的元素放后面，较小的元素放前面，这样一次循环下来，最大元素就会归位，若数组中元素个数为n，则经过（n-1）次后，所有元素就依次从小到大排好序了。整个过程如同气泡冒起，因此被称作冒泡排序。

选择排序代码如下：

public void Bubble_sort(int[] arr) {
		int temp;
		for(int i = 0 ; i < 9 ; i++) {
			for(int j = 0 ; j < 10 - i - 1 ;j++) {
				if(arr[j] > arr[j+1]) {
					/*
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
					*/
					swap(arr,j,j+1);
				}
			}
		}
		System.out.print("经过冒泡排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr[i] +" ");
		System.out.println("");
	}

插入排序
插入排序也是一种常见的排序算法，插入排序的思想是：创建一个与待排序数组等大的数组，每次取出一个待排序数组中的元素，然后将其插入到新数组中合适的位置，使新数组中的元素保持从小到大的顺序。

插入排序代码如下：

	public void Insert_sort(int[] arr) {
		int length = arr.length;
		int[] arr_sort = new int[length];
		int count = 0;
		for(int i = 0;i < length; i++) {
			if(count == 0) {
				arr_sort[0] = arr[0];
			}else if(arr[i] >= arr_sort[count - 1]) {
				arr_sort[count] = arr[i];
			}else if(arr[i] < arr_sort[0]) {
				insert(arr,arr_sort,arr[i],0,count);
			}else {
				for(int j = 0;j < count - 1; j++) {
					if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
						insert(arr,arr_sort,arr[i],j+1,count);
						break;
					}
				}
			}
			count++;
		}
		System.out.print("经过插入排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr_sort[i] +" ");
		System.out.println("");
	}
	public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
		for(int i = count; i > index; i--)
			arr_sort[i] = arr_sort[i-1];
		arr_sort[index] = value;
	}

快速排序
快速排序的效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一次外循环只能归位一个值，有n个元素最多就要执行（n-1）次外循环。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
快速排序的思想是：每趟排序时选出一个基准值（这里以首元素为基准值），然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。

	public void Quick_sort(int[] arr, int left, int right) {
		if(left >= right) 
			return ;
		
		int temp,t;
		int j = right;
		int i = left;
		temp = arr[left];
		while(i < j) {
			while(arr[j] >= temp && i < j)
				j--;
			while(arr[i] <= temp && i < j)
				i++;
			if(i < j) {
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		arr[left] = arr[i];
		arr[i] = temp;
		
		Quick_sort(arr,left, i - 1);
		Quick_sort(arr, i + 1, right);
	}

归并排序
归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，每两个小分组合并成一个大的分组，逐层进行，最终所有的元素都是有序的。

	public void Mergesort(int[] arr,int left,int right) {
		if(right - left > 0) {
			int[] arr_1 = new int[(right - left)/2 + 1];
			int[] arr_2 = new int[(right - left + 1)/2];
			int j = 0;
			int k = 0;
			for(int i = left;i <= right;i++) {
				if(i <= (right + left)/2) {
					arr_1[j++] = arr[i];
				}else {
					arr_2[k++] = arr[i];
				}
			}
			Mergesort(arr_1,0,(right - left)/2);
			Mergesort(arr_2,0,(right - left - 1)/2);
			Merge(arr_1,arr_2,arr);
		}
	}
	public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
		int i = 0;
		int j = 0;
		int k = 0;
		int L1 = arr_1.length;
		int L2 = arr_2.length;
		while(i < L1 && j < L2) {
			if(arr_1[i] <= arr_2[j]) {
				arr[k] = arr_1[i];
				i++;
			}else {
				arr[k] = arr_2[j];
				j++;
			}
			k++;
		}
		if(i == L1) {
			for(int t = j;j < L2;j++)
				arr[k++] = arr_2[j];
		}else {
			for(int t = i;i < L1;i++)
				arr[k++] = arr_1[i];
		}
	}

归并排序这里我使用了left，right等变量，使其可以通用，并没有直接用数字表示那么明确，所以给出相关伪代码，便于理解。

Mergesort(arr[0...n-1])
	//输入：一个可排序数组arr[0...n-1]
	//输出：非降序排列的数组arr[0...n-1]
	if n>1
		copy arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//确保arr_1中元素个数>=arr_2中元素个数
		//对于总个数为奇数时，arr_1比arr_2中元素多一个；对于总个数为偶数时，没有影响
		copy arr[n/2...n-1] to arr_2[0...n/2-1]
		Mergesort(arr_1[0...(n+1)/2-1])
		Mergesort(arr_2[0...n/2-1])
		Merge(arr_1,arr_2,arr)

Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
	//输入：两个有序数组arr_1[0...p-1]和arr_2[0...q-1]
	//输出：将arr_1与arr_2两数组合并到arr
	int i<-0;j<-0;k<-0
	while i<p and j<q do
		if arr_1[i] <= arr_2[j]
			arr[k] <- arr_1[i]
			i<-i+1
		else arr[k] <- arr_2[j];j<-j+1
		k<-k+1
	if i=p
		copy arr_2[j...q-1] to arr[k...p+q-1]
	else copy arr_1[i...p-1] to arr[k...p+q-1]

最后，完整代码如下：

package test_1;

import java.util.Scanner;

public class Test01 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr_1 = new int[10];
		for(int i = 0 ; i < 10 ; i++)
			arr_1[i] = sc.nextInt();
		Sort demo_1 = new Sort();
		
		//1~5一次只能运行一个，若多个同时运行，则只有第一个有效，后面几个是无效排序。因为第一个运行的已经将带排序数组排好序。
		
		demo_1.Select_sort(arr_1);//-----------------------1
		
		//demo_1.Bubble_sort(arr_1);//---------------------2
		
		/*							//---------------------3
		demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
		System.out.print("经过快速排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr_1[i] +" ");
		System.out.println("");
		*/
		
		//demo_1.Insert_sort(arr_1);//--------------------4
		
		/*							//--------------------5
		demo_1.Mergesort(arr_1,0,arr_1.length - 1);
		System.out.print("经过归并排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr_1[i] +" ");
		System.out.println("");
		*/
	}
}

class Sort {
	public void swap(int arr[],int a, int b) {
		int t;
		t = arr[a];
		arr[a] = arr[b];
		arr[b] = t;
	}
	
	public void Select_sort(int[]  arr) {
		int temp,index;
		for( int i=0;i<10;i++) {
			index = i;
			for(int j = i + 1 ; j < 10 ; j++) {
				if(arr[j] < arr[index])
					index = j;
			}
			/*
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
			*/
			swap(arr,i,index);
		}
		System.out.print("经过选择排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr[i] +" ");
		System.out.println("");
	}
	
	public void Bubble_sort(int[] arr) {
		int temp;
		for(int i = 0 ; i < 9 ; i++) {
			for(int j = 0 ; j < 10 - i - 1 ;j++) {
				if(arr[j] > arr[j+1]) {
					/*
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
					*/
					swap(arr,j,j+1);
				}
			}
		}
		System.out.print("经过冒泡排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr[i] +" ");
		System.out.println("");
	}
	
	public void Quick_sort(int[] arr, int left, int right) {
		if(left >= right) 
			return ;
		
		int temp,t;
		int j = right;
		int i = left;
		temp = arr[left];
		while(i < j) {
			while(arr[j] >= temp && i < j)
				j--;
			while(arr[i] <= temp && i < j)
				i++;
			if(i < j) {
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		arr[left] = arr[i];
		arr[i] = temp;
		
		Quick_sort(arr,left, i - 1);
		Quick_sort(arr, i + 1, right);
	}
	
	public void Insert_sort(int[] arr) {
		int length = arr.length;
		int[] arr_sort = new int[length];
		int count = 0;
		for(int i = 0;i < length; i++) {
			if(count == 0) {
				arr_sort[0] = arr[0];
			}else if(arr[i] >= arr_sort[count - 1]) {
				arr_sort[count] = arr[i];
			}else if(arr[i] < arr_sort[0]) {
				insert(arr,arr_sort,arr[i],0,count);
			}else {
				for(int j = 0;j < count - 1; j++) {
					if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
						insert(arr,arr_sort,arr[i],j+1,count);
						break;
					}
				}
			}
			count++;
		}
		System.out.print("经过插入排序后：");
		for(int i = 0 ; i < 10 ; i++)
			System.out.print( arr_sort[i] +" ");
		System.out.println("");
	}
	public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
		for(int i = count; i > index; i--)
			arr_sort[i] = arr_sort[i-1];
		arr_sort[index] = value;
	}
	
	public void Mergesort(int[] arr,int left,int right) {
		if(right - left > 0) {
			int[] arr_1 = new int[(right - left)/2 + 1];
			int[] arr_2 = new int[(right - left + 1)/2];
			int j = 0;
			int k = 0;
			for(int i = left;i <= right;i++) {
				if(i <= (right + left)/2) {
					arr_1[j++] = arr[i];
				}else {
					arr_2[k++] = arr[i];
				}
			}
			Mergesort(arr_1,0,(right - left)/2);
			Mergesort(arr_2,0,(right - left - 1)/2);
			Merge(arr_1,arr_2,arr);
		}
	}
	public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
		int i = 0;
		int j = 0;
		int k = 0;
		int L1 = arr_1.length;
		int L2 = arr_2.length;
		while(i < L1 && j < L2) {
			if(arr_1[i] <= arr_2[j]) {
				arr[k] = arr_1[i];
				i++;
			}else {
				arr[k] = arr_2[j];
				j++;
			}
			k++;
		}
		if(i == L1) {
			for(int t = j;j < L2;j++)
				arr[k++] = arr_2[j];
		}else {
			for(int t = i;i < L1;i++)
				arr[k++] = arr_1[i];
		}
	}
}

若有错误，麻烦指正，不胜感激。