1、冒泡排序（交换排序）
Demo.java
//冒泡排序中每一趟比较都会将最大的那个数找出来
public static void sort1(int[] arr) {
boolean sorted = true;// 假定有序
// 理论上会进行arr.length-1趟比较
for (int i = arr.length - 1; i > 0; i--) {
//sorted = true;// 每一趟比较初始都假定数组有序
for (int j = 0; j < i; j++) {
// 每趟比较的次数为arr.length - i;
if (arr[j] > arr[j + 1]) {
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
说明：
- 1、冒泡排序就是每次都是前一个数和后一个数进行比较，如果前面的数大，那么两者就交换位置。
- 2、冒泡排序每次都会找出一个“最大数”，所以每趟比较的次数递减，同时如果在某躺中没有发生过交换，那么显然数组就已经是有序的了，无序再进行下一趟排序。时间复杂度为
O(n^2)。平均时间复杂度为O(n^2)，是一种稳定的排序算法，空间复杂度为O(1)。
2、直接插入排序（插入排序）
/**
* 每次都是拿出其中一个元素（从arr[1]开始）和前面的元素进行比较，知道找到一个元素比自己小位置
* 然后进行位置变换
*/
public static void insertSort(int[] arr){
for(int i = 1; i < arr.length; i++){
int j = i - 1;//表示本元素前一个元素
int tmp = arr[i];
//j--表示会将本元素前面的所有元素遍历完，当然碰到比自己小的元素时就停止
//tmp < arr[j]就表示在前面所有元素中还没有找到了一个比自己小的，这里为假定为arr[j]
for(; j >= 0 && tmp < arr[j]; j--){//这里是升序，如果想要降序将条件改为tmp > arr[j]即可
arr[j+1] = arr[j];//此时将位置j前面的元素全部向前后移动
}
arr[j+1] = tmp;//这里之所以要j+1,表示将自己填到比自己小的元素的后面一个位置
}
}
说明：直接插入排序就是每次取一个元素（从arr[1]到最后一个）和自己前面位置的元素进行比较，如果前面的元素比自己大，则让其像后面移动，直到找到一个比自己小的元素则停止一轮循环，进入下一轮。举个例子：比如这样一个数组[5, 7, 8, 3]，此时我们从3这个元素开始。初始i = 3， 比较的情况如下：
5 7 8 3
5 7 8 8
5 7 7 8
5 5 7 8
3 5 7 8
时间复杂度为O(n^2)。平均时间复杂度为O(n^2)，是一种稳定的排序算法，空间复杂度为O(1)。
3、希尔排序（插入排序）
public static void shellSort(int[] arr) {
int j;
int len = arr.length;
for (int val = len / 2; val > 0; val /= 2) {
// 下面是对本次的所有分组做直接插入排序
for (int i = val; i < len; i++) {
int temp = arr[i];
/*
* 为什么每次都用temp比较呢？ 因为直接插入就是找到temp的合适位置。
* 为什么temp<arr[j-val]这个条件可以放在for内呢？ 因为原来的组内数据已经有序，找到位置就停止便是。
* 不甚理解的去看直接插入排序吧。
*/
for (j = i; j >= val && temp < arr[j - val]; j -= val) {
/*
* 为什么是arr[j-val]不是arr[j]呢？
* 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val]
*/
arr[j] = arr[j - val];
}
/*
* 注意不是arr[i] = temp 直接插入排序也是这样的。 为什么呢？ 因为j是位置，i是待插入元素
*/
arr[j] = temp;
}
}
}
说明：基本思想：算法先将要排序的一组数按某个增量d（Math.ceil(n/2),n为要排序数的个数）分成若干组，每组中记录的下标相差d。对每组中全部元素进行直接插入排序，然后再用一个较小的增量（Math.ceil(d/2)）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。这里要注意的是：对于每次d的取值，当d1为double类型时(d1/2)和整数类型的相除是不一样的，如果此时d1为double类型的3.0，那么Math.ceil((double)3.0 / 2)的值为2.0，而不是1.0。在d=1时排序之后就表示已经完成排序工作，此时排序停止。这里要注意的是：为什么是从int i = val开始，在i前面并且距离为val的元素只有一个，而后面的arr[j] = arr[j - val];以前考虑到了前面的这个元素，所以从val开始。最坏情况的时间复杂度为O(n^2)。平均时间复杂度为O(nlgn)，是一种不稳定的排序算法，空间复杂度为O(1)。
4、堆排序（选择排序）
堆排序的实现主要就是先构建一个二叉堆（和之前的不一样，这里是大根二叉堆），然后每次删除最大的数，这样输出就是由大到小的顺序，我们可以将删除的元素放到一个新的数组中再输出。
public static void heapsort(Comparable[] a) {
for (int i = a.length / 2; i >= 0; i--)
/* buildHeap */
percDown(a, i, a.length);
for (int i = a.length - 1; i > 0; i--) {
swapReferences(a, 0, i); /* deleteMax */
percDown(a, 0, i);
}
}
private static int leftChild(int i) {
return 2 * i + 1;
}
private static void percDown(Comparable[] a, int i, int n) {
int child;
Comparable tmp;
for (tmp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0)
child++;
if (tmp.compareTo(a[child]) < 0)
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
public static final void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
说明：首先构建一个大根树，然后每删除（将最后一个元素和根处元素交换）一个，进行下滤。（若不理解可以先看看二叉堆的实现）。时间复杂度为O(nlgn)，平均时间复杂度为O(nlgn)，是一种不稳定的排序算法，空间复杂度为O(1)。
5、归并排序
public static void mergeSort(Comparable[] a) {
Comparable[] tmpArray = new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
private static void mergeSort(Comparable[] a, Comparable[] tmpArray,
int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
private static void merge(Comparable[] a, Comparable[] tmpArray,
int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd)
if (a[leftPos].compareTo(a[rightPos]) <= 0)
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while (leftPos <= leftEnd)
tmpArray[tmpPos++] = a[leftPos++];
while (rightPos <= rightEnd)
tmpArray[tmpPos++] = a[rightPos++];
for (int i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
说明：归并排序较为容易理解。整体思路就是采用分治策略，将数组每次除以2来分成多个小块，然后进行排序（最后数组长度为2的时候只是两个数的比较），然后将多块已经排序的序列进行合并，其最坏运行时间为O(N lg N)。平均时间复杂度也是O(nlgn)，空间复杂度为O(1)。是一种稳定的排序算法。
6、快速排序（交换排序）
public static void quicksort(Comparable[] a) {
quicksort(a, 0, a.length - 1);
}
public static final void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
//取得枢纽元
private static Comparable median3(Comparable[] a, int left, int right) {
int center = (left + right) / 2;
if (a[center].compareTo(a[left]) < 0)
swapReferences(a, left, center);
if (a[right].compareTo(a[left]) < 0)
swapReferences(a, left, right);
if (a[right].compareTo(a[center]) < 0)
swapReferences(a, center, right);
swapReferences(a, center, right - 1);
return a[right - 1];
}
private static final int CUTOFF = 3;
private static void quicksort(Comparable[] a, int left, int right) {
if (left + CUTOFF <= right) {//至少有3个元素
Comparable pivot = median3(a, left, right);
int i = left, j = right - 1;
for (;;) {
while (a[++i].compareTo(pivot) < 0) {}//碰到相等或比pivot大的才停止
while (a[--j].compareTo(pivot) > 0) {}//碰到相等或比pivot小的才停止
if (i < j)
swapReferences(a, i, j);
else
break;
}
swapReferences(a, i, right - 1); //重新取得枢纽元素
quicksort(a, left, i - 1); // Sort small elements
quicksort(a, i + 1, right); // Sort large elements
} else
//做插入排序
insertionSort(a, left, right);
}
private static void insertionSort(Comparable[] a, int left, int right) {
for (int p = left + 1; p <= right; p++) {
Comparable tmp = a[p];
int j;
for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
说明：基本思想是选择一个基准元素,通常选择第一个元素或者最后一个元素（但是这种选择不好，上面我们给出的是三数中值分割法，但是如果要求不高可以直接使用第一个元素或者最后一个元素），通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。平均时间复杂度为O(n*lgn)，是一种不稳定的排序算法，空间复杂度为O(lgn)~O(n)。
7、简单选择排序（选择排序）
public static void selectSort(){
int a[] = { 1, 54, 6, 3, 78, 34, 12, 45 };
int len = a.length;
for(int i = 0; i < len; i++){
int j = i + 1;
int min = i ;
for(; j < len; j++){
if(a[j] < a[min]){
min = j;//min永远指向最小元素
}
}
//将最小值和索引为i的元素交换
int tmp = a[min];
a[min] = a[i];
a[i] = tmp;
for (int m = 0; m < a.length; m++)
System.out.print(a[m] + " ");
System.out.println();
}
}
说明：基本思想是在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。例如：
1 54 6 3 78 34 12 45
1 3 6 54 78 34 12 45
1 3 6 54 78 34 12 45
1 3 6 12 78 34 54 45
1 3 6 12 34 78 54 45
1 3 6 12 34 45 54 78
1 3 6 12 34 45 54 78
1 3 6 12 34 45 54 78
时间复杂度和平均时间复杂度都为O(n^2)，是一种稳定的排序算法，空间复杂度为O(1)。
