常见排序算法介绍

冒泡排序

原理：比较相邻两个数，如果前面的数大于（小于）后面的数，则二者交换位置，直到尽头，重复（N-1）次，得到一个有序数列
算法复杂度：O(n^2)
排序过程：

• 源数据： 7, 8, 3, 26, 99, 91
• 第1轮： 7, 3, 8, 26, 91, 99
• 第2轮： 3, 7, 8, 26, 91, 99
• 第3轮： 3, 7, 8, 26, 91, 99
• 第4轮： 3, 7, 8, 26, 91, 99
• 第5轮： 3, 7, 8, 26, 91, 99

public class BubbleSort extends Sort {
    //冒泡排序
    @Override
    public void sort(int[] array) {
        int length = array.length;
        //recordValues(array,"数据：");
        for (int i = 0; i < length - 1; i++) {
            for (int j = 1; j < length - i; j++) {
                //符合条件，交换位置
                if (array[j - 1] > array[j]) {
                    int tem = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tem;
                }

            }
            //recordValues(array,"第"+(i+1)+"轮：");
        }
    }
}

插入排序

原理：将一个数插入到一个有序数列，得到一个新的有序数列
算法复杂度：O(n^2)
排序过程：

• 源数据： 7, 8, 3, 26, 99, 91
• 第1轮： 7, 8, 3, 26, 99, 91
• 第2轮： 3, 7, 8, 26, 99, 91
• 第3轮： 3, 7, 8, 26, 99, 91
• 第4轮： 3, 7, 8, 26, 99, 91
• 第5轮： 3, 7, 8, 26, 91, 99

public class InsertionSort extends Sort {
    @Override
    public void sort(int[] array) {
       // recordValues(array,"数据：");
        int length =array.length;
        for(int i=1;i<length;i++){
            int tem =array[i];
            int j=i-1;
            for(;j>=0;j--){
                 if(tem<array[j]){
                     array[j+1] =array[j];
                 }else {
                   break;
                 }
            }
            array[j+1] =tem;
            //recordValues(array,"第"+(i)+"轮：");
        }
    }
}

选择排序

原理：从无序数组中选出一个最大值（最小值），放进有序数组
算法复杂度：O(n^2)
排序过程：

• 第1轮： 3, 8, 7, 26, 99, 91
• 第2轮： 3, 7, 8, 26, 99, 91
• 第3轮： 3, 7, 8, 26, 99, 91
• 第4轮： 3, 7, 8, 26, 99, 91
• 第5轮： 3, 7, 8, 26, 91, 99
• 第6轮： 3, 7, 8, 26, 91, 99

/**
 * 选择排序
 */
public class SelectionSort extends Sort {
    public void sort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            //从剩余数组里选择最小的
            for (int j = 1 + i; j < length; j++) {
                if (array[j] < array[i]) {
                    int tem = array[i];
                    array[i] = array[j];
                    array[j] = tem;
                }

            }
            //recordValues(array,"第"+(i+1)+"轮：");
        }

    }
}
}

快排

原理：找关键值，然后将数列分成两个数列，一个大于等于关键值的，一个小于等于关键值的，然后再对这两个数列进行递归
算法复杂度：O(nlogn)
算法步骤：

1. 找基准数，并将基准放到排序后的位置
2. 递归基准两侧的数组

排序过程：

• 源数据： 7 8 3 26 99 91
• 基准7: 3 7 8 26 99 91
• 基准8: 3 7 8 26 99 91
• 基准26: 3 7 8 26 99 91
• 基准99: 3 7 8 26 91 99

public class QuickSort extends Sort {
    //寻找基准
    public int findPartition(int[] array, int left, int right) {
        int pivot = array[left];
        while (left < right) {
            while (pivot <= array[right] && left < right) {
                right--;
            }
            array[left] = array[right];
            array[right] = pivot;
            while (pivot > array[left] && left < right) {
                left++;

            }
            array[right] = array[left];
            array[left] = pivot;
        }

        array[left] = pivot;
        //recordValues(array,"基准"+pivot+":");
        return left;

    }

