一.排序的概念

排序，简单来说就是将一组数据按一种特定的比较方式来递增或增减地将数据重新排列成有序的序列。

排序的稳定性：若在一组数据中存在两个或两个以上的相同的数据，在经过一定的排序算法排序后，这些相同的数据的前后顺序不变，那么我们就称这个排序算法是一个稳定的排序，反之，则为不稳定的排序

二.常见的排序算法

1.插入排序

1.1 直接插入排序

直接插入排序的基本思想：将一个个未排序的数据按照指定的比较方法依次插入已经排好序的有序序列中，直到所有的数据都插入到该有序序列中，就得到了一个新的有序序列，这个序列就是我们想要的最终序列。

直接插入排序代码实现（为了使代码更加直观、简单，本文所有代码都基于整数类型数据的比较）：

 public static void insertSort(int[] array){
        //i从1开始，一个元素时即自动为有序
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            //j每次都从已经有序的序列的最后一位开始比较
            int j=i-1;
            for (; j > 0 ; j--) {
                //若已经有序的数据比要插入的数据大，则将该有序数据后移
                if(array[j]>tmp){
                    array[j+1]=array[j];
                    //若要插入的数据比已经有序的数据大，则直接插入在该有序数据的后面
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            //最后都将j+1下标的元素置为要插入元素的值
            //两种情况：1.已经走到该有序序列的最前面 
            2.中途break退出，这里就相当于重复进行了一次赋值
            array[j+1]=tmp;
        }
    }

直接插入排序是一种稳定的排序，事件复杂度为O(N ^ 2)。

1.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先确定一个增量，先将要排序的数据按照相距所选定的增量大小的距离的数据分为一个组，再对各个组中的数据进行直接插入排序，在排序完成后将增量进行缩小再重复以上步骤，直到增量为1（此时即为直接插入排序，不过此时数据相对更加有序，排序效率更高）。

希尔排序代码实现：

   public static void shellSort(int[]array){
        //将初始增量设置成数组长度的一般，后续对增量的调整为每次减半
        int gap = array.length;
        while (gap > 1){
            gap = 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 = j - gap) {
                if(array[j] > tmp){
                    array[j+gap]=array[j];
                }else {
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

希尔排序是一种不稳定的排序，时间复杂度为   n ^ 1.3-n ^ 1.5

2.选择排序

2.1 直接选择排序

直接插入排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完为止 。

代码实现：

 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);
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

我们也可以对这个代码进行一次优化，即在一次遍历时同时寻找最大值与最小值并交换（我们要小心最大值就是第一个元素的情况，防止因交换最小值后第一个元素变为最小值，从而导致最大值的交换错误的情况，所以我们要将最大值的下标改为最小值交换后的下标）

代码实现：

public static void selectSort(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,left,minIndex);
            if(maxIndex == left){
            //防止第一个元素就是最大值发生第一个交换时，
            最大值被交换到下标为minIndex的位置上
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

直接选择排序是一种不稳定的排序，时间复杂度为O（N^2）

2.2 堆排序

堆可以将最大（或最小）的元素放在堆顶，然后我们将堆顶元素和最后一个元素交换位置，再是end--（即将最后一个元素屏蔽在堆之外），再对剩下的元素进行向下调整重新建立一个大根堆接着重复以上步骤，直到end==9（即排序完成）为止

代码实现：

 public static void heapSort(int[] array){
        createHeap(array);
        //定义end指针，指向未排序区间的最后一个元素
        int end=array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array){
        for (int parent = (array.length-1)/2; parent >= 0 ; parent--){
        // 从最后一个非叶子节点开始，向前遍历并下沉调整
            siftDown(array,parent,array.length);
        }
    }
    public static void siftDown(int[] array,int parent,int length){
        // 先定位parent的左孩子
        int child=2*parent+1;
        // 孩子节点在有效范围内才继续调整
        while (child < length){
            // 步骤1：找到左右孩子中值更大的那个（保证是大顶堆）
            if(child+1 < length && array[child]<array[child+1]){
                child++; // 切换到右孩子（右孩子更大）
            }
            // 步骤2：如果孩子值 > 父节点值，交换两者
            if(array[child]>array[parent]){
                swap(array,child,parent);
                // 交换后，原父节点位置变为新的parent，继续向下检查
                parent=child;
                child=2*parent+1;
            }else {
                // 父节点值 >= 孩子值，无需调整，直接退出
                break;
            }
        }

堆排序是一种不稳定的排序，时间复杂度为O（N*logN）

3.交换排序

3.1 冒泡排序

冒泡排序的基本原理：重复遍历待排序的数组，依次比较相邻的两个元素，若顺序错误则交换它们的位置，直到整个数组有序

代码实现：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;
        // 记录本轮是否发生交换，若无则说明数组已排序
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false; // 每轮初始化swapped为false
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true; // 标记本轮有交换
                }
            }
            // 本轮无交换，说明数组已完全有序，直接退出循环
            if (!swapped) {
                break;
            }
        }
    }

冒泡排序是一种稳定的排序，时间复杂度为O（N^2）。

3.2 快速排序

快速排序基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

代码实现：

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;
        }
        //优化：当范围在10以内时，不再进行递归，
        转而用直接插入排序（直接插入排序在数据越有序时排序越快）
        if(end-start+1 <= 10){
            insertSortRange(array,start,end);
            return;
        }
        //优化：三数取中法，将三个数的中间值放入开头作为基准
        int midIndex=getMiddleNum(array,start,end);
        swap(array,start,midIndex);
        //pivot即为左右指针相遇的地方，
        此时pivot左边的值均小于它，右边的值均大于它
        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
 public static int partition(int[] array,int left,int right){
        int tmp = array[left];
        while (left < right){
            while (left<right && array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while (left<right && array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }

挖矿法：先将基准放入tmp中，再从右边找出小于基准的值放入左边，然后再从左边找大于基准的值放入右边，循环至左右指针相遇

其中parttion部分也可以用Hoare法来进行，代码如下：

 public static int partitionHoare(int[] array,int left,int right){
        int tmp = array[left];
        int tmpleft = left;
        while (left < right){
            while (left < right && array[right] >= tmp){
                right--;
            }
            while (left < right && array[left] <= tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpleft);
        return left;
    }

原理解释：每次在基准值左边找到一个大于基准值的值和在基准值的右边找到一个小于基准值的值进行交换，重复进行上述过程直到左右指针相遇

注意：如果是从小到大排序的话要先从右边开始找，这样保证最后左右指针相遇时对应下标的值一定是小于基准值的。如果是从大到小则相反。

快速排序是一种不稳定的排序

4.归并排序

归并排序是基于"分治思想"的经典排序算法，核心思路可以概括为：先把数组 “分” 成多个子数组直到每个子数组只有 1 个元素（天然有序），再把有序的子数组 “合” 并成更大的有序数组，最终合并成完整的有序数组。

代码实现：

   public static void mergeSort(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }
    public static void mergeSortTmp(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        //递归分解数组
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //当代码运行到这里时，array数组已经全部分解完毕（长度为1）
        merge(array,left,mid,right);//合并数组
    }
    //merge方法合并数组
    public static void merge(int[] array,int left,int mid,int right){
        int[] tmp=new int[right-left+1];
        int k=0;//记录合并后数组的长度
        int s1=left;//第一个数组开始的位置
        int s2=mid+1;//第二个数组开始的位置
        while (s1 <= mid && s2 <= right){//防止数组越界
            if(array[s1]<=array[s2]){//从小到大排列数组
                tmp[k++]=array[s1++];
            }else {
                tmp[k++]=array[s2++];
            }
        }
        //走到这里时有s1或s2数组的数据已经存储完
        while (s1<=mid){
            tmp[k++]=array[s1++];
        }
        while (s2<=right){
            tmp[k++]=array[s2++];
        }
        for (int i = 0; i < k; i++) {
            //从第一个数组的下标开始存入原数组中，保证数组有序
            array[i+left]=tmp[i];
        }
    }
   

归并排序是一种不稳定的排序，时间复杂度为O（N*logN）。