import java.util.Arrays;
public class SortTest {
public static void main(String... args) {
int[] arr = {12, 55, 22, 166, 2, 75, 30, 100, 200};
bubbleSortArray(arr); //冒泡排序
selectSortArray(arr); //选择排序
insertSortArray(arr); //插入排序
shellSortArray(arr); //希尔排序
quickSortArray(arr, 0, arr.length -1); //快速排序
System.out.println("快速排序结果：" + Arrays.toString(arr));
int[] arr2 =mergeSortArray(arr);
System.out.println("归并排序结果：" + Arrays.toString(arr2));
}
/**
* 冒泡（Bubble）排序:效率 O（n²）,适用于排序小列表
* 原理：比较两个相邻的元素，将值大的元素交换至右端。
* 思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。
* 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
* 然后比较第2个数和第3个数，将小数放前，大数放后，
* 如此继续，直至比较最后两个数，将小数放前，大数放后。
* 重复第一趟步骤，直至全部排序完成。
*
* @param arr
* @return void
*/
private static void bubbleSortArray(int[] arr) {
int len = arr.length;
for (int i =1; i < len; i++) {
for (int j =0; j < len - i; j++) {
if (arr[j] > arr[j +1]) { //比较交换相邻元素
int temp;
temp = arr[j];
arr[j] = arr[j +1];
arr[j +1] = temp;
}
}
}
System.out.println("冒泡排序结果：" + Arrays.toString(arr));
}
/**
* 选择排序:效率O（n²），适用于排序小的列表
* 原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
* 也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
* 基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
* 思路：给定数组 int[] arr={里面n个数据}；
* 第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arr[1]交换；
* 第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；
* 以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
*
* @param arr
* @return void
*/
private static void selectSortArray(int[] arr) {
int len = arr.length;
int minIndex;
for (int i =0; i < len -1; i++) {
minIndex = i;
for (int j = i +1; j < len; j++) {
if (arr[j] < arr[minIndex]) minIndex = j; //记下目前找到的最小值所在的位置
}
if (minIndex != i) {
//找到最小项交换，将这一项移到列表中的正确位置
int temp;
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
System.out.println("选择排序结果：" + Arrays.toString(arr));
}
/**
* 插入排序:最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表 ;若列表基本有序，则插入排序比冒泡、选择更有效率。
* 原理：每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。
* 就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O（n²）。
* 这种算法是稳定的排序方法。
*
* @param arr
*/
private static void insertSortArray(int[] arr) {
int len = arr.length;
for (int i =1; i < len; i++) {
//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分
int temp = arr[i]; //temp标记为未排序第一个元素
int j = i -1;
while (j >=0 && arr[j] > temp) {
//将temp与已排序元素从小到大比较，寻找temp应插入的位置
arr[j +1] = arr[j];
j--;
}
arr[j +1] = temp;
}
System.out.println("插入排序结果：" + Arrays.toString(arr));
}
/**
* 希尔排序：缩小增量排序，适用于排序小列表。
* 效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。
* 建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
* 希尔排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
* 思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，
* 待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
* 思路：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，
* 所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。
* 然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
* 由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，
* 子序列中元素个数逐渐增多，由于前面大多数元素已经基本有序，所以排序速度仍然很快。
*
* @param arr
*/
private static void shellSortArray(int[] arr) {
int len = arr.length;
for (int incr =3; incr >0; incr--) {
//增量递减，以增量3，2，1为例
for (int l =0; l < (len -1) / incr; l++) {
//重复分成的每个子列表
for (int i = l + incr; i < len; i += incr) {
//对每个子列表应用插入排序
int temp = arr[i];
int j = i - incr;
while (j >=0 && arr[j] > temp) {
arr[j + incr] = arr[j];
j -= incr;
}
arr[j + incr] = temp;
}
}
}
System.out.println("希尔排序结果：" + Arrays.toString(arr));
}
/**
* 快速排序：在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。
* 思想：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
* 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* 时间复杂度：数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。
* 快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
* 空间复杂度：快速排序在每次分割的过程中，需要1个空间存储基准值。而快速排序的大概需要Nlog2N次的分割处理，占用空间也是Nlog2N个。
*
* @param arr
* @param left 数组的左边界(例如，从起始位置开始排序，则left=0)
* @param right 数组的右边界(例如，排序截至到数组末尾，则right=a.length-1)
*/
private static void quickSortArray(int[] arr, int left, int right) {
if (left < right) {
int i, j, k;
i = left;
j = right;
k = arr[i];
while (i < j) {
while (i < j && arr[j] > k) j--; //从右向左找第一个小于k的数
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] < k) i++; //从左向右找第一个大于k的数
if (i < j) arr[j--] = arr[i];
}
arr[j] = k;
quickSortArray(arr, left, i -1); //递归调用
quickSortArray(arr, i +1, right); //递归调用
}
}
/**
* 归并排序：
* 思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排序集合。
* @param arr
* @return
*/
private static int[]mergeSortArray(int[] arr) {
for (int gap =1; gap < arr.length; gap =2 * gap) {
int i =0;
// 归并gap长度的两个相邻子表
for (i =0; i +2 * gap -1 < arr.length; i +=2 * gap)
merge(arr, i, i + gap -1, i +2 * gap -1);
// 余下两个子表，后者长度小于gap
if (i + gap -1 < arr.length)
merge(arr, i, i + gap -1, arr.length -1);
}
return arr;
}
private static void merge(int[] arr, int low, int mid, int high) {
int i = low; // i是第一段序列的下标
int j = mid +1; // j是第二段序列的下标
int k =0; // k是临时存放合并序列的下标
int[] arr2 =new int[high - low +1]; //arr2是临时合并序列
// 扫描第一段和第二段序列，直到有一个扫描结束
while (i <= mid && j <= high) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if (arr[i] <= arr[j]) {
arr2[k] = arr[i];
i++;
k++;
} else {
arr2[k] = arr[j];
j++;
k++;
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while (i <= mid) {
arr2[k] = arr[i];
i++;
k++;
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while (j <= high) {
arr2[k] = arr[j];
j++;
k++;
}
// 将合并序列复制到原始序列中
for (k =0, i = low; i <= high; i++, k++) arr[i] = arr2[k];
}
}
运行结果：
冒泡排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
选择排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
插入排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
希尔排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
快速排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
归并排序结果：[2, 12, 22, 30, 55, 75, 100, 166, 200]
