排序算法总结

排序算法总结依次选择一个待排序的数据,插入到前边已排好序的序列中。 时间复杂度为$O(N^2)$,空间复杂度为$O(1)$。算法是稳定的,比较次数和交换次数都与初始序列有关。 直接插入排序每次往前插入时,是按顺序依次往前找,可在这里进行优化,往前找合适的插入位置时采用二分查找的方式,即折半…

image.png

排序算法

文章内公式可能不能解析,可以到我的技术博客的网站进行查阅

  • 交流或更多内容请关注我的公众号:nezha_blog
  • 我的技术博客:nezha.github.io
微信公众号

冒泡排序

原理

俩俩比较相邻记录的排序码,若发生逆序,则交换;有俩种方式进行冒泡,一种是先把小的冒泡到前边去,另一种是把大的元素冒泡到后边。

性能

时间复杂度为$O(N^2)$,空间复杂度为$O(1)$。排序是稳定的,排序比较次数与初始序列无关,但交换次数与初始序列有关。

优化

若初始序列就是排序好的,对于冒泡排序仍然还要比较$O(N^2)$次,但无交换次数。可根据这个进行优化,设置一个flag,当在一趟序列中没有发生交换,则该序列已排序好,但优化后排序的时间复杂度没有发生量级的改变。

###代码

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = true;
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
                flag = false;
            }
        }
        if (flag) return;
    }
}

插入排序

原理

依次选择一个待排序的数据,插入到前边已排好序的序列中。

排序算法总结

性能

时间复杂度为$O(N^2)$,空间复杂度为$O(1)$。算法是稳定的,比较次数和交换次数都与初始序列有关。

优化

直接插入排序每次往前插入时,是按顺序依次往前找,可在这里进行优化,往前找合适的插入位置时采用二分查找的方式,即折半插入。

折半插入排序相对直接插入排序而言:平均性能更快,时间复杂度降至$O(NlogN)$,排序是稳定的,但排序的比较次数与初始序列无关,总是需要$foor(log(i))+1$次排序比较。

