排序算法一般分别是冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序，如果按原理划分，冒泡排序和快速排序都属于交换排序，直接插入排序和希尔排序属于插入排序，而简单选择排序和堆排序属于选择排序。
选择排序
扫描所有元素，将最小的与第一位交换位置，再扫描除第一位以外最小的与第二位交换位置。
//选择排序 public static void selectSort(int[] arr) { //在推导的过程，我们发现了规律，因此，可以使用for来解决 //选择排序时间复杂度是 O(n^2) for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr[0], 即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } //System.out.println("第"+(i+1)+"轮后~~"); //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101 } }
平均时间复制度：O(n^2) 最好情况：O(n^2) 最坏情况：O(n^2) 空间复杂度：O(1) 稳定性：不稳定
插入排序
对最前面两个元素进行排序，将第三个元素插入到合适位置，插入过程种要求，其他元素后移，为新插入元素腾出位置。
//插入排序 public static void insertSort(int[] arr) { int insertVal = 0; int insertIndex = 0; //使用for循环来把代码简化 for(int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; insertIndex = i - 1; // 即arr[1]的前面这个数的下标 // 给insertVal 找到插入的位置 // 说明 // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界 // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } // 当退出while循环时，说明插入的位置找到, insertIndex + 1 // 举例：理解不了，我们一会 debug //这里我们判断是否需要赋值 if(insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } //System.out.println("第"+i+"轮插入"); //System.out.println(Arrays.toString(arr)); } }
平均时间复制度：O(n^2) 最好情况：O(n) 最坏情况：O(n^2) 空间复杂度：O(1) 稳定性：稳定
希尔排序
冒泡排序
冒泡排序算法的算法过程如下：
①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
③. 针对所有的元素重复以上的步骤，除了最后一个。
④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
如果有一趟排序下来没交换，则代表已经有序。
// 将前面额冒泡排序算法，封装成一个方法 public static void bubbleSort(int[] arr) { // 冒泡排序 的时间复杂度 O(n^2), 自己写出 int temp = 0; // 临时变量 boolean flag = false; // 标识变量，表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { // 第二趟排序，就是将第二大的数排在倒数第二位 for (int j = 0; j < arr.length - 1 - 1 ; j++) // 第三趟排序，就是将第三大的数排在倒数第三位 for (int j = 0; j < arr.length - 1 - 2; j++) for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 } } }
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。
选择表中的一个元素当作划分元素，对表进行划分，小于划分元素的所有元素都放到划分元素左侧，大于划分元素的所有元素都放到元素右侧，最后再递归地对两个子划分段进行排序。
快速排序并不稳定，快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序。
public static void quickSort(int[] arr,int left, int right) { int l = left; //左下标 int r = right; //右下标 //pivot 中轴值 int pivot = arr[(left + right) / 2]; int temp = 0; //临时变量，作为交换时使用 //while循环的目的是让比pivot 值小放到左边 //比pivot 值大放到右边 while( l < r) { //在pivot的左边一直找,找到大于等于pivot值,才退出 while( arr[l] < pivot) { l += 1; } //在pivot的右边一直找,找到小于等于pivot值,才退出 while(arr[r] > pivot) { r -= 1; } //如果l >= r说明pivot 的左右两的值，已经按照左边全部是 //小于等于pivot值，右边全部是大于等于pivot值 if( l >= r) { break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移 if(arr[l] == pivot) { r -= 1; } //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移 if(arr[r] == pivot) { l += 1; } //交换 } // 如果 l == r, 必须l++, r--, 否则为出现栈溢出 if (l == r) { l += 1; r -= 1; } //向左递归 if(left < r) { quickSort(arr, left, r); } //向右递归 if(right > l) { quickSort(arr, l, right); } }
性能分析
（1）时间复杂度分析
快速排序最好情况下的时间复杂度为O(nlog2n)，待排序列越接近无序，本算法效率越高。最坏情况下的时间复杂度为O(n2)，待排序列越接近有序，本算法效率越低。平均时间复杂度为O(nlog2n)。就平均时间而言，快速排序是所有排序算法中最好的。快速排序的排序趟数与初始序列有关。
（2）空间复杂度分析
本算法空间复杂度为O(log2n)。快速排序是递归进行的，递归需要栈的辅助，因此它需要的辅助空间较多。
归并排序
开始时将表划分为大致相等的两段，然后对每个字表递归调用自身，直到划分为很多只含一个元素的子表，然后控制返回递归调用结构，算法将从两个递归调用中得到两个有序字段，合并为一个有序表。
比如初始数组：[24,13,26,1,2,27,38,15]
①分成了两个大小相等的子数组：[24,13,26,1] [2,27,38,15]
②再划分成了四个大小相等的子数组：[24,13] [26,1] [2,27] [38,15]
③此时，left < right 还是成立，再分：[24] [13] [26] [1] [2] [27] [38] [15]
此时，有8个小数组，每个数组都可以视为有序的数组了！！！，每个数组中的left == right，从递归中返回(从19行--20行的代码中返回)，故开始执行合并(第21行)：
merge([24],[13]) 得到 [13,24]
merge([26],[1]) 得到[1,26]
.....
.....
最终得到 有序数组
由上图可看出归并排序时间复杂度为n-1 ，为线性增长。
治的过程以倒数第二组为例：
public class MergeSort { public static <T extends Comparable<? super T>> void mergeSort(T[] arr) { T[] tmpArray = (T[]) new Comparable[arr.length]; mergeSort(arr, tmpArray, 0, arr.length - 1); } /** * * @param arr an array of Comparable items * @param tmpArray an array to place the merge result * @param left the left-most index of the array * @param right right-most index of the array */ private static <T extends Comparable<? super T>> void mergeSort(T[] arr, T[] tmpArray, int left, int right) { if (left < right) { int center = (left + right) / 2; mergeSort(arr, tmpArray, left, center); mergeSort(arr, tmpArray, center + 1, right); merge(arr, tmpArray, left, center + 1, right); } } /** * * @param arr an array of Comparable items * @param tmpArray an array to place the merge result * @param leftPos the left-most index of the subarray * @param rightPos the index of the start of the second half * @param rightEnd the right-most index of the subarray */ private static <T extends Comparable<? super T>> void merge(T[] arr, T[] tmpArray, int leftPos, int rightPos, int rightEnd) { int leftEnd = rightPos - 1; int numElements = rightEnd - leftPos + 1; int tmpPos = leftPos;// 只使用tmpArray中某一部分区域 while (leftPos <= leftEnd && rightPos <= rightEnd) { if (arr[leftPos].compareTo(arr[rightPos]) <= 0) tmpArray[tmpPos++] = arr[leftPos++]; else tmpArray[tmpPos++] = arr[rightPos++]; } while (leftPos <= leftEnd) tmpArray[tmpPos++] = arr[leftPos++];// copy rest of left half while (rightPos <= rightEnd) tmpArray[tmpPos++] = arr[rightPos++];// copy rest of right half // copy tmpArray back for (int i = 0; i < numElements; i++, rightEnd--) arr[rightEnd] = tmpArray[rightEnd];//只拷贝当前 merge 的部分数组 /** * 复制了整个数组中的所有元素 for(int i = 0; i < tmpArray.length; i++) arr[i] = tmpArray[i]; */ } //for test purpose public static void main(String[] args) { Integer[] arr = {24,13,26,1,2,27,38,15}; mergeSort(arr); for (Integer i : arr) System.out.print(i + " "); } }
基数排序
1) 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
2) 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
3) 基数排序(Radix Sort)是桶排序的扩展。
4) 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
堆排序
堆排序基本介绍
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] 小顶堆：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] i 对应第几个节点，i从0开始编号。
例：[4,6,8,5,9] 要求用堆排序对数组进行升序排列。
堆排序的基本思想是：
1）将待排序序列构造成一个大顶堆
2）此时，整个序列的最大值就是堆顶的根节点。
3）将其与末尾元素进行交换，此时末尾就为最大值。
4）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
步骤一 构成一个大顶堆。
（2）此时从最后一个非叶子节点开始（arr.length/2-1=5/2-1=1），从左至右，从下至上调整。
3).找的第二个非叶子节点 4，由于【4，9，8】中9元素最大，4和9交换。
4）这时，交换导致了子根【4，5，6】结构混乱，继续调整，【4，5，6】中6最大，交换4和6。
步骤二，将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
1）将堆顶元素9和末尾元素4进行交换。
2）重新调整结构，使其继续满足堆定义。
3）再将堆顶元素8与末尾元素5进行比较交换，得到第二大元素8.
4）后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。
1.先将无序序列构成一个堆，升序构成大顶堆，降序构成小顶堆。
2.将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端。
3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
//编写一个堆排序的方法 public static void heapSort(int arr[]) { int temp = 0; System.out.println("堆排序!!"); // //分步完成 // adjustHeap(arr, 1, arr.length); // System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6 // // adjustHeap(arr, 0, arr.length); // System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4 //完成我们最终代码 //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆 for(int i = arr.length / 2 -1; i >=0; i--) { adjustHeap(arr, i, arr.length); } /* * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端; 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 */ for(int j = arr.length-1;j >0; j--) { //交换 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } //System.out.println("数组=" + Arrays.toString(arr)); } //将一个数组(二叉树), 调整成一个大顶堆 /** * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 * 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6} * 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4} * @param arr 待调整的数组 * @param i 表示非叶子结点在数组中索引 * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少 */ public static void adjustHeap(int arr[], int i, int lenght) { int temp = arr[i];//先取出当前元素的值，保存在临时变量 //开始调整 //说明 //1. k = i * 2 + 1 k 是 i结点的左子结点 for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) { if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值 k++; // k 指向右子结点 } if(arr[k] > temp) { //如果子结点大于父结点 arr[i] = arr[k]; //把较大的值赋给当前结点 i = k; //!!! i 指向 k,继续循环比较 } else { break;//! } } //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部) arr[i] = temp;//将temp值放到调整后的位置 }
部分参考 https://blog.csdn.net/flyingsbird/article/details/79533075