排序：顾名思义就是就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序的稳定性（面试）：两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
一、直接插入排序
思想：第一个数为有序的，从第二个无序数开始与第一个数比较并确定放在第一个数的前面还是后面。
1、时间复杂度：
最好情况：O(n) ；（数据是有序的。数据越有序，速度越快）。
最坏情况和平均：O(n^2)；（数据是逆序的）。
2、空间复杂度：O(1)；
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--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
二、希尔排序
思想：也叫缩小增量法，是直接插入排序的优化，先选定一个整数（gap），把待排序文件中所有记录分成（gap）组，在每组中再进行插入排序，直到分组（gap）为1时，进行最后一次排序。
1、时间复杂度：在 O(n^1.3 ) ~ O(n^1.5) 之间。与（gap）的大小有关。
2、空间复杂度：O(1)；
3、稳定性：不稳定。
三、选择排序
思想：每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。(定义i和j分别为第一个数和第二个数，让j遍历整个数据去和i比较)
1、时间复杂度：O(n^2)；
2、空间复杂度：O(1)；
3、稳定性：不稳定。
public static void selectSort(int[] array) { // 选择排序
for (int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length; j++) {
if(array[i] > array[j]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
四、冒泡排序
思想：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序 。
1、时间复杂度：
最好情况：O(n); （数据有序或代码有优化）
最坏情况和平均：O(n^2)；（数据逆序或代码没有优化）
2、空间复杂度：O(1)；
3、稳定性：稳定。
public static void bubbleSort(int[] array) { // 冒泡排序
for (int i = 0; i < array.length-1; i++) { // i记录比较次数，如有5个数，比较4次。
boolean flg = false; // 另一种优化
for (int j = 0; j < array.length-1-i; j++) { //一种优化 -i
if(array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if(!flg) {
break;
}
}
}
五、堆排序
思想：基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆。
1、时间复杂度：O(n*log n)；
2、空间复杂度：O(1)；
3、稳定性：不稳定。
public static void heapSort(int[] array) { //堆排序
//需要一个大根堆
createHeap(array);
int end = array.length-1;
while (end > 0) { //在不破坏树的结构下，利用最后一个和第一个交换，
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
shiftDown(array,0,end);
end--;
}
}
public static void createHeap(int[] array) { //在创建大根堆的时候要进行向下调整。
for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) { //从最后一个元素开始遍历,利用公式parent=(child-1)/2.想象那个树
shiftDown(array,i,array.length);
}
}
public 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]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
六、快速排序
思想：
(1) 从待排序区间选择一个数，作为基准值 (pivot) ； (2). Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边； (3). 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1 ，代表已经有序，或者小区间 的长度 == 0 ，代表没有数据。 1、时间复杂度：最好情况和平均：O(n*log n) ；（每次能够均匀的分割待排序序列）
最坏情况：O(n^2)；（数据是有序的，会出现单分支情况）
2、空间复杂度：
最好情况和平均：O(log n)；
最坏情况：O(n)；
3、稳定性：不稳定。
4、代码中有递归的方法和非递归的方法（挖坑法partition)public static void quickSort(int[] array){ //快速排序（递归思想）
quick(array,0,array.length-1);
}
public static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
//防止递归的太深，进行两次优化
//1.插入排序
if((end-start+1) <= 48) {
//直接插入排序
insertSort2(array,start,end);
return;
}
//2.三数取中法，找基准
mid_three(array,start,end);
int pivot = partition(array,start,end); //调用基准函数
quick(array,start,pivot-1); //递归基准左边
quick(array,pivot+1,end); //递归基准右边
}
public static void swap(int[] array,int left,int right) { //交换的函数
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
public static void mid_three(int[] array,int left,int right) {
int mid = (left+right) / 2;
//array[mid] <= array[left] <= array[right]
if(array[left] > array[right]) {
swap(array,left,right);
}//array[left] <= array[right]
if(array[left] < array[mid]) {
swap(array,left,mid);
}//array[left] >= array[mid]
if(array[mid] > array[right]) {
swap(array,mid,right);
}//array[right] >= array[mid]
}
public static void insertSort2(int[] array,int low,int high) {
for (int i = low+1; i <= high; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= low; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
public static void quickSortNor(int[] array) { //快速排序(非递归)
Stack stack = new Stack<>(); //每次入栈的是基准左边的开始和结束的下标（low，pivot-1）
// 和基准右边的开始和结束下标（pivot+1，high）
int start = 0;
int end = array.length-1;
int pivot = partition(array,start,end); //将0下标与最后一个下标传过去返回这个基准下标
if(pivot > start+1) { //确保基准左边最少有两个数据
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end -1) { //确保基准右边最少有两个数据
stack.push(pivot+1);
stack.push(end);
}
while ( !stack.empty()) { //循环的去调基准方法，将数据拍到有序
end = stack.pop(); //弹下标作为下一组调基准的开始和结束下标
start = stack.pop();
pivot = partition(array,start,end);
if(pivot > start+1) {
stack.push(start);;
stack.push(pivot-1);
}
if(pivot < end -1) {
stack.push(pivot+1);
stack.push(end);
}
}
}
public static int partition(int[] array,int start,int end) { //以基准为主将数据分为两部分
//基准左边都是比基准小的，右边比基准大。
int tmp = array[start];
while( start < end) {
while(start < end && array[end] >= tmp) { //从右向左找比tmp小的进行交换赋值
end--;
}
array[start] = array[end];
while(start < end && array[start] <= tmp) {//从左向右找比tmp大的进行交换赋值
start++;
}
array[end] = array[start];
}
array[start] = tmp; //代码下来，只能弄一次基准，
return start; //返回这个基准的下标。
}
七、归并si
思想：采用分治法，先分解，再将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
1、时间复杂度：O(n*log n)；
2、空间复杂度：O(n)；
3、稳定性：稳定。
4、代码中有递归的方法和非递归的方法
public static void mergeSort(int[] array) { //归并排序（递归）
mergeSortIn(array,0,array.length-1);
}
public static void mergeSortNor(int[] array) { //归并排序（非递归）
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i = i+gap*2) {
int low = i;
int mid = low+gap-1;
int high = mid+gap;
if(mid >= array.length) {
mid = array.length-1;
}
if(high >= array.length) {
high = array.length-1;
}
merge(array,low,mid,high);
}
gap = gap*2;
}
}
public static void mergeSortIn(int[] array,int start,int end) {
if(start >= end) {
return;
}
int mid = (start +end) / 2;
mergeSortIn(array,start,mid);//递归左边分割
mergeSortIn(array,mid+1,end);//递归右边分割
merge(array,start,mid,end);//递归合并并排序
}
public static void merge(int[] array,int start,int mid,int end) { //合并并排序
int s1 = start;
int e1 = mid;
int s2 = mid+1;
int e2 = end;
int[] tmpArr = new int[end-start+1];
int k = 0;
while (s1 <= e1 && s2 <= e2) {
//不加等于号 就不是稳定的排序
if(array[s1] <= array[s2]) {
tmpArr[k++] = array[s1++];
}else {
tmpArr[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmpArr[k++] = array[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = array[s2++];
}
//写回数据到原来的数组
for (int i = 0; i < k; i++) {
array[i+start] = tmpArr[i];
}
}
八、排序总结
| 排序方法 | 时间复杂度（最好） | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定性 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(1) | 不稳定 | ||
| 希尔排序 | O(n^1.3 ) ~ O(n^1.5) | O(1) | 不稳定 | ||
| 堆排序 | O(n*log n) | O(1) | 不稳定 | ||
| 快速排序 | O(n*log n) | O(n*log n) | O(n^2) | O(log n) ~ O(n) | 不稳定 |
| 归并排序 | O(n*log n) | O(n) | 稳定 | ||
