一：排序的分类
排序主要分为内部排序和外部排序两大类：其中内部排序将所有的数据都加载到内存中；外部排序由于数据量过大，需要借助外部存储进行排序。主要学习内排序的八种排序算法。
二：各排序算法的稳定性与时间复杂度
三：插入排序
（1）直接插入排序
1 import java.lang.reflect.Array; 2 import java.util.Arrays; 3 4 public class Solution { 5 public static void main(String[] args) { 6 InsertSort(new int[] { 9 ,20 , 10, 13 , 12}); 7 } 8 public static void InsertSort(int [] arr){ 9 int value;//待插入元素 10 int index;//初始值为待插入元素前一个元素的索引 11 12 for(int i= 1 ; i< arr.length;i++){ 13 //i从第二个元素开始，默认第一个元素是有序的 14 //循环条件是小于数组长度，因为也要将最后一个元素插入到前面的序列 15 value = arr[i]; 16 index = i - 1;//初始为前一个元素 17 while(index >=0 && value < arr[index]){ 18 //需要保证index合法 19 //每当前面的元素比待插入元素大，就向后移动 20 arr[index + 1] = arr[index]; 21 //不用怕覆盖，因为value保存着待插入的值 22 index--; 23 } 24 //当退出循环，表明已经找到了待插入位置，即index + 1 25 arr[index + 1] = value; 26 } 27 28 System.out.println(Arrays.toString(arr)); 29 } 30 }
简单插入排序存在的问题：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
（2）希尔排序
希尔排序时简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
基本思想：
1 /** 2 * 希尔排序演示 3 */ 4 public class ShellSort { 5 public static void main(String[] args) { 6 int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; 7 shellSort(arr); 8 9 for (int i : arr) { 10 System.out.print(i + "\t"); 11 } 12 } 13 14 private static void shellSort(int[] arr) { 15 //step:步长 16 for (int step = arr.length / 2; step > 0; step /= 2) { 17 //从第step个元素开始，逐个对当前元素所在的组进行插入排序。 18 for (int i = step; i < arr.length; i++) { 19 int value = arr[i]; 20 int j=i; 21 //找插入位置，并将当前组中比当前元素大的值后移 22 while(j-step>=0 && arr[j]<arr[j-step]){ 23 arr[j]=arr[j-step]; 24 j -= step; 25 } 26 //找到插入位置 27 arr[j] = value; 28 } 29 } 30 } 31 }
四：选择排序：
（1）简单选择排序（每次选择最小的值放在组头，缩小组的范围）（ O(n2) ）
基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
（2）堆排序
基本思想：
/** * 堆排序演示 * */ public class HeapSort { public static void main(String[] args) { // int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; int[] arr = {16, 7, 3, 20, 17, 8}; heapSort(arr); for (int i : arr) { System.out.print(i + " "); } } /** * 创建堆， * @param arr 待排序列 */ private static void heapSort(int[] arr) { //创建堆 for (int i = (arr.length - 1) / 2; i >= 0; i--) { //从第一个非叶子结点从下至上，从右至左调整结构 adjustHeap(arr, i, arr.length); } //调整堆结构+交换堆顶元素与末尾元素 for (int i = arr.length - 1; i > 0; i--) { //将堆顶元素与末尾元素进行交换 int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //重新对堆进行调整 adjustHeap(arr, 0, i); } } /** * 调整堆 * @param arr 待排序列 * @param parent 父节点 * @param length 待排序列尾元素索引 */ private static void adjustHeap(int[] arr, int parent, int length) { //将temp作为父节点 int temp = arr[parent]; //左孩子 int lChild = 2 * parent + 1; while (lChild < length) { //右孩子 int rChild = lChild + 1; // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } // 如果父结点的值已经大于孩子结点的值，则直接结束 if (temp >= arr[lChild]) { break; } // 把孩子结点的值赋给父结点 arr[parent] = arr[lChild]; //选取孩子结点的左孩子结点,继续向下筛选 parent = lChild; lChild = 2 * lChild + 1; } arr[parent] = temp; } }
五：交换排序
（1）冒泡排序
基本思想：
优化：（如果在某次排序中没有发生一次交换，就可以提前结束冒泡排序）
（2）快速排序
基本思想：
1 public class Solution { 2 public void sortArray(int[] A) { 3 if (A == null) return; 4 helper(A, 0, A.length - 1); 5 } 6 7 private void helper(int[] A, int left, int right) { 8 if (left >= right) { 9 return; 10 } 11 int pivot = A[left + (right - left) / 2]; 12 int i = left, j = right; 13 while (i <= j) { 14 while (i <= j && A[i] < pivot) { 15 i++; 16 } 17 while (i <= j && A[j] > pivot) { 18 j--; 19 } 20 if (i <= j) { 21 int tmp = A[i]; 22 A[i] = A[j]; 23 A[j] = tmp; 24 i++; 25 j--; 26 } 27 } 28 helper(A, left, j); 29 helper(A, i, right); 30 } 31 }
原文：https://www.cnblogs.com/Melo-ccyfy/p/14614416.html