1. 稳定性
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
图中排序后a仍然在b前面，此时这个排序就是稳定的。
常见的排序算法有 ：
2 . 插入排序
步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取下一个元素下标定义为i，并且放到变量tmp中，从已排序的元素序列从后往前扫描
- 如果该元素大于tem，则将该元素移到下一位
- 重复步骤3，直到找到已排序元素中小于等于tem的元素，直接break
- tem插入到该元素的后面（array[j+1]=tmp;），如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
- 重复步骤2~5
/**
* 直接插入排序
* 时间复杂度：O（N^2） 逆序的时候
* （最好的情况是O（N）：对于直接插入排序来说，最好的情况就是数组有序的时候）
* 根据这个结论：推导出另一个结论：对于直接插入排序来说，数据越有序，越快
* 直接插入排序所以也用于其他排序的优化！
* 空间复杂度：O（1）
* 稳定性：稳定
* 一个稳定的排序，可以实现一个不稳定的排序
* 但是一个本身就不稳定的排序就不可以变成稳定的排序
* 经常使用在 数据量不多 且 整体数据趋于有序了
* @param array
*/
public 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 {
// 只要j回退的时候，遇到了比tmp小的元素，就结束这次的比较
break;
}
}
//j回退到了 小于0 的地方
array[j+1]=tmp;
}
}
动图演示如下：
3. 希尔排序
步骤：
- 先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
- 当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
/**
* 希尔排序
* 时间复杂度：O(N^1.3-N^1.5)
* 空间复杂度：O(1)
* 稳定性 ： 不稳定的
* 看在比较的过程当中，是否发生了跳跃式的交换，如果发生了跳跃式的交换 那么就是不稳定的排序
* （基本上没有考过）
*
* @param array
* @param 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 {
// 只要j回退的时候，遇到了比tmp小的元素，就结束这次的比较
break;
}
}
//j回退到了 小于0 的地方
array[j+gap]=tmp;
}
}
public static void shellSort(int[] array){
int gap=array.length;
while (gap>1){
shell(array,gap);
gap/=2;
}
shell(array,1);
}
动图演示如下：
4. 选择排序
思路：
每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
/**
* 选择排序
* 时间复杂度：O(N^2)
* 空间复杂度：O(1)
* 稳定性：不稳定的排序
* @param array
*/
public static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
//优化选择排序：每次交换都是当前遍历j时候的最小值
public static void selectSort1(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);
}
}
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;
}
}
}
}
动图演示如下 ：
5. 堆排序
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆。
堆排序可以参考之前写的一篇博文：堆详解
也可以借鉴大佬的一篇关于堆排的文章，博主看了受益匪浅：堆排序
/**
* 堆排序 排升序要建大堆；排降序要建小堆。
* 时间复杂度 ：O(N*logN)
* 空间复杂度 : O(1)
* 稳定性：不稳定的
*
* @param array
*/
public static void heapSort(int[] array){
//1.建堆 O(N)
creatHeap(array);
int end=array.length-1;
//2.交换然后向下调整为大根堆 O(N*logN)
while (end>0){
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
public static void creatHeap(int[] array){
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
shiftDown(array,parent,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++; //保证child下标，就是左右孩子最大值下标
}
if (array[child]>array[parent]){
swap(array,child,parent);
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
算法图解 ：
6 冒泡排序
原理：
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
思路：
排序一趟可以让最大的数字沉底
排序len-1趟，一趟排序len-1-i次
详细实现看代码
/**
* 冒泡排序（未优化）
* 时间复杂度：O（N^2）
* 空间复杂度：O(1)
* 稳定性：稳定的排序
* @param array
*/
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1; j++) {
if (array[j]>array[j+1]){
swap(array,j,j+1);
}
}
}
}
/**
* 冒泡排序（优化）
* 时间复杂度：O（N^2） （最坏的情况）
* （最好的情况 ： 有序） O（N）
* 空间复杂度：O(1)
* 稳定性：稳定的排序
* @param array
*/
public static void bubbleSort2(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){ //没交换的话说明flg没被制成TRUE，则说明已经有序，可以跳出循环了
break;
}
}
}
动图演示如下 ：
