【Java学习笔记】排序算法：冒泡排序、快速排序、选择排序、插入排序算法思想及其Java代码实现

1、冒泡排序

算法思想：

从第一个元素开始，每个元素都与它的下一个元素比较，如果该元素比下一个元素大，则交换他们两个的值。这样一轮操作以后，整个数组中最大的值就被换到了最后一个，同理，对最后一个元素之前的元素再次进行重复操作，每次都找到剩余元素中的最大值并换到未排序部分的最后一个，就像泡泡一样不断浮出水面。对于有n个元素的序列，循环操作n-1次即可完成排序。

代码实现：

import java.util.Random;

public class AlgorithmExercise4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[10];
		Random rand = new Random();
		for(int i = 0;i < 10;i++) {
			a[i] = rand.nextInt(100)+1;
		}
		printArr(a);
		BubbleSort(a);//冒泡排序
		printArr(a);
	}
	
	public static void printArr(int[] a) {
		for(int i = 0;i < a.length;i++) {
			System.out.print(a[i]+"   ");
		}
		System.out.println();
	}
	
	public static void BubbleSort(int[] a) {
		int temp = 0;
		for(int i = a.length-1;i > 0;i--) {
			for(int j = 0;j < i;j++) {
				if(a[j] > a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		System.out.println("冒泡排序完成");
	}

}

2、快速排序

算法思想：

快速排序采用了分治法的思想，速度通常比其他算法更快，因此常被采用。
每次先找一个元素（第一个）作为“基准”，把剩余的元素按照比基准值小or大分开，比基准值小的放在前面，比基准值大的放在后面，完成后再将“基准”插入两者之间。这样分开后虽然“基准”前面的值都比“基准”小，后面的值都比“基准”大，但是它们仍未排序，此时对前后两部分递归进行同样的操作，直至进行递归操作的目标只剩下一个元素无法再排序，整个序列的排序就完成了。

代码实现：

import java.util.Random;

public class AlgorithmExercise4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[10];
		Random rand = new Random();
		for(int i = 0;i < 10;i++) {
			a[i] = rand.nextInt(100)+1;
		}
		printArr(a);
		quickSort(a,0,a.length-1);//快速排序
		printArr(a);
	}
	
	public static void printArr(int[] a) {
		for(int i = 0;i < a.length;i++) {
			System.out.print(a[i]+"   ");
		}
		System.out.println();
	}
	
	public static void quickSort(int[] a,int left,int right) {
		if(left > right) {
			return;
		}
		int base = a[left];//第一个元素作为基准
		int i = left;
		int j = right;
		int temp = 0;
		//寻找需要交换的元素
		while(i != j) {
			while(a[j] >= base && i < j) {
				j--;
			}
			while(a[i] <= base && i < j) {
				i++;
			}
			if(i < j) {
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		a[left] = a[i];
		a[i] = base;//把基准插入分类中间
		quickSort(a,left,i-1);//对前面部分进行递归
		quickSort(a,i+1,right);//对后面部分进行递归
		System.out.println("快速排序递归中...");
	}

}

3、选择排序

算法思想：

第一次逐个比较整个数组，寻找其中最小值的元素下标，待比较完成后把最小值和第一个元素交换，把最小值放在最前面。第二次对第一个元素（刚找出来的最小值）以外的剩余元素进行同样的操作，每次都把剩余元素中的最小值放在未排序部分的第一个。对于有n个元素的序列，循环操作n-1次即可完成排序。

代码实现：

import java.util.Random;

public class AlgorithmExercise4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[10];
		Random rand = new Random();
		for(int i = 0;i < 10;i++) {
			a[i] = rand.nextInt(100)+1;
		}
		printArr(a);
		selectSort(a);//选择排序
		printArr(a);
	}
	
	public static void printArr(int[] a) {
		for(int i = 0;i < a.length;i++) {
			System.out.print(a[i]+"   ");
		}
		System.out.println();
	}
	
	public static void selectSort(int[] a) {
		int min = 0;//用于记录最小值下标
		int temp = 0;
		for(int i = 0;i < a.length;i++) {
			min = i;
			for(int j = i;j < a.length;j++) {
				if(a[j] < a[min]) {
					min = j;
				}
			}
			temp = a[min];
			a[min] = a[i];
			a[i] = temp;
		}
		System.out.println("选择排序完成");
	}

}

4、插入排序

算法思想：

第一次先选择数组中的前两个元素进行排序，排好后让后一个元素也加入排序，如果新加入的元素比前一个元素的值小，就交换它们两个的位置，直至新加入的元素比前一个元素大或已经位于数组开头。就这样每次插入一个元素进行排序，直至所有的元素都已经加入排序。

代码实现：

import java.util.Random;

public class AlgorithmExercise4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[10];
		Random rand = new Random();
		for(int i = 0;i < 10;i++) {
			a[i] = rand.nextInt(100)+1;
		}
		printArr(a);
		insertSort(a);//插入排序
		printArr(a);
	}
	
	public static void printArr(int[] a) {
		for(int i = 0;i < a.length;i++) {
			System.out.print(a[i]+"   ");
		}
		System.out.println();
	}

	public static void insertSort(int[] a) {
		for(int i = 1;i < a.length;i++) {
			for(int j = i;j > 0;j--) {
				if(a[j] < a[j-1]) {
					a[j] = a[j] ^ a[j-1];
					a[j-1] = a[j] ^ a[j-1];
					a[j] = a[j] ^ a[j-1];
				}else {
					break;
				}
			}
		}
		System.out.println("插入排序完成");
	}
	
}