Java-排序算法

排序:按照指定的顺序排列出来.

升序:从小到大:

降序:从大到小.

--------------------------------------------

排序的分类：

选择排序（直接选择排序、堆排序）

交换排序(冒泡排序、快速排序)

插入排序（直接插入排序、二分法插入排序、Shell排序）

归并排序等。

排序有升序排列和降序排列之分，我们现在单讲升序排列：

我们主要讲解冒泡，选择，插入排序，当然在开发中因为性能问题，我们都不会自己写排序算法，不过排序在笔试题里却是常客。

若有下列int类型数组需要排序：

int[] arr = {2,9,6,7,4,1};

冒泡排序(Bubble Sort)：

这是最简单的排序法，基本思路：

对未排序的各元素从头到尾依次比较相邻的两个元素大小关系，若大于则交换位置，经过第一轮比较排序后可得出最大值，然后使用同样的方法把剩下的元素

逐个比较即可。

可以看出若有N个元素，那么一共要进行N-1轮比较，第M轮要进行N-M次比较。（若6个元素，要进行6-1轮比较，第一轮比较6-1次，第三轮比较6-3次）。


选择排序(Selection Sort)：

基本思路：选择某个索引位置的元素，然后和后面元素依次比较，若大于则交换位置，经过第一轮比较排序后可得出最小值，然后使用同样的方法把剩下的元

素逐个比较即可。

可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后。

第一轮从arr[0]和后面元素相比较，第二轮从arr[1]和后面的元素相比较，依次类推。N个数要进行N-1轮。选择排序每一轮只进行一次交换，相对于冒泡排

序效率高一些。

static void selectSort(int[] arr) {
	for (int times = 0; times < arr.length - 1; times++) {
		int minIndex = times;
		for (int i = times + 1; i < arr.length; i++) {
			if (arr[i] < arr[minIndex]) {
				minIndex = i;
			}
		}
		swap(arr, times, minIndex);
	}
}