关于排序的稳定性：
1.如果在排序的过程中，没有发生跳跃式的交换。那么是稳定的排序
2.一个稳定的排序，是可以被实现为不稳定的排序的，但是一个不稳定的排序是不可能变为稳定的排序的

一、直接插入排序

1.1 原理

将整个排序的区间，分为有序区间（刚开始一般只有0号下标元素，因为一个元素本身就是有序的）和无序区间，每次选择无序区间的第一个元素，插入到有序区间的合适位置，直到整个序列都变有序。

1.2 实现

public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {//循环无序元素
            int tmp = array[i];//临时变量来保存待插入元素
            int j = 0;
            for (j = i-1; j >= 0 ; j--) {//循环有序元素,每一躺j始终在i的前面一个位置
                if (array[j] > tmp){
                    array[j + 1] = array[j];
                }else {
                    break;//前面的已经有序了
                }
            }
            array[j+1] = tmp;//插入数据
        }
    }

1.3 性能分析

稳定性：稳定的
时间复杂度：最好情况O(n),最坏情况O(n^2),所以越有序的序列用直插排序越快。
空间复杂度： O(1)只用了一个数组

二、选择排序

2.1 原理

选择序列中最小的元素与当前元素进行比较并进行交换

2.2 实现

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[j];
                    array[j] = array[i];
                    array[i] = tmp;
                }
            }
        }
    }

2.3 性能分析

①稳定性：不稳定的
②时间复杂度：O(n^2)
③空间复杂度： O(1)

三、堆排序

3.1 原理

建立一个堆(升序大堆，降序小堆)
将堆最后一个元素与堆顶的元素交换位置，再从堆顶向下调整，第二次将堆倒数第二的元素与堆顶元素交换位置，再向下调整…直到没有元素为止，排序就完成了

3.2 实现

//1.向下调整
public static  void  adjustDown(int[] array,int index,int size){
        int left = index*2+1;
        while(left<size){
        	int max = left;
        	int right = index*2+2;
        	//找左右子节点最大值
        	if(right<size){
        		if(array[right]>array[left]){
        			max = right;
        		}
        	}
        	//如果index是最大的那说明调整结束
        	if(array[index]>=array[max]){
        		break;
        	}
        	//交换 index 和 max下标的值
        	swap(array,index,max);
        	
        	//开启下一轮循环
        	index = max;
        	left= index*2+1;
        }
    }
    //2.使用向下调整将待排序数组建立一个堆
    //从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆
    public static void createHeap(int[] array){
        for (int i = (array.length -2)/2; i >= 0 ; i--) {
            	//根据child反推parent
            adjustDown(array,i,array.length);
        }
    }
    //3.排序
    public static void heapSort(int[] array){
        //建堆的时间复杂度是 n*log2n
        //堆的一次调整的时间复杂度是log2n
        creatHeap(array);
        int end = array.length - 1;
        while (end > 0){
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            adjustDown(array,0,end);//长度一定是end因为end之后的已经调整好了
            end--;//必须在adjustDown下边
        }
    }

3.3 性能分析

**①稳定性：**不稳定
②时间复杂度： O(nlog2n)
建立大根堆的时间复杂度是O(nlog2n)
一次调整的时间复杂度为O(log2n)
③空间复杂度： O(1)

四、冒泡排序

4.1 原理

两个循环，一个躺数，一个比较次数，紧挨着的两个数字进行比较，并进行交换，将最大的数字“沉”下去，较小的数字“冒”上来，图解如下：

可见一共进行了数组长度-1躺，第 i 趟进行了数组长度 -1 - i 次比较

4.2 实现

public static void bubbleSort(int[] array){
        boolean flg = false;
        for (int i = 0; i < array.length - 1; i++) {//躺数
            for (int j = 0; j < array.length - 1 - i; j++) {//比较次数
                if (array[j] > array[j+1]){//交换数据
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;//对排序的优化，当该躺已经有序时，标志位为false就不用进行比较
                }
            }
            if (!flg){
                break;
            }
        }
    }

4.3 性能分析

①稳定性：稳定的
②时间复杂度：O(n^2)
③空间复杂度： O(1)

五、快速排序

5.1 原理

1.从待排序区间选择一个数，作为基准值(pivot)，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边
2.采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间长度等于1，代表已经有序，或者小区间的长度等于0，代表没有数据了。
下图为一趟快速排序的操作过程：

到此，数据6有序了，然后开始递归，有新的low和high进入下一个分段，最终每个值都有序了。

5.2 实现

1、递归实现

public static void quickSort(int[] array){
       quick(array,0,array.length-1);
    }
//快排主函数
public static void quick(int[] array,int low,int high){//O(log2n)
        //终止条件
       if(low < high){
           //1.写函数将待排序序列分为两部分
           int pivot = partion(array,low,high);
           //2.开始递归（左或右都可以）
           quick(array,low,pivot - 1);
           quick(array,pivot + 1,high);
        }
    }


