Java 中三种常用的排序方法

今天重新学习类三种排序方法，按照排序速度依次是冒泡排序，选择排序和插入排序。
以下示例皆为从小到大的排序

1.冒泡排序

每一次比较都可能要交换元素。
冒泡排序的思想是：
每一轮开始的时候，将第一个元素（a）开始与其后的元素（b）依次进行比较，将较大的元素（设为 m）放到后面，并将 m 与其后的另外一个元素继续进行比较，直到最后一个没有排好序的元素。
在接下来一轮的排序中，刚才以及之前选出来的、已经排好顺序的最大值不用参与排序。
依次类推，总共遍历 n-1 轮，即可完成排序。
具体代码如下：

 void bubble(int[] arr){
	int temp;
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = 0; j < arr.length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

	System.out.println("\n--bubble :");
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
}

2.选择排序

每次比较的时候不交换
选择排序的思想：
每次比较的时候找到的两个数中的较大值并记下其位置，等到当前一轮的遍历完成之后，将最后一个未排序元素与这一轮遍历找到的最大值交换
最多交换 n-1 次
代码如下：

   void select(int[] arr){

	for (int i = 0; i < arr.length; i++) {
		int maxIndex = 0;
		int temp = 0;

		for (int j = 1; j < arr.length - i; j++) {
			if (arr[maxIndex] < arr[j]) {
				maxIndex = j;
			}
		}

		temp = arr[maxIndex];
		arr[maxIndex] = arr[arr.length - i - 1];
		arr[arr.length - i - 1] = temp;
	}


	System.out.println("\n--select :");

	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
}

3.插入排序法

插入排序法思想：
将待排序的元素分为有序和无序两种，刚开始排序的时候假设只有第一个元素是有序的，其余 n-1 个元素都是无序的；
排序开始的时，将无序部分的一个元素（a）与有序部分的最后一个元素（b）进行比较，如果 a<b，则将 a 与 b 交换，再将 a 与下一个有序元素进行比较；否则，将 a 加到 b 后面，作为有序部分的最后一个元素。
接着再从无序部分取出一个元素与有序部分的元素依次比较，直达所有元素都为有序元素。
遍历 n-1 次
代码如下：

    void insertSort(int[] arr){

	for (int i = 1; i < arr.length; i++) {
		int instertValue = arr[i];

		for (int j = i - 1; j >= 0; j--) {
			if (instertValue < arr[j]) {
				arr[j+1] = arr[j];
				arr[j] = instertValue;
			}else {
				break;
			}
		}
	}

	/* 第二种表示形式
	for (int i = 1; i < arr.length; i++) {
		int instertVal = arr[i];
		int index = i - 1;

		while (index >= 0 && instertVal < arr[index]) {
			arr[index + 1] = arr[index];
			index--;
		}
		arr[index + 1] = instertVal;
	}
	*/

	System.out.println("\n--insertSort :");
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
}