目录
1、排序的概念
2、常见排序算法
3、直接插入排序
4、希尔排序
5、直接选择排序
6、堆排序
7、冒泡排序
1、排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，则称这种排序算法是稳 定的；否则称为不稳定的
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求能在内外存之间移动数据的排序
2、常见排序算法
3、直接插入排序
逻辑：
1. 假设这组数据的第一个元素是有序的
2. 从第二个元素开始，依次和前面的元素进行比较找到合适的位置就进行插入
/*** 时间复杂度：* 最坏情况下：O(n^2) 5 4 3 2 1* 最好情况下：O(n) 当数据越有序 排序越快 1 2 3 4 5* 适用于：待排序序列 已经基本上趋于有序了！* 空间复杂度：O(1)* 稳定性：稳定的* @param array*/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--) {// 这里加不加等号 和稳定有关系// 但是：本身是一个稳定的排序 可以实现为不稳定的排序// 本身是一个不稳定的排序 是不可能变成一个稳定的排序的if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}}直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
4、希尔排序
希尔排序法又称缩小增量法。
希尔排序法的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
// 希尔排序public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {gap /= 2;shell(array,gap);}}// 对每组进行插入排序public 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) {if(array[j] > tmp) {array[j+gap] = array[j];}else {break;}}array[j+gap] = tmp;}}希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序了，这样会很快。对整体而言，可以达到优化的效果
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此时间复杂度都不固定，严蔚敏版的数据结构教材给出的是 O(N^1.3) ~ O(N^1.5)4. 稳定性：不稳定
5、直接选择排序
直接选择排序/简单选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
/*** 选择排序：* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}swap(array,i,minIndex);}}
直接选择排序的特性总结
1. 直接选择排序非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2. 双向选择排序
代码思想：遍历一遍数组，找到数组的最大最小值，将最大值交换到后面，最小值交换到前面，直到 left 和 right 相遇。
1. 定义两个变量 minIndex , maxIndex来记录遍历一次数组得到数组的最大值和最小值的下标
2.定义 left 引用指向数组的第一个元素，定义 right 引用指向数组的最后一个元素
3. 遍历一遍后将最小值交换到前面，最大值交换到后面。left 向后走，right 向前走
4. 注意，找到 minIndex , maxIndex 后，先交换 minIndex 和 left 的值，如果 maxIndex 的指向刚好是数组的 left 指向，在交换 maxIndex 和 right 之前要更新 maxIndex 指向
时间复杂度也是 O(N^2)
public static void selectSort2(int[] array) {int left = 0;int right = array.length-1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left+1; i <= right ; i++) {if(array[i] < array[minIndex]) {minIndex = i;}if(array[i] > array[maxIndex]) {maxIndex = i;}}swap(array,minIndex,left);//防止 第一个是最大值 ，如果和最小的一换，最大值就跑到了原来最小值的位置if(maxIndex == left) {maxIndex = minIndex;}swap(array,maxIndex,right);left++;right--;}}6、堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序
private static void createHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {siftDown(array,parent,array.length);//alt+enter}}private static void siftDown(int[] array,int parent, int length) {int child = 2*parent + 1;while (child < length) {if(child+1 < length && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}/*** 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void heapSort(int[] array) {createHeap(array);int end = array.length-1;while (end > 0) {swap(array,0,end);siftDown(array,0,end);end--;}}堆排序的特性总结：
2. 时间复杂度：O(N*logN)
建堆：O(N)
排序：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
7、冒泡排序
基本思想：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序
public static void bubbleSort(int[] array) {//i代表的是趟数for (int i = 0; i < array.length-1; i++) {boolean flg = false;//j来比较 每个数据的大小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) {break;}}}冒泡排序的特性总结
2. 时间复杂度：O(N^2) ，最好情况下 可以达到O(N)
3. 空间复杂度：O(1)
4. 稳定性：稳定
由于篇幅有限，快速排序和归并排序放到下一小节