    //快排
    private void quickSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = findPartition(array, left, right);
            quickSort(array, left, mid - 1);
            quickSort(array, mid + 1, right);

        }

    }
    @Override
    public void sort(int[] array) {
       // recordValues(array,"数据：");
        quickSort(array, 0, array.length - 1);
    }
}

归并排序

原理：采用的是分治策略，将大问题分解成小问题，递归求解
算法复杂度：O(nlogn)
算法步骤：

1. 递归将数组分成两个数组，直至无法再分
2. 将分裂的后的数组，进行合并排序

排序过程：

• 源数据 7, 8, 3, 26, 99, 91
• 2为中间点 7, 8, 3, 26, 99, 91
• 1为中间点 7, 8, 3, 26, 99, 91
• 0为中间点 7, 8, 3, 26, 99, 91
• 0数据合并 7, 8, 3, 26, 99, 91
• 1数据合并 3, 7, 8, 26, 99, 91
• 4为中间点 3, 7, 8, 26, 99, 91
• 3为中间点 3, 7, 8, 26, 99, 91
• 3数据合并 3, 7, 8, 26, 99, 91
• 4数据合并 3, 7, 8, 26, 91, 99
• 2数据合并 3, 7, 8, 26, 91, 99

将排序过程简化：

• 源数据 7 8 3 26 99 91
• 以第三个数将数组分为两个数组
• 7,8,3 -- 26,99,91
• 继续均分数组
• 7,8 -- 3 -- 26,99 -- 91
• 继续均分数组
• 7 -- 8 -- 3 -- 26 -- 99 -- 91
• 数组合并
• 7,8 -- 3 -- 26,99 -- 91
• 继续合并
• 3,7,8 -- 26,91,99
• 继续合并
• 3,7,8,26,91,99

public class MergSort extends Sort {
    //数组合并
    private void merg(int[] array, int left, int mid, int right) {
        int[] arrayTem = new int[right - left + 1];
        int leftIndex = left;
        int rightIndex = mid + 1;
        int index = 0;
        while (leftIndex <= mid && rightIndex <= right) {
            if (array[leftIndex] < array[rightIndex]) {
                arrayTem[index] = array[leftIndex];
                leftIndex++;
            } else {
                arrayTem[index] = array[rightIndex];
                rightIndex++;

            }
            index++;
        }
        while (leftIndex <= mid) {
            arrayTem[index] = array[leftIndex];
            leftIndex++;
            index++;
        }
        while (rightIndex <= right) {
            arrayTem[index] = array[rightIndex];
            rightIndex++;
            index++;


        }
        index = 0;
        for (; left <= right; left++) {
            array[left] = arrayTem[index];
            index++;

        }

    }

    //排序
    private void mergSort(int[] array, int left, int right) {
        if (left != right) {
            int mid = (left + right) / 2;
            recordValues(array,""+mid+"为中间点");
            mergSort(array, left, mid);
            mergSort(array, mid + 1, right);

            merg(array, left, mid, right);
           // recordValues(array,""+mid+"数据合并");


        }


    }

    @Override
    public void sort(int[] array) {
        mergSort(array, 0, array.length - 1);

    }
}

堆排序

原理：和选择排序类似，只是将选择大小这一步用堆来实现
堆的性质

• 是一个完全二叉树

• 每个节点（非叶子节点）的值，都大于等于（小于等于）其孩子节点的值

  大顶堆：array[i] >= max(array[2i+1],array[2(i+1)])
  小顶堆：array[i] <= min(array[2i+1],array[2(i+1)])
  算法复杂度：O(nlogn)
  算法步骤：

1. 构建堆
2. 从堆顶选出最大（小）值（要注意堆的调整）

avatar