//寻找基准
public static int partion(int[] array,int start,int end){//O(n)
        int tmp = array[start];
        while (start < end){
        	//1.在后面找到比tmp小的
			while(start<end && array[end]>=tmp){
				end--;
			}
			if(start >= end){
				break;
			}else{
				array[start] = array[end];
			}	
			//2.在前面找到比tmp大的
			while(start<end && array[start]<=tmp){
				start++;
			}
			if(start >= end){
				break;
			}else{	
				array[end] = array[start];
			}		
        }
        array[start]  = tmp;
        return start;
    }

2、非递归实现

public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        stack.push(array.length - 1);
        stack.push(0);

        while (!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();
            if(left >= right){
                continue;
            }

            int pivot = partion(array,left,right);//还是要调用partion
            stack.push(right);
            stack.push(pivot + 1);

            stack.push(pivot -1);
            stack.push(left);
        }
    }

5.3 性能分析

①稳定性：不稳定
②时间复杂度：O(nlog2n)
注：看着和堆排一样快,但是比堆排序快一些因为前面系数小
③空间复杂度： O(log2n)
注： 就是二叉树的高度

六、归并排序

6.1 原理

给定一组待排序列， 首先，将其划分为一个一个有序的，然后进行二路递归。整体来说，递：分成单个有序。归：合并为整体有序序列。也是分治的思想

6.2 实现

1、递归实现

//入口函数
  public static void mergeSort1(int[] array){
       mergeSortInternal(array,0,array.length - 1);
    }
    
//分治函数
  public static void mergeSortInternal(int[] array,int low,int high){
        if(low >= high){ //low一直在high的左边
              		   //当low小于high的时候递归，其他情况停止
            return;
        }
        int mid = (low + high) / 2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        //进行合并
        merge1(array,low,mid,high);
    }

//合并函数
public static  void merge1(int[] array,int low,int mid,int high){
        int s1 = low;//第一个归并段的开始
        int s2 = mid + 1;//第二个归并段的开始
      /*思路：每次比较s1和s2下标的元素大小，把比较小拿到新的数组里，小的归并段下标(s1或s2)
      往后走一个元素，重复该过程。
      * 直到一个归并段走完了，把另一个归并段的剩余数据放到新数组后面。
      * 再把新数组的数据方放回原数组。
      * */
        int[] tmpArr = new int[high-low+1];//工具数组的长度
        int i = 0;//tmpArr的数组下标
        //当两个归并段都有数据的时候
        while (s1 <= mid && s2 <= high){//说明段里都有数据才可以比较
            //如果是小于，就不稳定了
            if (array[s1] <= array[s2]){
                tmpArr[i++] = array[s1++];
            }else{
                tmpArr[i++] = array[s2++];
            }
        }
        //退出循环的两种情况
        while (s1 <= mid ){//有可能第一个归并段中还余了数据
            //把第一个段中的所有数据拷贝到工具数组中
            tmpArr[i++] = array[s1++];
        }
        while (s2 <= high){//第二个归并段中余了数据
            tmpArr[i++] =   array[s2++];
        }
        //tmpArr存放的是最终有序的数据
        //这一步将tmpArr的有效有序数据放回到array里面
        for (int j = 0; j < tmpArr.length; j++) {
            array[low + j] = tmpArr[j];//要看上一步递归时，传进来的下标low
        }
    }
    

2、非递归实现

  //思路:先划分单个有序，然后两个有序，然后四个有序....最后整体有序（个数大于等于长度）
    public static void mergeSort2(int[] array){
        for (int i = 1; i < array.length; i *= 2) {
            merge(array,i);
        }
    }

     public static void merge(int[] array,int gap){//他的工作就是谁小拉谁下来
        int[] tmpArr = new int[array.length];
        int k = 0; //下标

         int s1 = 0;
         int e1 = s1 + gap - 1;
         int s2 = e1 + 1;
         int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
         //如果超了那么等于最后一个下标

         //此时两个归并段是都有数据的
         while (s2 < array.length){
             //且在比较的时候两个归并段是有数据的
             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++];
             }
             s1 = e2 + 1;
             e1 = s1 + gap -1;
             s2 = e1 + 1;
             e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
         }
         //判断是不是还有一个归并段，且这个归并段一定是s1的那个段，直接小于e1可能会越界
         while (s1 <= array.length -1){
             tmpArr[k++] = array[s1++];
         }

         //拷贝到array
         for (int i = 0; i < tmpArr.length; i++) {
             array[i] = tmpArr[i];
         }
    }

6.3 性能分析

①稳定性：稳定的
②时间复杂度：n*log2n
③空间复杂度： O(n)