分类
1. 内部排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中。
2. 外部排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。
插入排序
思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
**分为**
- 直接插入排序
- 二分插入排序
- 希尔排序
直接插入排序
思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
图示：
代码实现：
public static void main(String[] args) { int[] a=new int[] {1,9,45,2,5,92,3,10,20}; a=insertSort(a); System.out.println(Arrays.toString(a)); } public static int[] insertSort(int[] arr) { for(int i=2;i<arr.length;i++) { int temp=arr[i];//暂存位置 for(int j=i;j>0;j--) { if(temp>arr[j-1]) { arr[j]=temp; break; }else { arr[j]=arr[j-1]; } } } return arr; }
平均时间复杂度为O(n2)
折半插入排序
在已形成的有序表中二分查找，并在适当位置插入，把原来位置上的元素向后顺移。
优点：比较的次数大大减少，全部元素比较次数仅为O(nlog2n)。平均为Ｏ（log2n)
时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2) 。
空间效率： O（1） 稳定性：稳定
希尔（shell）排序
基本思想：先取定一个正整数d1<n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行插入排序；
然后取d2<d1，重复上述分组和排序工作，直至取d1=1，即所有记录放在一个组中排序为止。
技巧：希尔排序中增量di有多种取法，我们可选取如d1=n/2,di+1=di/2。
优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。
取gap为length/2，一次次进行插入排序，gap变为gap/2，直到gap为1为止
希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。
研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。
交换排序
冒泡排序
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。（两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。）
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
前提：顺序存储结构
代码略
快速排序
从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；
然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。
步骤：
1.定义一个basic，随机指向，为了方便，这里演示指向最右边
2.定义一个left指向最左，一个right指向最右
3.左边比右边小，进行向右移动，左边比右边大或者相等，停止
4.右边比左边小，进行向左移动，直到下一步右边比左边大，然后交换
5.递归使左右堆分别进行快排
选择排序
直接选择排序
思路简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
首先，在n个记录中选择最小者放到data[1]位置；然后，从剩余的n-1个记录中选择最小者放到data[2]位置；…如此进行下去，直到全部有序为止。
优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构