public class HeapSort extends Sort {
    @Override
    public void sort(int[] array) {
        buildMaxHeap(array);
        heapSort(array);

    }

    //堆排序
    private void heapSort(int[] array) {
        int len = array.length;
        for (int i = array.length - 1; i >= 0; i--) {
            int tem = array[0];
            array[0] = array[i];
            array[i] = tem;
            adJustMaxHeap(array, 0, --len);
        }

    }

    //最大堆调整
    void adJustMaxHeap(int[] array, int index, int len) {
        int largest = index;
        int left = leftChildIndex(index);
        int right = rightChildIndex(index);
        if (left >= len) {
            return;
        }
        if (array[left] > array[index]) {
            largest = left;
        }
        if (right < len && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != index) {
            int tem = array[largest];
            array[largest] = array[index];
            array[index] = tem;
            adJustMaxHeap(array, largest, len);
        }

    }

    //构建最大堆
    private void buildMaxHeap(int[] array) {

        int len = array.length;
        for (int i = len / 2; i >= 0; i--) {
           adJustMaxHeap(array,i,len);
        }

    }

    //左孩子
    private int leftChildIndex(int parent) {
        return parent * 2 + 1;
    }

    //右孩子
    private int rightChildIndex(int parent) {
        return (parent + 1) * 2;
    }
}

希尔排序(缩小增量排序)

原理：是插入排序的一种优化，先将整个序列分割成若干子序列分别进行直接插入排序，待整个序列中数基本有序后，再进行一次插入排序

• 源数据： 7 8 3 26 99 91
• 步长3: 7 8 3 26 99 91
• 步长1: 3 7 8 26 91 99

public class ShellSort extends Sort {
    @Override
    public void sort(int[] array) {
        recordValues(array,"源数据：");
        int len = array.length;
        for (int gap = len / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                if (array[i] < array[i - gap]) {
                    int k = i;
                    int tem = array[i];
                    while (k - gap >= 0 && tem < array[k - gap]) {
                        array[k] = array[k - gap];
                        k = k - gap;
                    }
                    array[k] = tem;
                }
            }
          //recordValues(array,"步长"+gap+":");
        }

    }
}

希尔排序的复杂度很大程度上由选择的增量序列决定，现今没有最优的增量序列

计数排序

原理：不是通过数据比较来进行排序，经过统计数据出现次数，然后根据统计个数排出序列
算法复杂度：O(n+k)
算法步骤：

1. 统计每个数据出现的次数
2. 将数据一次输出

public class CoutNumSort extends Sort {
    public static int SIZE =100;
    @Override
    public void sort(int[] array) {
        int[] countNum = new int[SIZE+5];
        for(int i=0;i<array.length;i++){
            countNum[array[i]]++;
        }
        int index =0;
        for(int i =0;i<SIZE;i++){
            for(int j=0;j<countNum[i];j++){
               array[index]=i;
               index++;
            }
        }
      // recordValues(array,"排序结果");

    }

}

空间优化：选出最大值和最小值，将统计数组大小开为 max-min+1（这种优化和数据关系很大）

public class CoutNumSort extends Sort {
    public static int SIZE =100;
    @Override
    public void sort(int[] array) {
        int min,max;
        min =max=array[0];
        for(int i=0;i<array.length;i++){
            if(min>array[i]){
                min =array[i];
            }
            if(max<array[i]){
                max=array[i];
            }
        }
        int[] countNum = new int[max-min+1];

        for(int i=0;i<array.length;i++){
            countNum[array[i]-min]++;
        }
        int index =0;
        SIZE =max-min+1;
        for(int i =0;i<SIZE;i++){
            for(int j=0;j<countNum[i];j++){
               array[index]=i+min;
               index++;
            }
        }
       //recordValues(array,"排序结果");

    }

}

如何保证相同数据按照本来数据排列