代码

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++){
        out:
        for (int j=i;j>0;j--){
            if (arr[j] < arr[j-1]){
                int tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }else break out;
        }
    }
}
public static void insertBinarySort(int[] arr){
    for (int i = 1; i < arr.length; i++){
        if (arr[i] < arr[i-1]){
            int temp = arr[i];
            int low = 0, high = i - 1, mid;
            while (low <= high){
                mid = (low + high) / 2;
                if (temp < arr[mid]){
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }
            for (int j = i; j >low; j--){
                arr[j] = arr[j - 1];
            }
            arr[low] = temp;
        }
    }
}

希尔排序

原理

插入排序的改进版,是基于插入排序的以下俩点性质而提出的改进方法:

  • 插入排序对几乎已排好序的数据操作时,效率很高,可以达到线性排序的效率。
  • 但插入排序在每次往前插入时只能将数据移动一位,效率比较低。

所以希尔排序的思想是:

  • 先是取一个合适的gap<n作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放入同一个子序列,再对每个子序列进行直接插入排序;
  • 缩小间隔gap,例如去gap=ceil(gap/2),重复上述子序列划分和排序
  • 直到,最后gap=1时,将所有元素放在同一个序列中进行插入排序为止。

###性能

开始时,gap取值较大,子序列中的元素较少,排序速度快,克服了直接插入排序的缺点;其次,gap值逐渐变小后,虽然子序列的元素逐渐变多,但大多元素已基本有序,所以继承了直接插入排序的优点,能以近线性的速度排好序。

###代码

public static void shellSort(int[] arr) {
    int gap = Math.round(arr.length / 2);
    while (gap > 0) {
        for (int i = 0;i<gap;i++){
            for (int j = i + gap;j<arr.length;j+=gap){
                if (arr[j] > arr[j-gap]){
                    int temp = arr[j];
                    int k = j - gap;
                    while (k >= 0 && arr[k] > temp)
                    {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}
public static void shellSort2(int[] arr){
    for (int gap = arr.length / 2; gap > 0; gap /= 2){
        for (int i = 0; i < arr.length; i = i + gap){
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && temp < arr[j-gap]; j -= gap){
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

选择排序

原理

每次从未排序的序列中找到最小值,记录并最后存放到已排序序列的末尾

性能

时间复杂度为$O(N^2)$,空间复杂度为$O(1)$,排序是不稳定的(把最小值交换到已排序的末尾导致的),每次都能确定一个元素所在的最终位置,比较次数与初始序列无关。

代码

public static void selectSort(int[] arr){
    int len = arr.length;
    //每次从后边选择一个最小值
    for (int i = 0; i < len-1; i++){ //只需选择n-1次
        int min = i;
        for (int j = i+1; j < len; j++){
            if (arr[min]>arr[j]){
                min = j;
            }
        }
        if (min != i){
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

快速排序

原理

排序算法总结

分而治之思想:

  • Divide:找到基准元素pivot,将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q],左边的元素都比基准小,右边的元素都比基准大;
  • Conquer:对俩个划分的数组进行递归排序;
  • Combine:因为基准的作用,使得俩个子数组就地有序,无需合并操作。

性能

快排的平均时间复杂度为$O(NlogN)$,空间复杂度为$O(logN)$,但最坏情况下,时间复杂度为$O(N^2)$,空间复杂度为$O(N)$;且排序是不稳定的,但每次都能确定一个元素所在序列中的最终位置,复杂度与初始序列有关。

代码

    public static void swap(int i, int j, int[] arr) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void sortQuick(int[] quickArray) {
        int[] arr = quickArray;
        quickSort(0, arr.length - 1, arr);
    }
    
    public static void quickSort(int start, int end, int[] arr) {
        if (start < end) {
            int pivot = arr[start];
            int left = start;
            int right = end;
            while (left != right) {
                while (arr[right] >= pivot && left < right) right--;
                while (arr[left] <= pivot && left < right) left++;
                swap(left, right, arr);
            }
            arr[start] = arr[left];
            arr[left] = pivot;
            quickSort(start, left - 1, arr);
            quickSort(left + 1, end, arr);
        }
    }

归并排序

原理

排序算法总结

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。

先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解,基本思路是将数组分解成left和right,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以再二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

性能

时间复杂度总是为$O(NlogN)$,空间复杂度也总为为4O(N)$,算法与初始序列无关,排序是稳定的。

###代码

    public static void mergeSort(int[] arr){
        mergeSortDiv(arr,0,arr.length-1);
    }

    public static int[] mergeSortDiv(int[] arr,int low,int high){
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSortDiv(arr, low, mid);
            // 右边
            mergeSortDiv(arr, mid + 1, high);
            // 左右归并
            merge(arr, low, mid, high);
        }
        return arr;
    }

    public static void merge(int[] nums, int low, int mid, int high){
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }

堆排序

原理

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的,虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

二叉堆具有以下性质:

  • 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  • 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)。

步骤:

  1. 构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆。

  2. 堆排序(HeapSort):由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。

  3. 最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。

排序算法总结

性能

时间复杂度为$O(NlogN)$,空间复杂度为$O(1)$,因为利用的排序空间仍然是初始的序列,并未开辟新空间。算法是不稳定的,与初始序列无关。

使用场景

想知道最大值或最小值时,比如优先级队列,作业调度等场景。

代码

排序算法之归并排序(JAVA)-数组形式

计数排序

原理

先把每个元素的出现次数算出来,然后算出该元素所在最终排好序列中的绝对位置(最终位置),再依次把初始序列中的元素,根据该元素所在最终的绝对位置移到排序数组中。

性能

时间复杂度为O(N+K),空间复杂度为O(N+K),算法是稳定的,与初始序列无关,不需要进行比较就能排好序的算法。

桶排序

原理

  • 根据待排序列元素的大小范围,均匀独立的划分M个桶
  • 将N个输入元素分布到各个桶中去
  • 再对各个桶中的元素进行排序
  • 此时再按次序把各桶中的元素列出来即是已排序好的。
排序算法总结

性能

时间复杂度为$O(N+C)$,$O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)$,空间复杂度为$O(N+M)$,算法是稳定的,且与初始序列无关。

使用场景

算法思想和散列中的开散列法差不多,当冲突时放入同一个桶中;可应用于数据量分布比较均匀,或比较侧重于区间数量时。

基数排序

原理

对于有d个关键字时,可以分别按关键字进行排序。有俩种方法:

  • MSD:先从高位开始进行排序,在每个关键字上,可采用计数排序
  • LSD:先从低位开始进行排序,在每个关键字上,可采用桶排序
排序算法总结

性能

时间复杂度为O(d*(N+K)),空间复杂度为O(N+K)。

总结

排序算法总结


image.png

参考文献

[1]经典排序算法总结与实现-基于Python的排序算法总结,写的很不错

[2]排序算法总结-带有优化

今天的文章排序算法总结分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/20214.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注