排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
常见的排序算法：
1.直接插入排序
基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。也就是说当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
代码实现：
1.首先我们手中仅有一个数。
2.我们去出第二个数，大于手中的数就放到右边，小于就放到左边。
3.当数组中没有元素时，就代表排序结束。
public static void insertSort(int[] array) { for(int i = 1;i < array.length;i++) { //插入的数 int tmp=array[i]; int j=i-1; for(;j >= 0;j--) { //两种情况； //1.插入的数大于前面的数；2.插入的数小于前面的数 //大小于决定排列顺序 if(array[j]>tmp) { array[j+1]=array[j]; }else { break; } } array[j+1]=tmp; } }
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.希尔排序
基本思想
希尔排序是直接插入排序的优化版
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
代码实现 （递归实现）
1.将待排数据进行分组，分组之后，将各组的数据进行直接插入排序
2.第一组个数一般是数组长度的二倍，排序直到每一组只有一个元素。
3.仅剩一个元素时，再进行一次整体的插入排序来完成对数据的排序。
public static void shellSort(int[] array) { int gap=array.length; while (gap>1) { shell(array,gap); gap/=2; } shell(array,gap); } //插入排序 private static void shell(int[] array,int gap) { for(int i = gap;i < array.length;i++) { //插入的数 int tmp=array[i]; int j=i-gap; for(;j >= 0;j-=gap) { //两种情况； //1.插入的数大于前面的数；2.插入的数小于前面的数 //大小于决定排列顺序 if(array[j]<tmp) { array[j+gap]=array[j]; }else { break; } } array[j+gap]=tmp; } }
希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
3.直接选择排序
基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
代码实现：
1.假设数组元素第一个元素是最小的元素。
2.对数组进行遍历，当遇到比minNub这个值小的元素，就将他赋值到minNub。
3.最终将minNub放到i下标处。
public static void selectSort(int array[]) { for (int i = 0; i < array.length; i++) { //存储最小值 int minNub=array[i]; //找最小值 for (int j = i+1; j < array.length; j++) { if(minNub>array[j]) { int tmp=array[j]; array[j]=minNub; minNub=tmp; } } //将最小值放到最前方 array[i]=minNub; } }
直接选择排序的特性总结
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
4.堆排序
基本思路
排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
代码实现
1.将根结点与最后一个叶子节点互换。
2.对堆进行向下调整，转换为大顶堆
3.此时，根结点是数组中最大的元素，将他与最后一个叶子节点进行互换。
4.循环上方1、2、3，最终得到的就是有序的数组
/** * 堆排序 * @param array */ public static void heapSort(int[] array) { createBigHeap(array); int end = array.length-1; while (end > 0) { swap(array,0,end); shiftDown(array,0,end); end--; } } /** * 建一个大根堆 * @param array */ private static void createBigHeap(int[] array) { for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { shiftDown(array,parent,array.length); } } /** * 对建立的堆进行向下调整 * @param array * @param parent * @param len */ private static void shiftDown(int[] array,int parent,int len) { int child = 2*parent+1; while (child < len) { if(child+1 < len && array[child] < array[child+1]) { child++; } if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } }
堆排序的特性总结
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
5.冒泡排序
基本思想
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特
点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
代码实现：
1.拿到一个元素，对数组中的每一个元素进行比较，小于就不换，大于就换位置。
2.直到每个元素都进行互换后，就得到有序数组。
/** * 冒泡排序 * @param array */ public static void bubbleSort(int[] array) { for (int i = 0; i < array.length-1; i++) { boolean flg=false; for (int j = 0; j < array.length-1-i; j++) { if(array[j]>array[j+1]) { swap(array,j,j+1); flg=true; } } if(flg==false) { return; } } }
冒泡排序的特性总结
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
6.快速排序
基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
代码实现：
1.找基准值，这个基准值是随机的。
2.将所有的小于基准值的数都放到基准值的左边，将所有的大于基准值的数都放到基准值的右边。
3.然后将左边和右边的排的数再看出一个数组再次进行上方1、2操作，知道数组中的元素只剩一个，这时待排数据就有序了。
/*** * 快速排序（递归实现） * 挖坑法 * @param array */ public static void quickSort1(int[] array) { quick(array,0,array.length-1); } /*** * 通过递归对左数和右树排序 * @param array * @param start * @param end */ private static void quick(int[] array,int start,int end) { if(start>=end) { return; } int pivot=partition(array,start,end); //左树排序 quick(array,start,pivot-1); //右树排序 quick(array,pivot+1,end); } /*** * 找基准值 * @param array * @param left * @param right * @return */ private static int partition(int[] array,int left,int right){ int tmp=array[left]; while (left<right) { //找比tmp小的值 while (left<right && array[right]>=tmp) { right--; } array[left]=array[right]; //找比tmp大的值 while (left<right && array[left]<=tmp) { left++; } array[right]=array[left]; } //将最后一个坑补上 array[left]=tmp; return left; }
快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
7.归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
代码实现：
/** * 归并排序 * @param array */ public static void mergeSort(int[] array, int left, int right) { if (left < right) { int mid = left + ((right - left) >> 1); mergeSort(array,left,mid); mergeSort(array,mid+1,right); merge(array,left,mid,right); } } //归并 public static void merge(int[] arr,int left, int mid, int right) { //第一步，定义一个新的临时数组 int[] tempar = new int[right -left + 1]; int temp1 = left, temp2 = mid + 1; int index = 0; //对应第二步，比较每个指针指向的值，小的存入大集合 while (temp1 <= mid && temp2 <= right) { if (arr[temp1] <= arr[temp2]) { tempar[index++] = arr[temp1++]; } else { tempar[index++] = arr[temp2++]; } } //对应第三步，将某一小集合的剩余元素存到大集合中 if (temp1 <= mid) System.arraycopy(arr, temp1, tempar, index, mid - temp1 + 1); if (temp2 <= right) System.arraycopy(arr, temp2, tempar, index, right -temp2 + 1); //将大集合的元素复制回原数组 System.arraycopy(tempar,0,arr,0+left,right-left+1); }
归并排序总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