public class CoutNumSort extends Sort {
    public static int SIZE =100;
    @Override
    public void sort(int[] array) {
        //这一部分作空间的优化
        int min,max;
        min =max=array[0];
        for(int i=0;i<array.length;i++){
            if(min>array[i]){
                min =array[i];
            }
            if(max<array[i]){
                max=array[i];
            }
        }
        int[] countNum = new int[max-min+1];
        //数据统计
        for(int i=0;i<array.length;i++){
            countNum[array[i]-min]++;
        }
       //确定位置，保持原有顺序
        for(int i=1;i<countNum.length;i++){
            countNum[i]+=countNum[i-1];
        }
        int[] result = new int[array.length];
        for(int i =array.length-1;i>=0;i--){
            result[countNum[array[i]-min]-1] =array[i];
            countNum[array[i]-min]--;
        }
       // recordValues(result,"排序结果：");
    }

}

计数排序的局限性

计数排序主要被数据最大值和最小值的差值给限制住了，当差值较大时，就意味着申请更多的空间，造成大量的浪费，
但在统计数值在一个固定范围的数据，比如身高，分数，体重之类的，效率还是比较高的。

基数排序

原理：从低位到高位过比较每个数据数位的值进行的排序，利用了计数排序
算法复杂度：O(n*m)

• 数据： 7 8 3 26 99 91
• 第1轮： 91 3 26 7 8 99
• 第2轮： 3 7 8 26 91 99

public class RadixSort extends Sort {
    @Override
    public void sort(int[] array) {
        recordValues(array,"数据：");
        int arrayLength = array.length;
        int[] temArray = new int[arrayLength];
        int[] bucks = new int[10];

        int[] weights = new int[8];
        weights[0] = 1;
        int numLength = maxLength(array);
        initWeight(weights, numLength);

        for (int i = 0; i < numLength; i++) {
            //置空
            for (int j = 0; j < bucks.length; j++) {
                bucks[j] = 0;
            }
            for (int j = 0; j < array.length; j++) {
                int digit = getDigit(array[j], weights[i]);
                bucks[digit]++;
            }
            for (int j = 1; j < bucks.length; j++) {
                bucks[j] += bucks[j - 1];
            }

            for (int j = arrayLength - 1; j >= 0; j--) {
                int digit = getDigit(array[j], weights[i]);
                temArray[bucks[digit] - 1] = array[j];
                bucks[digit]--;
            }
            for (int j = 0; j < array.length; j++) {
                array[j] = temArray[j];
            }
            recordValues(array,"第"+(i+1)+"轮：");
        }


    }

    //权重初始化
    private void initWeight(int[] weights, int len) {
        for (int i = 1; i <= len; i++) {
            weights[i] = weights[i - 1] * 10;
        }
    }

    //最大长度
    private int maxLength(int[] array) {
        int maxNum = array[0];
        for (int i = 0; i < array.length; i++) {
            if (maxNum < array[i]) {
                maxNum = array[i];
            }
        }

        return Integer.toHexString(maxNum).length();
    }

    //获取权重上数字
    private int getDigit(int num, int weight) {
        return (num / weight) % 10;

    }
}

总结

排序算法	时间复杂度	最差时间	空间复杂度	稳定性
冒泡排序	O(n2)	O(n2)	1	稳定
选择排序	O(n2)	O(n2）	1	稳定
插入排序	O(n2)	O(n2)	1	稳定
快排	O(nlogn)	O(n2)	logn	不稳定
归并排序	O(nlogn)	O(nlogn)	n	稳定
堆排序	O(nlogn)	O(nlogn)	1	不稳定
计数排序	O(n+k)	O(n+k)	n+k	稳定
基数排序	O(n*d)	O(n*d)	n+k	稳定

• 排序算法当n值较小的时候，O(n2)和O(nlogn)效率差不多，O(n2)甚至优于O(nlogn)。
• 当n值较大时O(n2)算法将不能选择，通常情况下快排会优于其他n(logn)算法。