常见排序算法介绍

2021-06-17 本文已影响0人 QiShare

冒泡排序

原理：比较相邻两个数，如果前面的数大于（小于）后面的数，则二者交换位置，直到尽头，重复（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)
算法步骤：

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

排序过程：

源数据： 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)
算法步骤：

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

排序过程：

源数据 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)
算法步骤：

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

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)
算法步骤：

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

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)算法。