排序分类.png

性能比较

对比图.png
O(nlogn)效率优于O(n^2)
简单算法：冒泡、选择、直接插入
改进算法：希尔、堆、快速、归并
不稳定的排序----快些选队（快速排序、希尔排序、选择排序、堆排序）

---

冒泡排序

    public static void BubbleSort(int[] num) {
        int size  =num.length;
        boolean flag = false;
        for(int i = 0; i< size-1; i++) {
            for(int j = 0; j< size-1-i; j++) {
                if (num[j] > num[j+1]) {
                    int temp = num[j];
                    num[j] = num[j+1];
                    num[j+1] = temp;
                    flag = true;
                }
            }
            if (flag == false) {
                break;          //遍历一遍数组后发现无元素交换时说明此时数组已有序
            }
        }
    }

---

快速排序（冒泡排序的升级，同属于交换排序类）

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
适用于数据量较大的情况

原始算法

    public static void quickSort(int[] num,int low, int high) {
        if (low < high) {
            int middle = getMiddle(num, low, high);     //将数组一分为二
            quickSort(num, low, middle-1);      //对低字段进行递归排序
            quickSort(num, middle+1, high);     //对高字段进行递归排序
        }
    }
    
    public static int getMiddle(int[] num, int low, int high) {
        int temp = num[low];        //优化前：选取第一个字段作为基准值
        while(low < high) {
            while(low < high && num[high] > temp) {     //从后往前找到一个比基准值小的数
                high--;
            }
            swap(num, low, high);
            while(low <high && num[low] < temp) {       //从前往后找一个比基准值大的数
                low++;
            }
            swap(num, low, high);
        }
        return low;     //返回中轴所在位置
    }
    
    
    public static void swap(int[] num, int low, int high) {
        int temp = num[low];
        num[low] = num[high];
        num[high] = temp;
    }

优化算法

采用三数取中方式选取基准值
采用替换方式而不是交换方式进行操作

    public static int getMiddle(int[] num, int low, int high) {
        //快速排序优化：三数取中方式选取基准值
        int m = low + (high - low) /2;      //获取数组中间值下标
        if (num[low] > num[high]) {
            swap(num, low, high);       //保证左端小于右端
        }
        if (num[m] > num[high]) {
            swap(num, m, high);     //保证中间小于右端
        }
        if (num[m] > num[low]) {
            swap(num, m, low);          //保证左端小于中间
        }
        int temp = num[low];            //优化后：选取数组第一个数，中间的数以及最后一个数中的中间数最为基准值
        while(low < high) {             //循环结束后low和high指向同一元素，该元素的位置就是基准元素的位置
            while(low < high && num[high] > temp) {     //从后往前找到一个比基准值小的数
                high--;
            }
            num[low] = num[high];           //采用替换而不是交换方式进行操作
            while(low <high && num[low] < temp) {       //从前往后找一个比基准值大的数
                low++;
            }
            num[high] = num[low];
        }
        num[low] = temp;        //将保存的基准值替换到相应位置
        return low;     //返回中轴所在位置
    }

---

选择排序

思想：在待排序的数中，选出一个最小的数与第一个位置的数交换，然后在剩下的数中找到第二小的数与第二个位置的数交换，如此反复。

    public static void selectSort(int[] num) {
        for(int i = 0; i < num.length; i++) {
            int min = i;
            for(int j = i+1; j < num.length; j++){
                if (num[j] < num[min]) {
                    min = j;
                }
            }
            if (i != min) {
                swap(num,i,min);                
            }
        }
    }

优化思路：每次遍历都找出一个最大值以及最小值

---

堆排序（选择排序的升级）

思路：构造一个最大堆，将根结点的值与最后一个叶节点交换，然后排除该叶节点后再次构造最大堆。

        for(int i=0; i<num.length-1; i++) {
            //循环建立最大堆
            buildMaxHeap(num, num.length-1-i);
            //交换根节点和最大堆最后一个叶节点
            swap(num, 0, num.length-1-i);
        }

    public static void buildMaxHeap(int[] num, int lastIndex) {
        //从lastIndex节点的父节点开始循环
        for(int i = (lastIndex-1) /2; i>=0; i--) {
            //保存正在判断的节点
            int temp = i;
            //当前节点的子节点存在时
            while( temp*2+1 <= lastIndex) {
                //当前节点的左节点
                int biggerIndex = 2*temp+1;
                if (biggerIndex < lastIndex) {
                    //biggerIndex指向当前节点左右孩子节点中较大值的索引
                    if (num[biggerIndex] < num[biggerIndex+1]) {
                        biggerIndex++;
                    }
                }
                //当前节点小于子女节点中较大值时
                if (num[temp] < num[biggerIndex]) {
                    //交换位置
                    swap(num,temp,biggerIndex);
                    //开启while的下一次循环，保证temp节点的值大于左右孩子节点的值
                    temp = biggerIndex;
                }else {
                    break;
                }
            }
        }
    }

---

直接插入排序

思路：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数加1的有序表。

    public static void insertSort(int[] num) {
        int i,j;
        for( i = 0; i< num.length; i++) {
            int temp = num[i];
            for( j = i; j > 0 && temp < num[j-1]; j-- ) {
                //temp小于前面的值，则前面的数右移
                num[j] = num[j-1];
            }
            num[j] = temp;
        }
    }

---

希尔排序（直接插入排序升级版）

思路：将待排序的数组按一定步长进行分组，并在每个分组中应用直接插入排序算法，然后缩短步长再次进行分组，直到步长为0为止。

    public static void shellSort(int[] num) {
        //设置步长
        int step = num.length/2;
        while(step >= 1) {
            for(int i = step; i< num.length; i+=step) {
                int temp = num[i];
                int j;
                //直接插入排序算法
                for(j=i; j>0 && num[j-step] > temp; j-=step) {
                    num[j] = num[j-step];
                }
                num[j]  = temp;
            }
            //缩小步长直到step为0
            step = step/2;
        }
    }

---

归并排序

思路：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2(向上取整)个长度为2或1的有序序列，再两两归并......,如此反复，直至得到一个长度为n的有序序列为止，这种排序称为2路归并排序。

    /**
     * @param num 待排序数组
     * @param n 排序元素个数
     */
    public static void mergerSort(int[] num, int n) {
        sort(num, 0, n-1);
    }
    
    public static void sort(int[] num, int left, int right) {
        if (left < right) {
            int middle = (right + left)/2;
            sort(num, left, middle);
            sort(num, middle+1, right);
            merge(num, left, middle, right);
        }
    }
    
    public static void merge(int[] num, int left, int mid, int right) {
        //计算数组大小
        int n = right-left+1;
        //创建临时数组保存数据
        int[] tempArr = new int[n];
        //临时数组下标
        int t = 0;
        int r = mid+1;
        int l = left;
        while(l <= mid && r <= right) {
            if (num[l] < num[r]) {
                tempArr[t++] = num[l++];
            }else {
                tempArr[t++] = num[r++];
            }
        }
        //剩余元素加入临时数组
        while(l <= mid) {
            tempArr[t++] = num[l++];
        }
        while(r <= right) {
            tempArr[t++] = num[r++];
        }
        
        //将临时数组的值复制到原数组中
        for(int i = 0; i < t ; i++) {
            num[left+i] = tempArr[i];
        }
    }